Xmas Contest 2017 H問題 Ango 解説

問題 | 解説まとめ

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

部分点１

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

部分点２

xは乱数でもおそらく被らないと思いますが、Nが大きいのでクエリへの応答が困難です。
ここで、(a^2+b^2)と(a+b)さえ分かっていれば a も b も求まるということを唐突に思いつきます。（そもそも僕が数日悩んだのち唐突に思いついたため、こうとしか解説できず）
（S=(a^2+b^2), T=(a+b)として、ab=(T^2-S)/2が求まり、|x-y|=sqrt(S-2ab)が求まり、T+(a-b),T-(a-b)として a, b が求まります）
これを実現するにはGETA=500000などとしてx_i = i^2*GETA+iなどとしておけば、S=sum/GETA, T=sum\%GETAとして S, T が求められます。

部分点３

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

Xmas Contest 2017 G問題 Maze 解説

問題 | 解説まとめ

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

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

f:id:snuke:20171226174325p:plain

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

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

Xmas Contest 2017 F問題 Tree Disassembly 解説

問題 | 解説まとめ

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

1~5

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

想定解は「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

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

7

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

8

f:id:snuke:20171226145433p:plain
これを見ても104の次数が高そうなことくらいしかわからないので、graphvisの方の画像を見た方がいいですが、サイズがデカすぎるので載せないでおきます。
f:id:snuke:20171226145439p:plain
代わりに、小さい版を作ってビジュアライズしました。
こんな感じで多角錐みたいになってます。
N=4から実験して見ると、12,28,60,124,252...となっていて、これは2^N-4です。
なぜこうなるかを考えてみると、周りの輪っかの辺の色を決めると、全部同じ色の時以外はスポークの辺の配色が２通り存在するので(2^(N-1)-2)*2という感じ。
f:id:snuke:20171226153239p:plain

9

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

10

f:id:snuke:20171226155051p:plain
これもgraphvisの方が見やすいです。
f:id:snuke:20171226155049p:plain
グリッドの最後を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

競プロ programming

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

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

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

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

IOI2017

JOI 競プロ

IOI2017を観戦しました。

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


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

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

KMPのK

Algorithm 競プロ programming

snuke.hatenablog.com

上の記事では記事中の注釈の通りMPを紹介したので、KMPとは何かを大雑把に解説しておきます。
KMPは、上の記事で紹介したMP（Morris-Pratt）にKnuthパワーが加わったものです。
さらなる考察がされて、文字列検索の効率が向上した感じです。
計算量的な面でも、全体計算量は線形のままですが、後述するような嬉しい点があります。

復習+α

まずはMPの復習からです。
上の記事で求めている A は 最長border と呼ばれるものらしいです。
文字列 S "aabaabaa" の A(border) は -1,0,1,0,1,2,3,4,5 となります。
この文字列の末尾にもう１文字加えたとき、A[9] はどう計算すればいいでしょうか？

図の赤い矢印は i→A[i] を結んでいます。
A[9] を求めるステップは以下のとおりです。

  1. 赤い矢印を辿って、次の文字を見る。
  2. ? と一致していたらそこの次の位置が A[9] になる。
  3. 異なるなら、また赤い矢印を辿って・・・を続ける。

? が a,b,c のときについてそれぞれ実際にシミュレートしてみるとイメージが湧きやすいかもしれません。

さて、ここまでがMPですが、MPの計算量は均し計算量でO(1)です。
つまり、１ステップの計算量は最悪でO(N)になることもあります。
例えば、aaa...aaab について計算する時、b を追加したときには赤い矢印を a の個数回辿らなければなりません。

KMP

下図のような青い矢印を考えます。
この青い矢印は「"次の文字"が異なるまで赤矢印を辿った場所」に張られたものです。

実は先程の A[9] を求めるステップでは、青矢印を赤矢印の代わりに使っても正しい答えが求まります。
なぜなら、5→2 の矢印をたどるということは ? が b ではなかったということで、それなら 2 を試す必要はなくスキップしても同じで、同様に 1→0 の矢印もスキップして良いからです。

実はこれで１ステップの計算量をO(log N)で抑えることができます。
で、これがKMPのKです。
計算量を解析してみます。間違っていたので修正しました（2022-09-15）

ある場所から赤矢印を辿るときの「"次の文字"が異なる赤矢印」（特別な赤矢印と呼ぶことにする）の個数を見積もればよいです。

赤矢印を辿って α → β → γ と遷移し、２つ目の矢印が特別な赤矢印であるとき、

  • |α| \gt |β|+|γ|

が成り立つことを示します。 0 \leq |β|+|γ|-|α| (= d) と仮定すると、

  • β は α のprefixかつsuffix
  • γ は β のprefixかつsuffixなので α のsuffixでもある
  • α の |β|+1 文字目を x、|γ|+1 文字目を y とすると x ≠ y (∵２つ目の矢印は特別な赤矢印)
  • γ の d+1 文字目は x、β の d+1 文字目は y であり、γ が β のprefixであることに矛盾する ■

特別な赤矢印を辿る回数が k 回になるような最短の文字列の長さを L_k とすると、

  • L_k \gt L_{k-1}+L_{k-2}

（上の状況で α→β は特別な赤矢印とは限らないが、βの前に辿った最後の特別な赤矢印の直前の文字列の長さは |α| 以上）
L を帰納的に求めるとfibonacci数的になっているため、特別な赤矢印を辿る回数は O(log N) 回であることが示せる。ちなみに log の底は黄金比 φ = \frac {1+{\sqrt {5}}}{2}で、最悪ケースは fibonacci word。

実装等はこの記事を参考にするといいでしょう。ここも良さそう。

応用問題

xmas contest 2015 D - Destroy the Duplicated Poem
問題概要を一口で説明すると「Trie木が与えられるので各頂点に対して赤矢印を求めよ」です。
普通にMPをやろうとすると、aaa...aaときてそのあとにbやらcやらと枝分かれしまくるケースとかで計算量が２乗に爆発してしまいます。
そこで、KMPを使えば遷移が常にO(log N)で抑えられてしまいます。やったー。
ソースコード
木上でやるとなると少し実装がトリッキーになるので頑張って混乱しないように整理して実装しましょう。
ちなみに想定解は違う解法だったので、期せずしてKMPの良い例題を作ってしまったらしい。