Learning Algorithms

アルゴリズムの勉強メモ

平面上のロシアゲー(構築ゲー)を解くためのそこそこ一般的なテクについて

平面上のロシアゲー(構築ゲー)を解くためのそこそこ一般的なテクについて

この記事はCompetitive Programming Advent Calendar 2017の12月13日の記事です。

ロシアゲーとは

「ある条件を満たすものを何でもいいから一つ出力しなさい」という形式の問題のことです(参照)。色々なロシアゲーがありますが、この記事では平面上で何かを構築する系のものを扱います。

やり方

1.「ヘビがくねくねしたようなやつ」を作ります。次のようなヘビをヘビAと呼ぶことにします(てきとー)。

f:id:KokiYamaguchi:20171212142314p:plain

そして次のようなものをヘビBと呼ぶことにします。

f:id:KokiYamaguchi:20171212142255p:plain

2. 必要ならばヘビの頭と尻尾をくっつけます。

例えば次のヘビは、ヘビAの頭と尻尾をくっつけたやつです(いつでも作れるとは限りません)。

f:id:KokiYamaguchi:20171212142544p:plain

3. このヘビをいい感じに使います。
4. ヘビを描いただけで問題が解けるので、サルのように喜びます。


このサルでもわかるテクを使って解けるロシアゲーを5問ほど紹介していきます!

その前にこの「ヘビ」について少しだけ書きます。

なぜヘビか?

ヘビには次のような性質があるため、色々な構築に使えそうだということが雰囲気とノリでわかります。

1. ヘビは各場所を高々一回しか通らない
2. ヘビは連結である
3. ヘビの周りの部分は連結である(ヘビが平面を分けることはない)
4. ヘビAは場所を余すことなくきれいに敷き詰めることができる
5. ヘビBは、各部分が互いに接することなく十分近い距離を保ちながら、密度を高くすることができる

これらの性質が構築においてどのような意味をもつかは例題を見ていくと明らかになりますので、早速見ていきましう!

実装自体は大事ではないので省略です。

例題1

D - Grid Coloring

各色が連続した層になって入ったペンを使ってグリッドを塗れればよいので、ヘビAでてきとーに塗ってしまえば終わりです。

ここで利用しているのは、ヘビの性質1, 2, 4です。

例題2

F - RPG Maker

みかけ倒しな問題です。変な制約に注目すると、次のようなヘビBの頭と尻尾をつなげたやつを常に描くことができて、すべての'*'を回収可能であることが言えます。この軌道上でスタート位置に応じて適当にルートを決めればよいです。

f:id:KokiYamaguchi:20171212153537p:plain

ここで利用しているのは、ヘビの性質1, 2, 5です。

例題3

C - AND Grid

editorialには微妙に違う解説が書いてありますが、一般的にヘビで解いていきたいのでこれもヘビで解きます。

まず各紙のどちらも真っ白という状況で得をすることはないので、一枚の紙の上に赤と青を独立に塗って、そこから広げるようにして紫をつくることを考えます。

この一枚の紙をどのようにして作るかというと、まず真っ赤な紙を用意して、その上に青を塗っていくことを考えます。

ここで、ヘビの性質1, 2, 3, 5を使うと、次のようにヘビBを使って青色を塗ればよいことに気づきます。残りの部分は赤色で、性質3からこれも連結になっていますね。

f:id:KokiYamaguchi:20171212153557p:plain

性質5が効いていて、縁を除く任意の位置を紫にすることができます。

例題4

E - すぬけそだて――わっか――

これはグリッドの問題ではないですが、これもヘビで解けます。

まずある向きに、十分大きなヘビを作ってしまって(この時点では性質5より平面がまだ分割されていません)、そのヘビの向きを変えて徐々に重なるようにしていきます。

性質3と性質5が効いていて、小さい個数から十分大きな個数までの平面の分割をうまく調整することができます。

例題5

CS Academy

scoreboardを見ると解いている人があまりいないようですが、これも基本的にはヘビA(の組み合わせ)で殴ればよいです(問題名がMax Snakeなんだからそれはそうという感じなんですが...)。

特に高さと幅の少なくとも一方が偶数のときは、ヘビAの頭と尻尾をくっつけたやつを書けばよいことにはすぐに気づきたいところです。

あとはグリッドを白黒に塗ったときに、少ない方の色からスタートした時は色の個数の観点から構築不可能である場合を除けば、場合分けをしながら頑張ってヘビAを組み合わせていけばよいです。

最後に

このほかにもヘビで解ける問題がありましたらぜひ教えてください!当然どんな平面上のロシアゲーでもヘビで解けるなんていうことはありませんが、とりあえず最初の段階でヘビでなんとかならないかを考えてみる価値は十分あるのではないでしょうか。ここまで読んでいただきありがとうございました。それでは楽しい†ヘビライフ†をお送りください!(ei1333さんのパクリ)