問題リンク A Holiday of Miss Brute Force 解法 ダイクストラで解きました。 dist[x座標][y座標][時刻%6] -> 最小の指示無視回数 という頂点でダイクストラをします。 座標(x, y)において、時刻 t と t+6*k (1 座標は負のことがあり得るので予め+100してお…

問題リンク Kagisys 解法 登録文字列をsetで持ち、鍵の状態を管理しながらシミュレートします。 ソース

問題リンク YAML 解法 YAMLを一番最初に全部読みこんでおくと非常に解きやすくなります。 現在の注目オブジェクトのmapping-itemが羅列してあるインデントの高さを覚えておきつつプロパティを潜っていきます。 インデントの数が等しく、プロパティ名に一致す…

問題リンク Zero Division Checker 解法 スタックに積むのを「整数値」ではなく、「取りうる値の範囲」にすれば解けます。 "/"の演算子が登場してオペランドaとbをpopしたとき、0がbに含まれていると0除算の可能性があることになります。 ソース

問題リンク Kakezan 解法 数xが次にどこに遷移するのかを最初に全部求めておきます。 xがxより大きい数に遷移することはなさそうだなー（勘）ということで、遷移を求める範囲は10^6までで十分です。 無限回の判定は、xを遷移させていって、同じ数に戻った時…

問題リンク Code Art Online 解法 e[i][j]: i番の人が穴jを通ることができる という表を作った後、DFSで辞書順の通り方を調べるのが方針です。i番目の人がj番の穴を通ることができるかどうかは、iの人の最小包含円の半径が穴jの半径以下かどうかチェックする…

問題リンク Transparent Mahjong 解法 加える牌を1種類ずつ試していき、上がることができるかをDFSで探索するのが方針です。 配列を2つ用意しました。 c[k]: kと書かれた牌の数 use[k]: kと書かれた牌で探索中に使った枚数(4を超えないようにする) 更に、変…

問題リンク Anipero 2012 解法 DPもといメモ化再帰で解きました。 dp[歌の番号][折っていないサイリウムの本数][折ってから5分経ったサイリウムの本数][折ったばかりのサイリウムの本数] -> 満足度の最大値 という表を埋めます。 サイリウムは折ったとき、振…

問題リンク Acrophobia 解法 全マスについて移動コストを求めた後、集める巻物の順序を全探索します。 巻物の本数が5本以下と小さいので、DPを使うまでもないと思います。 ソース

問題リンク Problem B War II 解法 自販機の残金、10円玉のストック枚数、R大の人たちの所持枚数を管理しながらのシミュレートです。 自販機の残金が80円のときに100円玉を入れるとジュースが2本分買えそうですが、出てくるのは1本で90円の釣銭が出ることに…

問題リンク Flick Input 解法 1と0以外なら「子音+母音」。それ以外ならちょろっと例外処理を書きます。 ソース

問題リンク Acceleration of Network 解法 復旧度を0日目から3652425日目まで1日ずつ求めるのが方針です。 復旧するサービスが出たり消えたりするので、うまく復旧度の増分を管理します。 t=0のサービスは、そのサービスを行っている少女の数だけ復旧度が上…

問題リンク Village 解法 村をx座標の昇順にソートして、[x-R, x+R]の範囲にある全ての村と距離比較をするというのが方針です。 まず、全ての村の対について距離がR以下か、3R以上という制約があるので、[x-R, x+R]の範囲以外でこれらと同じ表札になる村は絶…

問題リンク The Enemy of My Enemy is My Friend 解法 探索+枝刈りで解きました。 まず、国に番号付けをします。自国が0なら他の国はどんな番号でもいいです。 次に、i番の国に隣接している国をビットマスクの形で保持します。これをadj[i]とします。 更に s…

問題リンク Janken 解法 すっげぇ強い手の集合を作って、その中から適当に出せば350点くらい稼げるだろう、というのが方針です。 強い手の集合は次のようにして作ってみました集合のどれかの手を使えば、全ての手に対して負けない(あいこか勝ちになる) 上を…

問題リンク Power 解法 貪欲法で解けます。 現在カバーできている部屋の右端をfとしたとき、 a を満たす教授の中で、f なお、最初はどの部屋もカバーしていないので、fの初期値は0とします。 最終的にf ソース

問題リンク Social 解法 b[i] にi番のうさぎが何番のボートに乗っているかを格納します。 うさぎpとqが仲が悪いとき、b[p] == b[q]となっていたら、これらのうさぎは気分を悪くします。 ソース

問題リンク Simple Othello 解法 両端の駒の状態だけ見て、O(1)で判定できます。 結論から言うと、両端がともにxのときだけxが勝ち、それ以外はoが勝ちます。 両端がoとxのとき、先攻はx側に駒を置いて両端がoになります。xはどちらに駒を置いても、次のター…

問題リンク Al dente 解法 1番目の砂時計から順番に[T-E, T+E]の区間のどこかを図れるかを調べます。 T+Eが3000弱なので単純なループでも余裕ですが、 T-E となるような最小のkを k = (T-E-1)/x + 1 として求めて、 T-E となっているかを調べるとO(1)でチェ…

問題リンク Milky Way 解法 星を頂点、辺のコストを星間の最短移動距離としたグラフの最短経路を求めるのが方針です。 グラフの最短経路はワーシャルフロイドが短く書けるのでこれを使いました。 問題は星と星の間の距離をどう求めるかです。これは星を線分…

問題リンク Equation 解法 変数はa〜kの11種類あるので、true/falseの割り当て方は2^11 = 2048通りしかありません。割り当て方を全て試し、右辺と左辺で常に結果が正しければ恒等式であると言えます。 右辺と左辺については、BNFに従って構文解析すればいい…

問題リンク You Are the Judge 解法 ログの通りに、正答数、誤答数、ペナルティを計算します。 最後にルール通りにソートします。 ソース