問題リンク 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…

問題リンク 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 解法 総和を取るだけです ソース

問題リンク Ice Maze 解法 色々アプローチを試し、最終的に通ったのは反復深化法でした。 最初に氷をグルーピングしておきます。 ゴールから各マスへの最短距離を調べます。このとき、氷は考慮しません。この距離が、(i, j)からゴールへ辿り着くために必要な…

問題リンク Bara-Bara Manju 解法 深さ優先探索+枝刈りが方針です。 何をどう深さ優先探索したのかという話になりますが、ずばり、「10の作り方」です。 10を和で表現する方法は調べてみると41通りあります。この10の作り方それぞれに番号を振り、k番の10の…

問題リンク Filling Game 解法 深さ優先探索+枝刈りで解きました。 まず、最初から隣接している同色のパネルはくっつけてグループにしておきます。そして、グループ間の隣接リストを作っておきます。 1度くっついたグループは以降離れることはないので、bool…

問題リンク 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の総和になります ソース

問題リンク Alien Messages 解法 全探索+枝刈りで解けました。 ある方向から進入して別のある方向へ出て行くと考えられるので、その動き方は6通りあります。 石像のないマス全てにいずれかの動き方をセットし、1つの閉路ができるかをチェックします。 単純に…

問題リンク The Last Door 解法 e[i][j]: 三角形iを光らせたときの光が三角形jに当たるか否か という表を作ってから、最小何回で全体を光らせるかの処理に入ります。 e[i][j]を作るところから説明します。 3点の中で、三角形の頂点となる点を調べます。これ…

問題リンク Sergeant Rian 解法 DPチックに解きました。が、例によって解いてから時間が経っているので詳細まで覚えておりませぬ・・・。 1の島を根とする木を作ります。木のノードに、「そこから出発し、その木より下の橋を全て爆破してなお且つ戻ってくる…

問題リンク Aizu Buried Treasure 解法 DP+メモ化探索です。 mem[i][j][k]: 段Hにおいて訪れたマスの集合i, 残りの酸素kという状態でマスjに訪れたときの最小コスト というDPを最下層の段から作って行きます。 H段目のmemを埋めるには1つしたのH+1段目のmem…

問題リンク Book Arrangement 解法 マイナス10進数を下の桁から順に求める方針で解きます。 残念なことに、これを解いたのは結構前でソースが何をしてるんだかあまり思い出せません、なので記憶の片隅にあるアイデアだけ述べさせてください。 ある桁kで作る…

問題リンク Life Game 解法 DPです。 dp[i][j]: 所持金 i を持ってマス j へ到着する確率 という表をjが小さい方から埋めることで解けます。これは、ゲーム中、後ろのマスへ下がることがないから可能です。 初期値はdp[初期所持金][0] = 1.0となります。 ま…

問題リンク Dangerous Bridge 解法 イベント処理で解きました。体重wの人物が「橋に乗る」「橋からいなくなる」というイベントを時間でソートしてシミュレートします。同時刻のものがあったら、「橋からいなくなる」イベントが先に来るように順序をつけます…

問題リンク Ninja Climbing 解法 忍者の位置による幅優先探索です。コストは移動距離ではなく、ジャンプした回数です。 ビルの状態によって色々場合分けが必要なので、注意深く実装する必要がある厄介な問題だと思います。 ソース