2012-07-09から1日間の記事一覧
問題リンク Time Sale 解法 メモ化再帰で解くのが方針です。 dp[ i ][ j ][ S ]: 商品の状態がSで(i, j)にいるための最小時間 という表を埋めて解きます。Sは、手に取った商品の番号のビットが立っているような整数です。 この問題の厄介な部分は、移動しな…
問題リンク Hot Spring Trip 解法 頂点を少し拡張してダイクストラするのが方針です。頂点を 0: まだ無料の権利を使っていない 1: 無料の権利を使い始めた 2: 無料の権利を使い終わった という状態に拡張します。 状態0からは0か1 状態1からは2 状態2からは2…
問題リンク Input Candidates 解法 出現単語ごとに登場回数をカウントし、最後に登場回数、辞書式の順でソートすればOKです ソース
問題リンク Quaternion Multiplication 解法 (x1 + y1*i + z1*j + w1*k) * (x2 + y2*i + z2*j + w2*k) を頑張って展開すると (x1*x2 - y1*y2 - z1*z2 - w1*w2) +(x1*y2 + y1*x2 + z1*w2 - w1*z2)i +(x1*z2 - y1*w2 + z1*x2 + w1*y2)j +(x1*w2 + y1*z2 - z1*y…
問題リンク Interest Rates 解法 単利と複利の場合の計算方法があるので計算し、最大値をとる銀行を求めるだけです ソース
問題リンク Calorie Counting 解法 p[i] を満たすお菓子が食べてよいお菓子です ソース
問題リンク Time to Study 解法 区間[s, f)はどれも重ならないので勉強時間はf-sの総和になります ソース