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
幅2の管状になっていて木幅が小さいので列単位で適当なDPをすれば解けます。
実際に考えて見ると、実は状態は「片方の色が繋がっててもう一方が繋がってない」の実質1通りしかないので、単に2*6^50が答えになります。
8
これを見ても104の次数が高そうなことくらいしかわからないので、graphvisの方の画像を見た方がいいですが、サイズがデカすぎるので載せないでおきます。
代わりに、小さい版を作ってビジュアライズしました。
こんな感じで多角錐みたいになってます。
N=4から実験して見ると、12,28,60,124,252...となっていて、これは2^N-4です。
なぜこうなるかを考えてみると、周りの輪っかの辺の色を決めると、全部同じ色の時以外はスポークの辺の配色が2通り存在するので(2^(N-1)-2)*2という感じ。
9
なんか投網みたいな形です。
良く考えると輪っかサイズが10になった08.txtを10個繋げたのと同じ状況なので、(2^11-4)^10が答えです。
10
これもgraphvisの方が見やすいです。
グリッドの最後をK4で帳尻合わせた形になっています。
この問題の性質を考えると、次数2の頂点は片方が赤でもう片方が青になるだけなので、答えを2倍して取り除いても同じだということがわかります。それを隅から順番にやっていくと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]
の3つです。
さて、この問題を出した動機ですが、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をやらせていただいてからもう3年目になりました。
やはりこの伝統は受け継いでいきたいという思いと、また本家のXmas Contestに出たいという思いがある今日この頃です。
毎年このコンテストの準備には苦労しているのですが、プログラミングを使った問題の新しい形を探求することはなかなか楽しいですね。
今年の問題は前年よりも変わった問題を増やそうというコンセプトで作問をしてみました。
僕が担当した問題は E〜I です。
問題タイトルの頭文字がChristmasになるように適当に並べ替えると自然とこうなっていてびっくりです。
解説は問題ごとに記事として投稿していきます。
IOI2017
IOI2017を観戦しました。
師匠が圧倒的な1位を取り、日本チーム自体も金3銀1と過去最高成績で激アツでした。
金3も1,4,5位で凄すぎる。
おめでとう&お疲れ様!
本番から1時間遅れで問題を閲覧することができ、yandexにjudgeが立っていたので何問か気になった問題を解いてみました。
今年の問題は、解いていない問題も含めてなかなか面白く、また、かなり難しめのセットだったと思います。解いた問題についての解説を書いたのでブログとして貼っておきます。
- Day1 Nowrus 96.31点
- 久々のOutputOnlyでした。とりあえずで書いてみた解法で高得点を取れたため、順位を大きく分けるというよりはタイブレイクとして機能していたのではないかと思います。ちゃんと焼きなましなどをすれば100点も可能なのかもしれません。
- Day1 Toy Train 満点
- 一見NP困難にしか見えないんですが、仮定をおいたりして考えて行くと多項式で解くことができ、ほえーってなった。ゲーム系なんですが、なかなか独特かつシンプルなルールで面白い。
- yosupo氏の解法もどうぞ。こうやるとたしかに典型だけで片付けられるなぁ、不思議。
- Day2 Books 満点
- ありがちでシンプルな設定なんですが、なかなかにadhocで面白かった。それっぽいことをすれば50点来てしまうのですが、そこからは適当にやるだけでは満点は取れません。冷静にじっくり考察する力が試される良問。解法も面白いので結構好き。
KMPのK
上の記事では記事中の注釈の通りMPを紹介したので、KMPとは何かを大雑把に解説しておきます。
KMPは、上の記事で紹介したMP(Morris-Pratt)にKnuthパワーが加わったものです。
さらなる考察がされて、文字列検索の効率が向上した感じです。
計算量的な面でも、全体計算量は線形のままですが、後述するような嬉しい点があります。
復習+α
まずはMPの復習からです。
上の記事で求めている A は 最長border と呼ばれるものらしいです。
文字列 S "aabaabaa" の A(border) は -1,0,1,0,1,2,3,4,5 となります。
この文字列の末尾にもう1文字加えたとき、A[9] はどう計算すればいいでしょうか?
図の赤い矢印は i→A[i] を結んでいます。
A[9] を求めるステップは以下のとおりです。
- 赤い矢印を辿って、次の文字を見る。
- ? と一致していたらそこの次の位置が A[9] になる。
- 異なるなら、また赤い矢印を辿って・・・を続ける。
? が a,b,c のときについてそれぞれ実際にシミュレートしてみるとイメージが湧きやすいかもしれません。
さて、ここまでがMPですが、MPの計算量は均し計算量でO(1)です。
つまり、1ステップの計算量は最悪でO(N)になることもあります。
例えば、aaa...aaab について計算する時、b を追加したときには赤い矢印を a の個数回辿らなければなりません。
KMP
下図のような青い矢印を考えます。
この青い矢印は「"次の文字"が異なるまで赤矢印を辿った場所」に張られたものです。
実は先程の A[9] を求めるステップでは、青矢印を赤矢印の代わりに使っても正しい答えが求まります。
なぜなら、5→2 の矢印をたどるということは ? が b ではなかったということで、それなら 2 を試す必要はなくスキップしても同じで、同様に 1→0 の矢印もスキップして良いからです。
実はこれで1ステップの計算量をO(log N)で抑えることができます。
で、これがKMPのKです。
計算量を解析してみます。間違っていたので修正しました(2022-09-15)
ある場所から赤矢印を辿るときの「"次の文字"が異なる赤矢印」(特別な赤矢印と呼ぶことにする)の個数を見積もればよいです。
赤矢印を辿って α → β → γ と遷移し、2つ目の矢印が特別な赤矢印であるとき、
が成り立つことを示します。 と仮定すると、
- β は α のprefixかつsuffix
- γ は β のprefixかつsuffixなので α のsuffixでもある
- α の |β|+1 文字目を x、|γ|+1 文字目を y とすると x ≠ y (∵2つ目の矢印は特別な赤矢印)
- γ の d+1 文字目は x、β の d+1 文字目は y であり、γ が β のprefixであることに矛盾する ■
特別な赤矢印を辿る回数が k 回になるような最短の文字列の長さを とすると、
(上の状況で α→β は特別な赤矢印とは限らないが、βの前に辿った最後の特別な赤矢印の直前の文字列の長さは |α| 以上)
L を帰納的に求めるとfibonacci数的になっているため、特別な赤矢印を辿る回数は O(log N) 回であることが示せる。ちなみに log の底は黄金比 φ = で、最悪ケースは fibonacci word。
応用問題
xmas contest 2015 D - Destroy the Duplicated Poem
問題概要を一口で説明すると「Trie木が与えられるので各頂点に対して赤矢印を求めよ」です。
普通にMPをやろうとすると、aaa...aaときてそのあとにbやらcやらと枝分かれしまくるケースとかで計算量が2乗に爆発してしまいます。
そこで、KMPを使えば遷移が常にO(log N)で抑えられてしまいます。やったー。
ソースコード
木上でやるとなると少し実装がトリッキーになるので頑張って混乱しないように整理して実装しましょう。
ちなみに想定解は違う解法だったので、期せずしてKMPの良い例題を作ってしまったらしい。
丸くなってしまったtwitterアイコンを戻す方法
なんか、twitterとtweetdeckのアイコンが突然丸くなった。
四角を想定して作られたアイコンの四隅が切り取られるのはアレなので、CSSをいじって直した。
twitter社はなにを思ってこんなことをしてしまったんだろう・・・?
直し方
まず、CSSをカスタマイズできるブラウザ拡張を入れます。
.ProfileAvatar, .ProfileAvatar-image, .avatar, .js-action-profile-avatar { border-radius: 5% !important; }
角丸の度合いを変えたかったら5%のところをいじって下さい。
2023-06-20:これのおかげで、アイコンの四隅に隠しイラストを仕込んだ人に10分で気づけました。
Google Code Jam 2017 Round 3
通過しました。
初のGCJ決勝進出です。
GCJは現時点での第一目標だったのでとても嬉しい。
次はTCOかぁ、きっつい。
今回はどれも解法がすらすらと分かったので、GCJと相性が良いのかもしれない。
(けど謎の問題(sortアルゴリズムを推測せよとか、乱択とか)とか強実装とかが出てくると多分苦手)
戦略的にも最適に動けていたので、かなり理想的なパフォーマンスだった。
流れとしては、
- SubmissionsとTop Scoresはちらちら動いて邪魔だし、焦りの原因になるので閉じておいて必要な時だけ見る
- とりあえずAは解いておく
- 逆向きに探索できるなぁとなる
- 状態数を減らしたい
- 前の状態が存在する条件=合計がL以下
- そういう状態は18C9しかなくて余裕
- 前の状態が存在しないのは探索せずに数式で計算する
- L!から種類iがCi個ある時にCi!で割っていけば良くて、解けた
- small時点で24位だった
- largeはとりあえず保留するスタイル
- 最大ケースが明らかに100000000で、これが爆速だったので通るだろと思う
- とりあえずBも読んで少し考える
- サンプルを見ながらサイクルにそって加算する感じだと思う
- なんで負が出てくるのという違和感はあった
- 他のサンプルを見るとサイクル(有向)がないのにOKな例がある
- ある辺にx流すのと、逆辺に-xを流すのは同じだという考察
- 無向グラフで考えた方が良さそう
- サイクル基底っぽい
- DFS木を書くと分かった
- 後退辺に1を割り当てて、対応する木の区間(?)にも+1してやればいい
- 非連結なケースを忘れたのと修正ミスで2WA
- 出力をもうちょっとちゃんと確認すれば少なくとも2つ目は防げたし、これが今回唯一の反省点
- largeは保留
- サンプルを見ながらサイクルにそって加算する感じだと思う
- Bをさらっと解けて有利になったという実感があったので順位表を見てFinishまでの道のりを確認する
- D smallが簡単らしい
- C smallもまぁまぁ解かれてる
- とりあえずDを読んでlargeは捨てるのが正しそうだと思いつつsmallを解く
- FAが11分台だったので実装も大したことないはずと考える
- 小さいやつから伝播させていく感じの貪欲でいけそうとなる
- 小さい数から見ていけば下限制約は保証できるので、うん正しそうという感じ
- 通る、調子が良い
- C-smallをやる前にlargeたちを送っておくかを考える
- C-smallは必要そうな気配を感じるし、少なくともC問題文読んでからにするかとなる
- もしlarge提出でトラブルが起きたら焦ってCの問題文長めだしテンパって読めなくなるのが想像できるし
- C-smallやるだけ感があったのでやる、通る
- この時点で通過をほぼ確信したので、largeたちをドキドキしながら出す。
- のんびりC-largeでも考えるかーとなる(実際にはこれが解けないと通過できなかった)
- お祈りフェイズ。Dはさすがに無理だし、暇
- ペナルティ差で準急に微妙に負けていた(◞‸◟)
- 仕方ないからD-largeを綺麗に実装できないか考える
- ボロノイ図みたいになるのはすぐ分かった
- bounderyが8種類の直線で表せてそのandを取った領域内の値を頑張って計算したい
- 始点から距離を1ずつ増やしていって距離が同じマスたちを一括で足す感じをイメージする
- bounderyに引っかかると、増えなくなる方向が出てくる
- 右下、右上、左下、左上と真上、真下、真右、真左の8種類の領域に分けてみると、bounderyにぶつかった時に増えなくなる分が割と簡単に求まることが分かる
- 有限時間で実装できる気にはなったから実装を始めたけどさすがに間に合わない
- (追記)後で気づきましたが、領域凸にならない場合あるやん!(sample1とか)これは実装不能ですね。
- 終了、全部通って12位通過、めっちゃ嬉しい
GCJはいかに冷静に解くべき問題を取捨選択するかが重要で、これさえ間違えなければ解けるべき問題さえ解ければ割と通れる。
昔の自分だったら絶対やってないんですが、素早く書けそうなC/Dのsmallをさっさと回収するとだいぶ心に余裕が生まれたりもするので重要な気がする。
ストレステストにも使えるし、ベースの解法の確認ができることもあるし、無駄ってことはないと思うし。
GCJの戦略とかはりんごさんのツイートを見ると参考になると思います。
例えばこれとか。
GCJ 40 分の法則というのがあって、40 分で解かれているものを足すと通貨の目安というのがあるんですが
— rng_58 (@rng_58) 2017年6月10日
おまけ:コンテスト前の準備
昼ごはんは慎で贅沢に天ざるうどんを食べた。
くっそうまかった。やっぱりこの店最高すぎる。(ちょっと遠いけど)(大体並んでるけど)
2014の問題を解いてたら眠くなったので仮眠を取った。
晩飯はがっつり食べずに、プリンとメロンパンと高千穂コーヒー牛乳で済ます。
念のため栄養ドリンクを買ったけど飲まなかった。
コンテスト前にプリンを食べるのはおすすめです。