問題リンク : True Liars | Aizu Online Judge問題概要 : 自分今、伝説の島にいる その島には正直者と嘘つきがいて、自分はその正直者に用事がある 以前の調査で正直者はp1人、嘘つきはp2人いることが分かっている 今、各人に１から昇順に(p1+p2)まで番号を…
問題リンク : http://uva.onlinejudge.org/external/119/11908.pdf問題概要 : いくつかの重み付きの線分が与えられる それらの内いくつかを選択し、その重みの総和を最大化せよ ただし、ある点が複数の線分におおわれてはならない解法 : 重み付き区間スケジ…
問題リンク : Problem - 1693問題概要: h*w のグリッドがあり、各マスには木が生えているかなにもないかのどちらかである 化け物が木の生えているマスに現れ、隣接するマスで木が生えているマスに移動しどんどん木を食べて、その後に消える 移動経路が円にな…
問題集 : ( タグはネタバレを含むため白文字 ) ・ AOJ 2171 Strange Couple : Strange Couple | Aizu Online Judge タグ : 期待値、連立1次方程式・ yukicoder No.75 : No.75 回数の期待値の問題 - yukicoder タグ : 期待値、連立1次方程式・ AOJ 2172 Queen…
問題リンク : http://uva.onlinejudge.org/external/120/12086.pdf問題概要 : 長さNの数列とクエリーが与えられる クエリーの種類と効果は次の通り 1. S x y 数列のx番目の要素 ( 1-indexed ) を y に変更する2. M x y 数列のx番目の要素からy番目の要素まで…
問題リンク : TV Watching | Aizu Online Judge問題概要 : N本のテレビ番組の情報が与えられる 同じ時刻に複数の番組を同時に見ることは不可能なので、自分はそのテレビ番組をリアルタイムで見るか録画して後で見るかを選べる リアルタイムで見た時の満足度…
問題リンク : http://uva.onlinejudge.org/external/125/12509.html問題概要： n本の線分が与えられる 線分はx軸かy軸に平行である 外側から到達可能な線分の部分の長さの総和を求めたい解法 : 線分アレンジメント + 座標圧縮 + DFS 線分をアレンジメントし…
問題リンク : http://uva.onlinejudge.org/external/122/12294.html問題概要 : ゲームの主人公の初期の力はpであり、これからn個のステージを全て入力で与えられた順番でクリアしなければならない ( できない場合は"Impossible"と出力 ) 各ステージは p1, p2…
問題リンク : http://uva.onlinejudge.org/external/122/12295.html問題概要 : n * n のセルがあり、セルの中には1以上9以下の数字がかかれている 左上を(0,0), 右下を(n-1,n-1)としたとき、左上から右下へ移動する経路のうち、通ったセルの数字の和が最小と…
問題リンク : Crop Circle | Aizu Online Judge問題概要 : n個の円の中心点の座標と半径が与えられる 円周上で他のどの円にも囲まれていないような部分の長さの総和を求めよ解法 : 各円について、他の円との交点で細分化する 例えば円0については以下通りに…
問題リンク : D: 禁止された数字 - AtCoder Beginner Contest 007 | AtCoder問題概要 : A以上B以下の整数で４か９を含むものの数を求めよ解法： 桁DP dp[桁][ぎりぎりかどうかをboolでもつ] := 総数 間違えて４も９も含まない数字を数え上げてしまったので全…
問題リンク : http://uva.onlinejudge.org/external/17/1707.pdf問題概要 : 凸多角形の建物がある それはn枚の壁からなり、壁は１からnまで番号がつけられている k個のカメラがその建物のまわりに設置してあり、i番目のカメラはs[i]からt[i]までの壁を撮影で…
UVa演習 2014/7/14 (月) 問３問題リンク : http://uva.onlinejudge.org/external/103/10328.html問題概要： n回コインをなげたとき、2^nだけコインの状態がある そのうち連続でk回以上表がでているようなものはいくつあるか？解法: 動的計画法 dp[何桁までみ…
UVa演習 2014/7/14 (月) 問2問題リンク : http://uva.onlinejudge.org/external/115/11500.html問題概要： 2人のプレイヤーでゲームを行う プレイヤー１の体力はEV1,プレイヤー２の体力はEV2である ゲームがはじまるとプレイヤーが交互にサイコロをふってい…
UVa演習 2014/7/14 (月) 問1問題リンク : http://uva.onlinejudge.org/external/111/11181.html問題概要： N人の人がショッピングにいく 人i ( 1 N人中ちょうどr人が何かを購入する時、人iが何かを購入する確率を求めよ制約： 1 0 0.1 解法: Nが２０人しかい…
UVa演習 2014/6/24 (火) 問3問題リンク : http://uva.onlinejudge.org/external/104/10453.html問題概要 : 文字列が与えられる その文字列の任意の場所に任意の文字を任意の数だけ追加できる 追加の回数を最小にして回文を作成せよ そのときの最小の追加回数…
UVa演習 2014/6/24 (火) 問2問題リンク : http://uva.onlinejudge.org/external/111/11151.html問題概要 : 文字列が与えられる 文字列から余計な文字を削除して良いのでそこから得られる最長の回文の長さをもとめよ解法： メモ化再帰 両端を決めてどちらを削…
UVa演習 2014/6/24 (火) 問１問題リンク : http://uva.onlinejudge.org/external/107/10739.html問題概要： 長さ１０００以下の文字列が与えられる この文字列のアルファベットに対して以下の３つの操作を自由に使うことができる ・任意の場所に任意のアルフ…
問題リンク : Pump up Batteries | Aizu Online Judge問題概要： N人のボディーガードは1から順にNまで番号が割り振られており、それぞれがウェアラブルコンピュータを身につけている 各ウェアラブルコンピュータは使える時間とその後充電にかかる時間を周期…
UVa演習 2014/6/17 (木) 問1問題リンク : http://uva.onlinejudge.org/external/12/1220.html問題概要： とある会社の社員達がパーリィを開くことにした Big Bossと呼ばれる社員以外はちょうど１人のボスをもつ(つまり、ツリー状のグラフになる) パーリィに…
UVa演習 : 2014/6/16 (月) 問１問題リンク : http://uva.onlinejudge.org/external/2/245.html問題概要： 暗号化されたテキストが与えられるので復号せよ解法： 書いてある通りに実装するコード： #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i</bits/stdc++.h>
UVa演習 2014/6/17 (火) 問１問題リンク : Scheduling Lectures問題概要： n個のジョブがあり、それぞれ処理にt[i]秒だけ時間がかかる ジョブは0から順番に番号付けられていて、0から順に処理されていかなければならない １つのプロセッサーで処理できるジョ…
問題リンク：http://uva.onlinejudge.org/external/117/11753.html問題概要： 文字列に文字をいくつか追加して回文にしたい K回以下の追加で回文にできるか？解法： 実際に再帰で試してみて最小の追加回数を求めるコード： #include<bits/stdc++.h> #define REP(i,s,n) for(</bits/stdc++.h>…
UVa演習 : 2014/6/10 (火) 問8問題リンク : http://uva.onlinejudge.org/external/106/10690.html問題概要： N+M個の整数(-50以上50以下)が与えられる (x1+x2+...+xN)*(y1+y2+...+yM)の最大値と最小値を求めよ解法： 動的計画法 dp[i個の整数をつかった][そ…
UVa演習 : 2014/6/10 (火) 問７問題リンク : http://uva.onlinejudge.org/external/100/10069.html問題概要： ２つの文字列X,Zがあたえられる X中に部分列としていくつZが存在するか？数えよ解法: 動的計画法 dp[Z[0:i]][X[0:j]] := 総和 ただし答えは10^100…
UVa 演習 2014/6/9 (月) 問2問題リンク：http://uva.onlinejudge.org/external/103/10364.html問題概要： 最大２０本の棒があり、それらの長さが与えられる これを使って正方形をつくれるか？解法： 再帰で探索する POJのsticksの下位互換コード: #include<bits/stdc++.h> #</bits/stdc++.h>…
UVa演習 2014/6/10 (火) 問６問題リンク : http://uva.onlinejudge.org/external/123/12324.html問題概要： スペースシップで旅をする 旅はn個のフェーズに分かれている 各フェーズはt[i]秒で終わる 各フェーズでb[i]個のスペースシップ加速素材を手に入れる…
UVa演習 2014/6/10 (火) 問５問題リンク : http://uva.onlinejudge.org/external/112/11218.html問題概要： 9人で歌を歌いたい 3人１組でそれぞれが１回ずつ歌う 3人の組み合わせとその組み合わせにすることで得られる得点が入力として与え等れるので得点を…
UVa演習 2014/6/10 (火) 問４問題リンク : http://uva.onlinejudge.org/external/118/11832.html問題概要： N個の正の整数が与えられる これらに任意の符号を付け、その総和をFにしたい 各整数の符号を決定し、正でも負でも良いなら'?',正なら'+',負なら'-'…
UVa演習 2014/6/10 (火) 問３問題リンク:http://uva.onlinejudge.org/external/110/11088.html問題概要： n人の人がいて、それぞれが３０以下のパワーをもっている その中から3人チームを何組か作りたい チーム全体のパワーは２０以上でなければならない 最…
