問題リンク Sheets 解法 a[y][x]: 左下の座標が(x, y)である1*1のマスを覆うシートの数 という表をyについて1行ずつ更新する方法で解くことができました。 シートの枚数が変わるタイミングはシートの上辺と下辺の部分です。 面積はa[y][x]が正になっている部…

問題リンク Make KND So Fat 解法 DPです。 buy[甘味セット][使える金額] -> 体重への影響の最大値 という表を前処理で作ったのち、 dp[何日目][使える金額] -> 体重への影響の最大値 という表を埋めればOKです。 ソース

問題リンク KND is So Sexy 解法 ヘロンの公式を使います。三角形ADCとBECの辺の長さは、計算すると、AD=DC、BE=ECになるような二等辺三角形にすれば面積最大になることが分かります。 ソース

問題リンク Colored Cubes 概要 サイコロがN個あり、各面に色が塗られている。どのサイコロのどの面も任意の色に書きかえることができる。N個のサイコロを全て同じサイコロにするために必要な色の塗り替え回数の最小値を求めよ。 1 解法 全探索です。 サイコ…

問題リンク Manhattan Wiring 概要 H*Wのナンバーリンクのパズルがある。0は空白マス、1は壁、2と3同士が結ぶべきマスである。このパズルを解くために必要な線の長さを最小化せよ。解が無い場合は0とせよ。 1 解法 DFS+枝刈りが方針です。 2を結ぶ線をDFSで…

問題リンク Kuru-Kuru Robot 解法 線分アレンジメントを施したのちダイクストラして解きました。 線分アレンジメントの説明はスパゲッティさんにソースコードと共にあります。ここのソースをおおいに参考にして線分アレンジメントを書きました。オーバーラッ…

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

問題リンク Finding the Largest Carbon Compound Given Its Longest Chain 概要 炭素だけを結合した化合物の構造の中で、最大鎖長がNであるようなもののうち、炭素の数の最大を求めよ 1 解法 Nの偶奇で場合分けすると、炭素の最大数の増え方の規則が見えて…

問題リンク Dominating Set 概要 グラフG = (V, E)の支配集合Dとは、D ⊆ V で、V-Dの全ての頂点が、少なくとも1つのDと隣接しているようなもののことを言う。 与えられるグラフの支配集合のうち、最小の要素数を答えよ。 解法 この問題、おっそろしいことに…

問題リンク The Number of the Real Roots of a Cubic Equation 解法 f(x)を微分してみる問題です。 f(x)を微分したf'(x)は2次方程式になり、その解がf(x)における極値を取る座標になります。極値と極値の間の区間は、ただの単調増加(減少)な関数になるので…

問題リンク 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のサービスは、そのサービスを行っている少女の数だけ復旧度が上…