Xmas Contest 2017 I問題 SAT Puzzle 解説

問題 | 解説まとめ

まずはコードです。
このコードでやっていることを解説します。

まず、各マスには「黒」または「白」ではなく、「黒」または「(1,1)~(4,4)」を割り当てることにします。
ただし、(j,k)は「j番目の白マスグループのk番目のマス」を表すものとします。
これを実現するには、黒を割り当てることを表す x[1]~x[36] の他に、マス
i に (j,k) を割り当てることを表す変数 x'[i][j][k] を用意し、条件を節として書き連ねていきます。
書かなければいけない条件は以下の通りです。

• 各マスは「黒」または「(1,1)~(4,4)」のいずれかちょうど１つに割り当てなければならない。
• 「(1,1)~(4,4)」が割り当てられるマスはそれぞれちょうど１つずつでなければならない。
• 「(j,1)~(j,4)」は連結でなければならない。
• 「(j,k)~(j',k')」(j≠j')は隣接してはいけない。

１つ目と２つ目

１つ目の条件では、各 i について x[i] と x'[i][1~4][1~4] のうちちょうど１つが真であれば良く、
２つ目の条件では、各 j,k の組について x'[1~36][j][k] のうちちょうど１つが真であれば良いです。
いずれにおいても「いくつかの変数のうちちょうど１つが真」というのを表現できればいいです。
これは、例えば a,b,c の3つの変数のうちちょうど１つのときは、

• (a V b V c)（少なくとも１つは真）
• (-a V -b)^(-b V -c)^(-c V -a)（どの２つを取ってきてもどちらかは偽＝多くとも真は１つ以下）

と表現できます。

３つ目

「連結」という条件をそのまま扱うのは難しいため、「うまく有向辺をはると根付き木ができる」という条件として実装します。
このとき、辺は小→大へのみ張れることとし、根は1番になるようにするとします。
つまり、k=2~4について、隣接のいずれかに1~k-1のいずれかがあれば良いことになります。
これを節で表すと、

• (x'[i][j][k] → V(x'[i'][j][k'] | i' ∈ iの隣接, 1 ≦ k' < k))

A→Bは「AならばB」の意味で、(A,B)が(真,偽)のときのみ偽となります。
これをCNFに直すと、

• (-x'[i][j][k] V (V(x'[i'][j][k'] | i' ∈ iの隣接, 1 ≦ k' < k)))

となります。（数式が見にくいのでソースコードも参考に・・・）

４つ目

隣接するマスが別グループであってはならないという条件。
ドモルガンでandの否定を否定のorに変換するのはSATの基本。

• (-x'[i][j][k] V -x[i'][j'][k']) (i' ∈ iの隣接, j ≠ j')

これで満点が取れます。

パズルをSATで解く話は昔、準急がJOIの春合宿の講義でしていて、すごく面白かったので自分でも遊んでみてたりしました。（なのに準急がこれ解けなかったのは意外だった）
楽しいので、他のパズルのソルバも書いて遊んでみてください。
初心者向けなのは数独かなぁ。
僕は美術館とひとりにしてくれを昔書きました。
僕のコードはここにあります。（honeyはこの問題の元になったハニーアイランドというパズルで、これは普通に枝刈り探索のコードです）（number_linkはgraphillionで書きました）
github.com

Xmas Contest 2017 H問題 Ango 解説

問題 | 解説まとめ

リアクティブ・encode/decode系の変わった問題。
部分点はmax(x)に関する関数にしてもよかったかなぁ。

部分点１

割と効率が悪くてもACできますがそこまで簡単ではないと思います。
例えばNが小さければフィボナッチ数列でいけますが、N=300だと厳しいです。
解答例としては、xを乱数にしたり、和が被らないようなxを愚直に探索するなどがあります。
N=300なら２つ選んだ時の和というのはあらかじめ列挙できるのでクエリに答えるのはあまり難しくありません。

部分点２

xは乱数でもおそらく被らないと思いますが、Nが大きいのでクエリへの応答が困難です。
ここで、さえ分かっていれば a も b も求まるということを唐突に思いつきます。（そもそも僕が数日悩んだのち唐突に思いついたため、こうとしか解説できず）
（として、が求まり、が求まり、として a, b が求まります）
これを実現するにはなどとしてなどとしておけば、として S, T が求められます。

部分点３

などとして、全ての演算の法をpとして計算します。
mod計算で難しい部分はsqrtですが、今回は1~400000についての二乗mod pの値を前計算しておけば十分です。（効率的に計算したい人はこちらを）
ちなみにsqrt(x) mod pの値は一意に定まらず２つありますが、正負が違うだけなのでどちらでも良いです。

Xmas Contest 2017 G問題 Maze 解説

問題 | 解説まとめ

作問slackに最初に投稿した問題。
今年はこんな感じの問題にするぞという思いも込めて作りました。

解法：ペイント等でゴールのラインに縦線を引き、バケツツールで塗りつぶすと・・・

答え：ACEFGHNPQSYZ
ペイントってBFSができるんですねぇ。

おまけ：迷路を生成して遊べるprocessingのコード

Xmas Contest 2017 F問題 Tree Disassembly 解説

問題 | 解説まとめ

1~5は全探索ができる大きさのランダムケース、6~10は大きいけれどそれぞれなんらかの性質を持ったグラフとなっています。
手元で全ての答えを計算して埋め込めばいいですね。Nが全ての入力で異なるので、ケースの特定も簡単です。

1~5

1は手計算でも頑張ればできるかも。
2は各辺について色を全通り試して判定しても間に合います。
3以降はちゃんと枝刈り探索などを書かないと厳しいと思います。

次数 3 以下の点は必ず存在して，次数 2 なら単に消して答えを 2 倍にすればよくて，次数 3 ならその点まわりのつなぎ方は 3 通りなので全部試して再帰できて，これをやると 70 点

— 準急くき (@semiexp) 2017年12月24日

想定解は「graphillionで殴る」です。
グラフの列挙したりするのが得意なライブラリです。
辺に重みをつけて重みを最大化/最小化する問題なんかも解けます。
数え上げおねえさんを救うために開発された(page3)ライブラリで、はなく(page4)、ZDDを使ったすごいやつです。強い。
パスの他にもサイクルや木や森やクリークや...といろんなグラフが扱えるし、それらを組み合わせたものを列挙みたいなこともできます。結構いろいろできます。
例えば今回の問題の1~5は以下のコードで解けます。

from graphillion import GraphSet

def read():
  return map(int, raw_input().split())

n = read()[0]
edges = [tuple(read()) for i in range(2,n*2)]

GraphSet.set_universe(edges)
trees = GraphSet.trees(is_spanning=True)
comps = trees.complement()
ans = comps&trees

print(len(ans) % (10**9+7))

こういうアルゴリズム系のライブラリはpythonが結構多いのでpython書けるとだいぶいい感じです。
やってることとしては、辺をタプルで持ったリストを作って、それをグラフに登録し、全域木(trees)を列挙し、その補グラフ(comps)を列挙し、それらの積集合を取ってそのサイズを求めています。
"列挙"と言っても、全部を実際に列挙しているわけではなく、実態としては条件を満たす集合の圧縮表現を構築しているだけで、かなり速いです。
自分はまだあまり使いこなせてはいませんが、それですらかなり強力なライブラリだと思うのでオススメです。

6~10

6~10はそれぞれのグラフをビジュアライズするとどんなグラフかが見えると思います。
グラフのビジュアライズはgraphvisやjs製のそれっぽいライブラリを使うと良いでしょう。
僕はこのサイトをよく使います。（超便利、EMKさんありがとうございます）

6

K4が頂点どうしで繋がって木っぽくなっています。
この問題の性質を考えると、関節点で分離して独立に解いて掛け合わせると良いことが分かるので、K4の答え12を33乗すれば良いです。

7

幅２の管状になっていて木幅が小さいので列単位で適当なDPをすれば解けます。
実際に考えて見ると、実は状態は「片方の色が繋がっててもう一方が繋がってない」の実質１通りしかないので、単に2*6^50が答えになります。

8

これを見ても104の次数が高そうなことくらいしかわからないので、graphvisの方の画像を見た方がいいですが、サイズがデカすぎるので載せないでおきます。

代わりに、小さい版を作ってビジュアライズしました。
こんな感じで多角錐みたいになってます。
N=4から実験して見ると、12,28,60,124,252...となっていて、これは2^N-4です。
なぜこうなるかを考えてみると、周りの輪っかの辺の色を決めると、全部同じ色の時以外はスポークの辺の配色が２通り存在するので(2^(N-1)-2)*2という感じ。

9

なんか投網みたいな形です。
良く考えると輪っかサイズが10になった08.txtを10個繋げたのと同じ状況なので、(2^11-4)^10が答えです。

10

これもgraphvisの方が見やすいです。

グリッドの最後をK4で帳尻合わせた形になっています。
この問題の性質を考えると、次数２の頂点は片方が赤でもう片方が青になるだけなので、答えを２倍して取り除いても同じだということがわかります。それを隅から順番にやっていくとK4が最後に残り、(2^99)*12が答えであることがわかります。

Xmas Contest 2017 E問題 String Problem 解説

問題 | 解説まとめ

このセット随一の普通の問題です。
少し言い換えると、Sから'A'をいくつか削除し、Tから'B'をいくつか削除することによってSもTもUにすることができるような文字列Uが存在するかを判定すれば良いです。
「dp[i][j] = S[0]~S[i]とT[0]~T[i]を同じ文字列にできるか」というDPをします。
遷移は

• if (S[i] == 'A') dp[i+1][j] |= dp[i][j]
• if (T[j] == 'B') dp[i][j+1] |= dp[i][j]
• if (S[i] == T[j]) dp[i+1][j+1] |= dp[i][j]

の３つです。

さて、この問題を出した動機ですが、AKIBAを正規表現で解くと楽だとちょっと前に気づき、さらにそれが書かれたのブログがAdvent Calendarに投稿され、これをもう少し応用できないかと考えた結果こんな問題になりました。

正規表現解はこんな感じ(python)です。
やってることとしては、Sの先頭/各文字の間/末尾に"B*"を挿入し、"A"を"A?"に置換しています。
で、これがTにマッチすればYESです。
ただし、これでは部分点しか得られません。pythonの正規表現アルゴリズムでは*とかのマッチングを愚直なバックトラックでやっていて*の個数が増えると指数的に計算量が爆発してしまうためです。
これはなんとC++でも同様です。
ここで、Go言語やD言語やgrepなどを持ち出すと計算量がちゃんと入力長に対する線形時間であることが保証されているっぽいので間に合います。
※「入力長に対する線形時間」と言ってもO(|S|)ではなく、O(正規表現とかでかかる計算量*|S|)ということぽいので注意

あと、この正規表現にマッチするかを自力で判定しようと思ったら、dp[i][j] = Sのi文字目までが正規表現のj文字目までにマッチするかどうか、みたいなDPをやればO(正規表現の長さ*|S|)になりますね。
より良い方法として、NFAを作るというのがあります。（定数倍がよさそう）

Xmas Contest 2017

Xmas Contest 2017 を開催しました。
ご参加いただいたみなさま、ありがとうございました。
楽しんでいただけたなら幸いです。（そして毎年一緒に運営を手伝ってくれるじゃっぷるさんにも感謝です）
あと、アンケートに回答してくださったみなさまありがとうございました。思ったよりも感触がよく、開催したかいがあったなぁと感じました。
Fのリジャッジの件、手際が悪く申し訳ありませんでしたm(_ _)m

Xmas Contestのwriterをやらせていただいてからもう３年目になりました。
やはりこの伝統は受け継いでいきたいという思いと、また本家のXmas Contestに出たいという思いがある今日この頃です。

毎年このコンテストの準備には苦労しているのですが、プログラミングを使った問題の新しい形を探求することはなかなか楽しいですね。
今年の問題は前年よりも変わった問題を増やそうというコンセプトで作問をしてみました。

僕が担当した問題は E〜I です。
問題タイトルの頭文字がChristmasになるように適当に並べ替えると自然とこうなっていてびっくりです。
解説は問題ごとに記事として投稿していきます。

• E問題
• F問題
• G問題
• H問題
• I問題

IOI2017

IOI2017を観戦しました。

師匠が圧倒的な１位を取り、日本チーム自体も金３銀１と過去最高成績で激アツでした。
金３も１，４，５位で凄すぎる。
おめでとう＆お疲れ様！

---

本番から１時間遅れで問題を閲覧することができ、yandexにjudgeが立っていたので何問か気になった問題を解いてみました。
今年の問題は、解いていない問題も含めてなかなか面白く、また、かなり難しめのセットだったと思います。解いた問題についての解説を書いたのでブログとして貼っておきます。

• Day1 Nowrus 96.31点
  • 久々のOutputOnlyでした。とりあえずで書いてみた解法で高得点を取れたため、順位を大きく分けるというよりはタイブレイクとして機能していたのではないかと思います。ちゃんと焼きなましなどをすれば100点も可能なのかもしれません。
• Day1 Toy Train 満点
  • 一見NP困難にしか見えないんですが、仮定をおいたりして考えて行くと多項式で解くことができ、ほえーってなった。ゲーム系なんですが、なかなか独特かつシンプルなルールで面白い。
  • yosupo氏の解法もどうぞ。こうやるとたしかに典型だけで片付けられるなぁ、不思議。
• Day2 Books 満点
  • ありがちでシンプルな設定なんですが、なかなかにadhocで面白かった。それっぽいことをすれば50点来てしまうのですが、そこからは適当にやるだけでは満点は取れません。冷静にじっくり考察する力が試される良問。解法も面白いので結構好き。