問題リンク Walking Santa 解法 x座標方向とy座標方向について独立に考えます。 ある点Xと、N個のx座標の差の絶対値の総和が最小になる場所はど真ん中の座標です。例えば、Nが奇数なら中央のx座標、Nが偶数個なら中央2つのx座標の区間内が最小になる場所です…

問題リンク Bingo 解法 DPで解いたわけですが、DPについて色々と考えさせられる問題でした。 まず、ビンゴカードは狭義単調増加の長さN*Nの1次元配列と捉える事が出来ます。つまり、1〜Mの中からN*N個の要素を取り出して、その和がSになるパターン数を答える…

問題リンク Card Game II 解法 公式解説を読んで解きましたが、所々理解が追いついてない状態です。 Mで場合分けして解くようです。 M=0のとき、nk枚目に引くカード(最後に引くカード)が1である場合が、ゲームをクリアする必要十分条件というらしいのです。…

問題リンク Can I go there? 解法 長らく悩んでいた問題なんですが、折れて答えを調べました。 次のすげぇ性質を使うようです行列A^kの(i, j)成分を、頂点iから頂点jへkステップで到達できるなら1、そうでないなら0、と決めると A^1 = グラフの隣接行列 A^m …

問題リンク 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以外なら「子音+母音」。それ以外ならちょろっと例外処理を書きます。 ソース

問題リンク The Closest Circle 概要 N個の円が重なることなく散らばっている。円同士が最も近づいている場所の距離を求めよ。円同士の距離は、 中心間の距離−円1の半径−円2の半径 とする。なお、N個の円の中の半径の最小値をRとすると、全ての円の半径rはR …

問題リンク Super Star 概要 3次元上の点がN個与えられる。点を全て包含するような球の最小の半径を答えよ。 4 0 点は互いに0.01以上離れている 解法 いわゆる最小包含球を求める問題です。ココにすごく分かりやすい解説がまとまっているのでこれを参考にし…

問題リンク Driving an Icosahedral Rover 概要 20面体を点(0, 0)に、"0"を接地させ"5"が北側になるように置く。1ステップに3方向へ転がすことができる。点(x, y)に数字nが接地するように動かすための最小ステップ数を答えよ。nが接地さえしていれば方向は問…

問題リンク Hit and Blow 概要 Hit and Blowをする。今、N回の試行とその結果が分かっている。試行結果から、答えが1つに定まるならその答えを出力せよ。 そうでなければ新たに数xを試行する。試行し、その結果から解が一意に決まるならばそのxを答えよ。xが…

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