問題リンク Kongo Type 解法 入力値を16進数の1つの整数としてみて、ビットマスクを使って解きました。 (0.5)^n の浮動小数点は誤差なく正確に計算できるので、色々と心配しなくて大丈夫です。余談 入力値が32ビットなので、楽をするためにInteger.parseInt(…

問題リンク Triangle of Blocks 解法 配列でブロックの個数を管理して解きました。 あとは問題文通りにシミュレートさせるだけです。 ソース

問題リンク Aka-beko and 40 Thieves 解法 DFAの遷移関数を書いて解きました。 A: 1 X: 2 Y: 3 Z: 4 W: 5 B: 6 砂漠: 0 という風に状態を置いています。 ソース

問題リンク Finite Field Calculator 解法 構文解析です。 四則演算の解析にちょろっと手を加えれば解けます。 ソース

問題リンク Beat Panel 解法 DPで解きました。 dp[i][S]: iターン目終了時点のボタンの状態がSのときの最高得点 という表を埋めます。 ボタンの状態や押すボタンの状態、押した後のボタンの状態など全部ビット操作で書けば、コードがめっさスッキリしますね。…

問題リンク Making Sugoroku 解法 マスを頂点にした有向グラフを作ります。 マスiからサイコロを振って進み、マスの指示に従って辿りつけるマスjに向かって有向辺を張ります。あがりマスから逆辺を辿ると、訪問したマスはあがることができるマスになります。…

問題リンク Mayan Crucial Prediction 解法 入力された日が基準日(0.0.0.0.0 or 2012/12/21)から何日離れているかを計算して、もう片方の暦の上でその日数分、日にちを進めました。 1日ずつカウントするとえらいことになるので、1周期(マヤなら13*20*20*18*2…

問題リンク Surf Smelt Fishing Contest II 解法 最初はPriorityQueueでゴリオシできると思ったのですが無情のTLE。 なのでセグメント木っぽいの作って解きました。 木のノードには、その区間の最大匹数とそのidを持たせておき、クエリが来るたびに更新しま…

問題リンク Maximum Sum Sequence II 解法 よくある総和の問題です。 (1, 1)-(i, j)の部分行列の総和S[i][j]を前計算しておくと、 (y, x)-(i, j)は S[i][j] - S[y-1][j] - S[i][x-1] + S[y-1][x-1] で求められます。 ソース

問題リンク Sum of Integers II 解法 DPです。 dp[N][X][S]: X以下の数字から異なるN個を選んで、和がSになる組み合わせ数 という表を埋めれば解けます。 解法2 DPですが、 dp[N]: 2個の数字を使って和がNになる組み合わせ という表を用意して dp[i] * dp[N-…

問題リンク Sum of 4 Integers II 解法 よくあるタイプの数え上げ問題です。 (a, b)と(c, d)の組に分け、(a, b)で和sを作る組み合わせ数、(c, d)で和n-sを作る組み合わせ数を掛け合わせていけば解けます。 ソース

問題リンク Surf Smelt Fishing Contest 解法 1人ずつ記録を見ていって、定義通りに優勝者を探します ソース

問題リンク Calculation of Area 解法 割るだけです ソース

問題リンク Blur 解法 DFS+枝刈りで解きました。 f(i, j, k, drop): 既にk滴使っている状態でマス(i, j)に大きさdropの滴を落とす という関数を作っておいて、左上から右下のマスへこの関数を再帰させます。 問題が与えている座標系は(x, y)座標ですが、自分…

問題リンク Taro's Obsession 解法 容疑者を頂点にした有向グラフで考え、Y->Xという証言を辺にします。頂点の出次数が0の頂点はもう出力してしまってよく、その頂点をグラフから取り除きます。これを繰り返せばOKです。 ソース

問題リンク Salary for a Plumber 解法 ジョイントを1つ使うと、使ったジョイントの長さだけパイプの長さの総和が伸び、パイプの本数が1つ減ります。残ってるジョイントの内、最も長いものを使えば、N-1本における給料が最大になります。ジョイントを使って…

問題リンク All Numbers Lead to 6174 解法 数NをソートすればSになり、SをreverseすればLになります。 入力された数値が1111の倍数なら"NA"です ソース

問題リンク Kitchen Garden 解法 i番目の草が雑草の場合、数列からi番目を除いたものが等差数列になるので、iをN+1通り全部試せば解けます ソース

問題リンク Railway Ticket 解法 2進数だと思えば1か6の時にOpenと判定できます ソース

問題リンク Points for a Perfect Scorer 解法 総和を取るだけです ソース