問題リンク Space Coconut Grab 解法 Z[x]: xが3乗の値かどうか z[x]: v^3 = xとなるような値 v の配列を作っておきます。 後は、xとyを共に0〜1000000まで回してx+y^2+z^3 = eとなるかを調べます。 表向きは(10^6)^2の計算量となりますが、実際には枝刈りが…

問題リンク Gather the Maps! 解法 DPです。 dp[i][j]: i番目の人の手にj日目までに集めることができる地図の最大の集合 とします。地図には0〜n-1番号がついているものとし、集合はその番号の桁のbitを立てることで、整数で表すものとします。 dp[i][j]の漸…

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

問題リンク Big Hit ! 解法 揃った絵柄とボーナスの通りにメダルの枚数を計算するだけです。 ソース

問題リンク Seven Segments 解法 0〜9を"0""1"で表現しておきます。ある数xからyへ変更するには、それらの間で0と1が反転しているビットの所に1を立てればいいです。 ソース

問題リンク Thanksgiving 解法 野菜を値段でソートします。合計額をなるべく小さくしたいので、値段の高い野菜を割引の対象にしたいことになります。これは、袋に値段の高い順に貪欲に突っ込んでいくことで、高い野菜を割引対象にすることができます。 ソース

問題リンク Hit and Blow 解法 数えるだけです。 ソース

問題リンク Kobutanukitsuneko 解法 アルファベットの文字を頂点にしたグラフを作ることで解けます。 例えば、abcという言葉があったら、'a'という頂点から'c'という頂点へ有向辺を引きます。これは、しりとり中にabcという単語を使ったら、この辺を使うとい…

問題リンク Bicycle Diet 解法 (場所, 訪れたケーキ屋の集合)を対にしたグラフで最短経路探索です。今回は負っぽい値が出てくるのでベルマンフォード法を使いました。 場所iからjへの移動コストは距離*kです。ただし、行こうとしている場所がケーキ屋で、既…

問題リンク Stray Twins 解法 2人の子供の位置を対にしたノードで幅優先探索します。 2人が互いに逆向きに進むというのに注意しましょう。 ソース

問題リンク Prime Quadruplet 解法 大きさ10^7のエラトステネスの篩を作ります。そして、N, N-2, N-6, N-8が全て素数であるようなNを列挙しておきます。 入力のnを受け取ったら、列挙されたNの中でnより小さくて一番大きいものを探します。 ソース

問題リンク FizzBuzz 解法 1ステップずつシミュレーションしていくだけです。 人はListで表現し、発言する人のインデックスkを覚えておきます。発言があったときに、正しい答えとkの人の発言が合っていなかったら、リストからkを除き、kを更新します。 ソース

問題リンク Binary Digit A Doctor Loved 解法 小数部が4ケタ以内で表せる小数は16倍すれば(全体を左へ4ビットシフトすれば)整数になるはずです。なので、入力された値を16倍して、小数点以下が0になっているかを調べればいいです。 ソース

問題リンク A Popular Ice-cream Shop 解法 各アイスについて売れた個数のヒストグラムを出すだけです。 ソース

問題リンク Dividing Students 解法 定義通りにクラス分けするだけです。 ソース

問題リンク Walking in the Hospital 解法 最大値を更新していくだけです。 ソース

問題リンク Cutting Down Water Bills 解法 計算するだけです。 ソース

問題リンク Pachimon Creature 解法 ダイクストラを5回やることで解きました。 マス(i, j)と(y, x)の距離ですが、このボード中に通れないマスというのは存在しないので2点間のマンハッタン距離がそのまま移動コストとなります。 次に、最初に持つパチモンの…

問題リンク Autumnal Illumination 解法 幾何問題です。 凸多角形同士の接触判定をバグ無くかけるかがカギになります。 凸多角形i, jが衝突しているとは以下のいずれかを満たすことを指します。 1. jが完全にiの内側に入っている 2. iが完全にjの内側に入っ…

問題リンク Subdivide The Land 解法 全探索+枝刈りです。 i番目の人の求める面積がSだとします。このとき、面積Sであるような長方形で且つ数字iを囲むような長方形の置き方を全通り試します。このとき、他の人と領域がかぶってしまったりする場合枝刈りを加…

問題リンク Highway Express Bus 解法 (都市, 残りの割引券)をノードにしたダイクストラで解けます。 ソース

問題リンク Jogging 解法 ある生徒 i と別の生徒 j が小学校で会うのはそれぞれki周とkj周走った時です。生徒 i が別の生徒 k と一緒に小学校に会うには、 それぞれ ki'周とkk周走った時です。生徒 i が生徒j, kと共に一緒に小学校に会うには、kiとki'の最小…