問題文 : DNAの合成解法 : dp[M] = M番目の文字までを構成するのに必要なDNA素数の最小値, とすると, M + 1 ~ M + kまでの部分文字列s_kがあるとするとdp[M + i] (1 ≦ i ≦ k) = min(dp[M + i], dp[M] + 1) となる. DNA素を全て確かめるとO(strlen(合成したい…

問題文 : 占い解法 : あるカードを奇数回ひっくり返せばそのカードは裏で, 偶数回ひっくり返せばそのカードは表である.これは, カードをひっくり返す順序によらないので, y1 ≦ y ≦ y2 行 x1 ≦ x ≦ x2列のカード をひっくり返す, という命令を x1 ≦ x ≦ x2と…

問題文 : MooFest解法 : 2匹の牛について、離れている距離*Max(牛iの聴力, 牛jの聴力)が必要な声のレベルなので、 (全ての声の大きさの総和) = 最も聴力が必要な牛 * 離れている距離の総和 + 次に聴力が必要な牛 * 離れている距離の総和 + ... となる.ゆえに…

結果 : ooo--o---- 4完 31点 3WAくらい. 9位でなみだらしい＞＜感想 : デバッグに2時間位費やした点以外はだいたい良かったと思う. 5は思いついていた解法の計算量を測り間違えて書かずに残念なことをしてしまった. 4も簡単な幾何だったので, ちゃんと読もう…

問題文 : ルパン四世解法 : まず, bitDPで最短時間を求める. その後に, 最短時間を達成する訪問の仕方を出発するノードから確かめていく. 出発するノードは, dp[S | S_n = 1, else S_i = 0][n]の中で最も小さいものとなる.誤差に注意して計算していくこと.コ…

問題文 : 冊子の配布解法 : 得られるやる気を最大化したいので, 葉まで冊子を流し, その中の最大値を取っていけば良い. つまり、葉までやる気を伝搬させれば良い. この操作をM回繰り返す.木の操作、最大値の取得をO(N)時間で行うことで, O(MN)時間でこの問題…

問題文 アナグラム(pdf注意, 1枚目)解法 : 元の文字列sの各文字を昇順にソートしたs'を考える. 目的の文字列の前にある順列の総数は, s'の先頭から文字を選んでいき, 元の文字列の接頭辞にならない文字列の組み合わせを全て求めれば求まる. もとの文字列と現…

問題文 : 象使い(pdf注意, 2-3ページ目)解法 : 辺と辺で成される角を求めるには, (直前の点, 今いる点, 次に行く点)の3つの情報が必要である.直前の点をvec(P_0) = (x0, y0), 今いる点をvec(P_1) = (x1, y1), 次に行く点をvec(P_2) = (x2, y2) とすると (vec…