Advent Calendar Contest 2013、終了しました。
参加していただき、ありがとうございました。
コンテスト結果→各問題の軽い解説→統計、という流れで書きます。
コンテスト結果
ペナルティシステムは多分あまり意味をなしていない気がするので、完答数でいきます。
１位：rng_58さん,cgy4everさん（６問全問正解）
２位：antaさん,hirosegolfさん（５問正解）
３位：uwiさん（４問正解）
４位：tomerunさん,ushさん（２問正解）
５位：tozangezanさん,catupperさん,xyz600さん,Lepton_sさん,ACRashさん,omeometoさん（１問正解）
おめでとうございます。
各問題の軽い解説
戦艦のパズル
[+解説を開く]
ルールのところに「この問題の制約をよく読んで解かなければならない。」とあるので制約を読みます。
「sum(X) = sum(Y) = N*N/2 (切り捨て)」
と書いてあります。つまりoの数は N*N/2 個（だいたい全体の半分くらい）です。実はこれめちゃくちゃDenseです。とりあえずmaxでいくつまで置けるかを考えてみます。
「向きと長さが全く同じ船が２つ以上あってはならない。」「船の長さの偶奇は、Nの偶奇と一致していなければならない。」なので、使える船はかなり限られています。
Nが偶数の場合
2縦,2横〜N縦,N横しか盤面に収まらないし、N縦とN横は同時には入れられなさそう。
長さの合計を計算してみると、N*N/2になっています。
Nが奇数の場合
1,3縦,3横〜N縦,N横しか盤面に収まらないし、N縦とN横は同時には入れられなさそう。
長さの合計を計算してみると、(N*N-1)/2になっています。
ということで、入れるべき船の形は確定しました。これを敷き詰められれば勝ちです。
長い方から入れていってみます。次の船のことを考えながら入れて行くと、残っている領域の両端のうちのどちらかに入れるしかないことが分かります。あとは、どちらに入れるべきなのかを周りに書いてある数字から判断して入れて行けば良いです。
maxで入れると1/2くらいになる、の図
孤独のパズル
[+解説を開く]
まずは各列・行について、１つしかない数字は塗りつぶせないのでそれらを消します。
下の例でやってみます。
1 2 1 3 4 5 2 3 4 1 5 3 1 4 1 5 3 2 3 1 5 4 2 3 4 5 3 2 2 1 5 3 2 3 1 4
ここから塗りつぶせないのを消します。
1 x 1 x x x x 3 x x x 3 1 x 1 x x x x x x x x 3 x x x x 2 x x 3 x 3 x x
1の塗りかたは２通り、2,3の塗りかたは１通りになっていると思います。
残った数字を頂点として、同じ行/列にある数字どうしに辺を張ったようなグラフを作り、連結成分毎に
・サイクルなら２倍
・パスなら１倍
として計算して行けば良いです。
別解？
各行/列の条件は「あるマスかあるマスのうち片方だけを塗る」なので、"塗る"を1、"塗らない"を0としたときに「あるマス＋あるマス＝1 (mod 2)」となっています。つまり、こういう連立方程式の解の個数を掃き出したりして計算すれば良いです。
が、計算量やばいので、意味のない項を消したり64bit高速化したり、頑張らないと多分無理です。(頑張っても無理かも？)
愚者のパズル
[+解説を開く]
想定解・the_n_kaidoes(○△○)さんタイプ
まず、どんな解法でも共通だと思いますが、偶数回の操作で作ることができる形と奇数回の操作で作ることができる形に分け、それぞれの特徴を探ります。
チェス盤に置いた時に黒いマスに来るか白いマスに来るかで、各ピースを２つの同じ形のパーツに分けてみます。すると、0のグループは／の方向に二つ連なった形、1のグループは＼の方向に二つ連なった形になります。
さて、これを45度右に回転させて、チェス盤の黒いマスだけに注目すると、
・0のグループは横向き、1のグループは縦向きのドミノを敷き詰めたもの
となっているため、二部グラフの完全マッチングを１つ求めてそれを復元するなりして縦向きのものを数えれば良いです。
rngさんタイプ（多分tomerunさんもこれに近い？）
こう斜めにみて各列の個数を見ると、
・0のグループは(1,1,1,1)・1のグループは(2,2)
これらを各列を端から見て行て、奇数個の時は今の行から４列先までの値を-1していく。すると0のグループが何個あるかがmod 2で分かる。
cgy4everさん・hirosegolfさんタイプ
・0のグループは(1,1,1,1)・1のグループは(2,2)
→４つおきに偶奇を調べて足すだけで分かるじゃん。
実に簡潔だった。
ACRash(△□☆□)さんタイプ
101110111011 001000100010 111011101110 100010001000 101110111011 001000100010 111011101110 100010001000
みたいなフィルタをかけて、1の部分にあるブロックの個数を数えれば良い。
なんでこんなの思いつくんだ・・・
と思って聞いてみたところ、どうせこんな感じで解けるだろうと４×４のパターンの敷き詰めを全部試してみたらしいです。
なんでこんなの思いつくんだ・・・
超面白いっ
antaさんタイプ
気合い（submission参照）
コメント
いろんな解法があって面白かったです。
この問題はチャレンジやhackのあるコンテストには、入力チェッカーが作れる気がしないので出せません。ちなみに入力データが正しいことの証明はこちら。
新作のパズル
[+解説を開く]
とりあえず、１つブロックを選んでXとします。で、そいつに対応するブロックがどれで(Yとします)、二つのグループの向き関係がどうなってるのかを全部試します。
「あるブロックがXと同じグループにあるならどのブロックがYのグループになるか」みたいな有向辺を張ります。行き先にブロックがない場合、"あるブロック"はYのグループであると確定できます。そんな感じでやって行って、矛盾したら答えはないです。
さらに上記のグラフにサイクルが出来ていた場合はAmbiguousになります。(ただし、ブロックが２つしかない場合はValid)
あとは、Yと向きが違っても分け方が同じならばAmbiguousにはならないとかに気をつければ良いと思います。
実装がちょいめんどくさいです。
禁断のパズル
[+解説を開く]
禁断のパターンについて考察します。
色が違う辺に黄色い線を引いてみました。４マスの中心(青丸)に注目すると、右側二つの禁断でないパターンの方では次数が２となっています。全ての交点から出ている辺が二本ずつになるような感じにすると良さそうです。
周りには緑マス(赤マスでもいい)が敷き詰めておくといい感じになります。
黄色い辺からいくつか使う辺を選び、青の点の次数が２紫の点の次数が０になるように出来れば"Yes"、出来なければ"No"です。
あとは、チェス盤方式で二部グラフにして適当に辺を張って、最大流を求めれば良いです。
完成図は交差しない輪っかがいくつか出来ている形となり、輪っかの中と外で色が反転している感じになります。
コメント
どうやら最難だったらしい。
ほぼ既出みたいなものなのにー。(まあリンク先の問題は結構いじってあるけど「輪っかで被覆する」っていう原型はこれと同じ)
SATsolverでは解けなかった模様です。
聖夜のパズル
[+解説を開く]
例題の方
オートマトンを見てみると「○○××△△...ク」というパターンが受理されるということが分かります。
とりあえず、偶数歩目で訪れるマスから奇数歩目で訪れるマスへ、二つのマスの文字が同じであるという条件のもと有向辺を張って行って、あとはそれらを適当に繋ぐと解けます。
問題の方
適当に僕が想定していた解答の過程を追って行きます。
まず、オートマトンの序盤と終盤に着目し、全マスを通ることが出来なくならないように気をつけつつ線を引いて行きます。
下の離れ小島に入らないように進めて行きます。
ここが一番難しいところだと思います。
"ク"に注目します。オートマトンの右下の方で「"ク"("クク"や"ククク"はダメ)」が必要になるため、図の上の方の"ク"３つを繋げてしまうと、オートマトンの二段目右から２つ目の状態から抜け出すために図の右下の"ク"を使わざるを得ないためうまくいきません。
また、オートマトンの二段目右から２つ目の状態から抜け出すために図の右下の"ク"を使ってしまうと、オートマトンの右下の方を抜け出すことが不可能になってしまいます。つまり、オートマトンの二段目右から２つ目の状態から抜け出すためには図の上の方の"クク"を使わなければなりません。
途中経過です。この盤面では右下の"ク"に注目すると良いです。
最後のロジックです。"ス"を奇数回通って折り返し、2 (mod 3)個目のマスが"リ"である経路は一意に定まります。
ふぃー、完成。
あとは入力ミスに気を付けるだけです。
コメント
修正が何回か入ってごめんなさい。
残りコンテスト時間が短いし、意表を突けそうだし、さくっと解けそうなクリスマスに関連したペンシルパズルを出そうと思って作りました。
最初は適当によくありそうなルールで適当に作ろうとしていたら自明すぎる問題とかしか出来なくて、悩んでたらオートマトンというアイデアが降ってきました。
いろんなバリエーションの問題が作れそうで結構面白いのでは？と思っていますが、問題を作るのが結構ムズイです。ちょっとまた作ってみて面白い問題が出来たらどこかで出そうかなとか思ってます。
antaさんがプログラムで解答をされていて驚きました。(解は一意らしいので安心しています)
統計
| 戦艦 | 孤独 | 愚者 | 新作 | 禁断 | 聖夜 | |
|---|---|---|---|---|---|---|
| 正解者数 | 11 | 6 | 6 | 5 | 2 | 6 |
| 提出数 | 37 | 13 | 66 | 48 | 25 | 19 |
| FA | rng_58 | rng_58 | rng_58 | cgy4ever | cgy4ever | omeometo |
追記：NPCA Judgeがなくなったので、HackerRankに移植した。前２問の問題文は消失したので適当に書いた。
