ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

JOI

第11回日本情報オリンピック 予選 E - イルミネーション

お題箱より。 E - イルミネーション (Illumination) 解法 座標の表記について、(縦の座標, 横の座標)という順番で表記することにします。こちらのほうが配列の添字順と合うので都合が良いです。 公式解説と同じく、与えられる領域の外周にもう1つ分の六角…

第11回日本情報オリンピック 予選 D - パスタ

お題箱より。 D - パスタ (Pasta) 解法 ※実装に合わせて、0-indexedでの記述とします。最初の日は 日目です。 日目から順番にパスタの種類を決めていくことにします。ルールは「事前に指定された日のパスタの種類は決まっている」ことと「3日連続で同じパス…

第16回日本情報オリンピック 本選 B - 準急電車 (Semiexpress)

お題箱より。 B - 準急電車 (Semiexpress) 解法 後戻りできないこと、急行が停まる駅には必ず準急も停まることから、駅 からある目的駅までの最適な移動経路は「行けるところまで急行で行く→行けるところまで準急で行く→残りは普通で行く」となります。 その…

JOI春合宿2015 K - 遺産相続

お題箱より。JOIの解説記事は初めてかな…? K - 遺産相続 解説途中の証明についてのリクエストだったのでそこを重点的に書きます。 解法 最大全域木として考える 都市を「頂点」、鉄道を「辺」、鉄道の収益を「辺重み」と考えます。 「閉路ができない範囲で…