http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0530 足場の位置とすべりやすさが与えられ，向こう岸に辿りつくルートのうち危険度の合計が最小になるときの値を求める問題． 最初はグラフとみて Dijkstra 法で解いて 00:19 sec，2988…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0529 N 個の得点が与えられ，この中から4つまで選んでその合計を最大値を求める問題． ただし，合計が M を超えてしまった場合は 0 点になってしまう． 最初 DP でいけるかと思ったけど…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0528 ある2つの文字列が与えられて，それの最長共通部分文字列の長さを答える問題． 空文字列は任意の文字列の共通部分文字列とし，空文字列の長さは 0 とする． 最初は最長共通部分文…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0527 規則に従って白黒の碁石を並べていったときに，最終的に白が何個あるかとう問題． 言われた通りにシミュレーションすると最悪 O(n^2) になって n 連続する同じ色の碁石の数のリス…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2153 BFS するだけ． # だけじゃなくて部屋の端も # と同様に壁と見なされることに注意 (これで WA 出してしまった)． なんか statistics 見ると自分だけメモリ使用量が少ないんだけど…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1168&lang=jp 本番中に解けなかった問題． 入力がひどい(と思う)ので一旦それぞれのピースにユニークな id を割り振ってから解いた． check の型が若干アレだが，start の地点にあるピ…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2200&lang=jp Warshall-Floyd で陸路のみ・海路のみを用いた場合のそれぞれの最短経路を求めた後に DP． 街 j に船がある場合の i 番目の集配地への最小コストを dp[i][j] は，i 番目の…