Xmas Contest 2016 講評

この記事は Competitive Programming Advent Calendar 2016 - Adventar の 25 日目の記事です。ワオ、最終日！

アドベントカレンダーではよくネタっぽい記事を書いていたし、実際アドベントカレンダーのページでの参加メッセージもふざけていたし、今年もふざけるんだろ？と思いきや、まともにコンテストの講評を書きます！と思ってたんだけどあとから読むとなんかふざけてるんだよなぁ

クリスマス当日なので Xmas Contest 2016 の講評を書きたいと思います。解説ではありませんが、問題によっては解法のネタバレを含むのでご注意ください。

はじめに

かなりの高難度セットでしたが、大変多くの方にご参加頂きました。参加された皆様、ありがとうございます＆お疲れ様でした。（主に準備が直前すぎたため）不備もありましたが、問題を楽しんでいただけたならば幸いです。

どの問題も様々な側面から面白いと自信をもっておすすめできる問題ですので、高難度ではありますが本番中では解けなかった問題にも気が向いたら是非挑戦してみてください。

ちなみにこの高難度セットですが、本来ここまで難しくなる予定ではなく、運営スタッフが気づいたらいつの間にかこんなセットになっていました (幾つかの問題については各問講評でその経緯について触れられると思います)。

総評

昼・夜・深夜の部すべてを合わせた上位チーム (個人参加者) は以下の通りです。得点が同じチームは最終提出の早い順です。

名前	A	B	C	D	E	F	G	H	I	J	Total
cookie☆sugimとsigmaのクッキーYosupo	100	70	100	100	100	100	0	-	100	50	720
rco-xmas2016	100	89	-	100	100	-	0	-	100	100	589
Adjumani	100	89	-	100	100	0	-	-	100	100	589
湘南のサワヤカBoys	90	70	0	100	100	100	-	-	100	0	560
semiexp feat. GUMI	100	70	-	100	100	0	-	-	100	50	520
anta	100	-	-	100	100	0	100	100	-	-	500
omeometo	100	82	0	-	100	100	-	-	100	-	482
kawatea	100	24	-	100	100	-	-	-	-	100	424
yutaka3141	100	35	-	-	100	-	-	0	100	50	385
古寺いろはチーム	100	17	-	0	100	100	-	-	15	50	382

優勝は 720 点を獲得したチーム「cookie☆sugimとsigmaのクッキーYosupo」となりました。おめでとうございます！唯一6問で100点満点をとったチームであり、2位以下に 100 点以上の差をつけての優勝でした。

次に、正解者のいなかった問題 B で高得点を獲得した方々、正解者の少なかった問題 C, G, H を正解した方々を紹介します。

問題	名前	得点
B	square869 (E869120+square1001)	96
B	037_yosss	89
B	rco-xmas2016	89
B	Adjumani	89
C	aaaaajack	100
C	cookie☆sugimとsigmaのクッキーYosupo	100
G	anta	100
H	anta	100
H	yukim	100

難問の AC や高得点、おめでとうございます。B 問題でのチーム「square869 (E869120+square1001)」は単独最高得点でした。また 037_yosss さんは、コンテスト時間中には間に合いませんでしたが、終了後に 100 点の解法を提出されていました。

各問題ごとの得点分布は以下のようになりました (提出した人のみの分布です)。A, B 問題は部分点が一定の点数ではありませんがここではまとめて表示し、以下の各問講評において詳細な分布を掲載します。

各問題の講評

あとから読むと、最初の方は真面目に講評してるんだけどだんだんコンテスト準備の裏側みたいな話になってますね…………まぁそれもアリでしょ！（投げやり）

なんか無駄に長いし Xmas Contest 2016 の有益な material というよりは、ただの開催記ですね。まぁアドベントカレンダーのネタとして自分語りが流行っているらしいのでこれもそういうことにしておきましょうか！

A: Array Sum (原案: snuke)

12月20日頃にリアクティブ枠として提案された問題です。非常にシンプルな問題設定ながら奥が深くて面白い問題です。

詳細な得点分布は以下のようになっています。N の 2 進数表記で立っているビットに対応するクエリを飛ばしていく、最大質問回数 16 回 (56 点) の解法から、想定の 9 回 (100 点) の解法まで、どの点数もとっている人がいるのが興味深いです。この問題への取り組み方法や細かい実装の工夫などの多様性が感じられます。

A 問題の First AC は anta さん (15分38秒) でした。

B: Binary Tree (原案: snuke)

コンテスト準備 slack 立ち上げ時から提案されていた問題です。想定解はなんと 64×64 のグリッドで 1 点を余らせるだけという驚きの最適解になっています。

詳細な得点分布は以下のようになっています。こちらは A 問題より点数が多様で棒グラフだと少し分かりづらいぐらいですね。

この問題については、snuke がおそらく最適解や様々な参加者の出力した解をビジュアライズして眺める記事を作ってくれると思うのでそれに期待しておきます。

100 点をとられた方はおられませんでしたが、square869 (E869120+square1001) さんが単独最高点の 96 点 (209分16秒) を獲得しています。

C: Cutting Swiss Roll (原案: japlj)

12月6日ぐらいに僕が提案しました。昨年の Xmas Contest 2015 では運営スタッフだったのですが一問も原案を出せず申し訳なかったということもあり、今年は原案 0 問を回避しようと張り切った結果作られた問題です。

提案時は整数列が与えられて、問題文にあるように切り分けて片方捨てることを繰り返すゲームを行って、残る整数の最大値を求めるという問題でした。つまり、リアクティブ要素はなく、単に X の値を求めるだけの問題でした。

要はこの問題、提案時は完全に普通の問題で、クリスマスコンテストという一風変わった問題を目指すコンテストの目的に全く沿っていませんでした。僕が原案 0 問を回避したいという一心で勢いだけでクリスマスコンテストに投げてしまったものです。

……という話は置いておいて、X を求めるだけならまともに考えるだけでなく、いろんなケースで実験して法則を探るだけでわりと簡単に解けます。というわけでこの問題はコンテストの中では比較的取り組みやすい枠……だったのですが、12月22日夕方

お前！！！コンテスト全体の難易度バランスも考えろよ！！！！テンション激アゲじゃあないんだよ！！！

というわけできちんと勝敗の法則を考察し、証明を通して実際の戦略を構築してそれを実装する問題に変貌してしまいました。気づいたら高難度セットになってたとか言いましたが完全にこの japlj とかいうやつが愚かですね。これを棚に上げて「気づいたら難しくなってた」とかよく言えたもんだと思います。

そんな経緯で出来た AC 2人の難問でしたが、First AC は aaaaajack さん (146分08秒) でした。

D: Distributed Sorting (原案: japlj)

12月14日ぐらいに僕が提案しました。この時点でパッと見た感じそこまで楽そうなのが無かった (C もこの時点では比較的楽とはいえ、実験して法則を探るという想定で多少は時間を要しそうだった) ので、チョチョイとやってスッと解ける感じの簡単枠を作ろうということで提案しました。

しかし現実は、高々 2 回の操作でソート可能というところに気づくのが実はかなり難しく、多くの人が log N 回ほどの操作を出力するプログラムを提出してしまい、とてもじゃないが簡単枠どころではない状態になってしまいました。

下に示すのは提案時の様子です。

これはたまたま writer も tester も操作が 2 回というところにすぐ気づいてしまい簡単枠という判断をしてしまったということで、もうしょうがないと思います（開き直り）。さっきの C の難化みたいなのは「確かに面白いけどちょっと冷静になろ？」と落ち着けば防げたかもしれませんが、両者ともにたまたまサクッと解けて難易度見積もりを大失敗してしまったみたいなのはなかなか防ぎようがないと思います。

強いて対策があるならば、もう少し多くの tester に見て難易度を多角的に判断してもらうとか……つまり、そこのあなた！来年のクリスマスコンテスト (やるかどうか未定ですが、やるとして) のスタッフになりませんか？？？是非、普通のコンテストで出しづらいようなクリスマスコンテスト向きの問題を溜めてスタッフをやりましょう！！！！

いや勧誘でごまかそうとしてるけど、そもそもさ、難易度見積もりとか以前にこれってそこまで普通のコンテストで出しづらい感じじゃなくない？難易度見積もりは仕方ないにしても、これをクリスマスコンテストに提案したことがまず問題なんじゃないの？？という正論につきましては、えー、そのですね、ここでこうやって想定正論みたいな感じで挙げて予防線を張っておくと同時に、はい、その、回答の方は差し控えたいと考えております。

First AC は anta さん (35分48秒) でした。anta さん、ここで既に 2 問目の First AC ですね、すごい。

E: Examination, Estimation (原案: japlj)

どうだッ！難易度もそこそこ、取り組みやすく、そして普通のコンテストに出すわけにはなかなかいかない！完璧なクリスマスコンテスト向け問題だろう！文句があるか？？何でも言ってみろッ！何も答えませんけど。

という問題ですね。12月7日頃に僕が提案したようです。各うなぎについて、他のうなぎとの回答の一致率などをもとにうなぎのタイプ分けを推測し、それをもとに正答を最尤推定するという、そこそこまともっぽい想定解法で用意しました。が、厳密な AC 率の保証などはできていないので、誰か確率統計とかこの辺の計算が得意な人、お願いします。とか、コンテストが終わった後で虚空にぶん投げられる、やっぱりクリスマスコンテストは最高だなァ〜？こりゃあ来年のスタッフをやるしかないぜ！！

確率計算がちゃんと出来てないのはまぁ僕が弱いということで申し訳ないんですが、クリスマスコンテストの問題としてはかなりいい感じに仕上がったと思います。

First AC は くコ:彡 さん (14分57秒) でした。早すぎてホントにびっくりしてました。

F: Fifty-Fifty? (原案: snuke)

12月17日頃に「ちょい簡単め」として提案されました。実際解法を聞くと見掛け倒し問題っぽい感じがあって、僕が tester として解いたときも超面白かったけど、たしかに見掛け倒しだな〜と思っていました。

実際、偶奇だけが問題だと実は回文の数を数えるだけだよ〜 (K=1の場合を除く) みたいなこと言われたら、見掛け倒しだな〜って感じると思います。見掛け倒しであること自体は間違ってないと思うんです。でも、重要なこととして、その見かけを剥ぎ取って本質を顕にさせること自体は、全然簡単じゃないんですよね……。

偶奇を求めればよいのだから、K 次回文は実はうまいことペアが作れて結構打ち消し合うのではないか？という取っ掛かりから始めて、どういうペアが作れるかを考えていって、確かに A が K 次回文なら reverse(A) も K 次回文だな〜というところまで行って……というプロセスは、見掛け倒しの見かけをぶっ倒してるわけなんですけど、コレ自体は結構骨太な考察なんですよね。見かけを剥いだら単純じゃ〜ん、ハイ簡単！とうっかり思ってしまうと危ないということですね。

と言っておいてなんですが、僕がこれを解いたのはコンテスト当日の AM 3 時とかで、そもそも難易度を判定する脳の働きが停止していて何も考えてませんでした。ちゃんちゃん。

First AC は cookie☆sugimとsigmaのクッキーYosupo さん (131分32秒) でした。

G: Guide Passengers (原案: snuke)

これも確か立ち上げ当初から提案されていました。想定解法がちょっと一発ネタっぽいからクリスマスコンテストに持ってきた、という感じで、僕は「へぇ〜（やっべ全然解き方わかんねえなあ一発ネタってなんやそれ論文系か？）」と思ってました。

これも僕は怠慢で結局コンテスト当日の AM 5 時とかに解いていて、それまで全然難易度とか分かってなかったんですが、全然難易度のわからない問題があるような状態で！何も考えずに！！コンテスト全体のバランスを無視して！！！問題を追加したりしてはいけません！！！！！ホントごめんなさい。

結局わからなくて snuke にヒントもらって「N, M が 100 ぐらいならどう解きますか？」と言われて、それぐらいならフロー流すやろ〜とすぐ思いついて、「では、追い越しなしの制約とは……？」と言われて「あっ planar……」ってすぐなって、N, M 小さいときを考えて解くとか基本中の基本っぽい考察方針なのにすっかり忘れてたなぁ〜、でもそれに忠実にやっていくとこうもスッと解法に至るのか〜とか思ってました。ヒントもらったからスッと解法に至っただけなのに何を言っているんだこの人は。

snuke も後悔してましたが、確かにこういう道筋であることを考えると、フローの解法に部分点をあげるとよかったかもしれません。実際、コンテスト中にフローを流す解法も送られてきていたと思います。

AM 5 時に実装するのはとても辛かったです。

First AC (しかも唯一 AC) は anta さん (107分09秒) でした。anta さん、First AC も多いし WA も全然出してなくてやばすぎる……。

H: High-powered Illuminations (原案: snuke)

これも立ち上げ当初から提案されていたやつです。木！ということで catupper が担当する！ということで僕は相変わらずノータッチで全然難易度とか分かってなくて、とにかく全然難易度のわからない問題があるような状態で！何も考えずに！！コンテスト全体のバランスを無視して！！！問題を追加したりしてはいけません！！！！！いいですね？

コンテスト前日（あれ？当日の深夜だったか）にデータとかが上がってきて、いいじゃ〜んって感じだったんですが、もともとこの問題の木は辺に重みなしで、J 問題を作るにあたってこの H の入力は N, K と来たあと木の辺 (a_i, b_i) が与えられる〜という仮定でやっており、ここでまず問題が発生しました。最初の問題では頂点 i の親は a_i という形式で入力が与えられることになっていたのです！やべぇ！

いやでもこれは簡単な作業で (a_i, b_i) の形式に直せるし、実は大した問題じゃなくて本当によかったですね……。

と思いきや、問題設定が実は上司部下の関係の木構造でした。これつまり、a_i は b_i の直属の部下である、みたいな形式で与えられるわけで、a_i と b_i を結ぶ辺があるという形式より入力の制約が厳しくなるんですよね。実は大した問題でした……ので、やむを得ず問題設定を全面書き直しすることにしました。このときの時刻、開催当日朝8時！！！！

というわけで問題文を書き換え終えて一件落着。間に合って本当によかったですね……。

と思いきや、TLE 解が TLE しませんでした。ということで snuke が超頑張って追加のデータづくりを行い、僕は完全に一仕事終えた気分で（いやぁ本当に疲れた……snuke頑張ってくれ〜〜）とか思ってました。

あとはsnukeが頑張ってくれれば、とりあえず僕の仕事は終わり。9時が近いがようやく寝られる。本当によかったですね……。

と思いきや、辺に重みがないと TLE 解をグッと遅くするのはかなり大変ということになりました。

でも辺に重みつけるって、問題文ちょっと変えるだけでしょ、チョチョイのチョイやで、本当によかったですね……。

と思いきや、H 問題の入力フォーマットが決定的に変わるので、J 問題が完全に変わってしまいました。というわけで J 問題へ続く (このとき開催当日朝 8時 50分)。

First AC は anta さん (172分31秒) でした。anta さんが凄すぎてもうコメントのネタが尽きた。

I: ISOLT (原案: snuke)

これも初期提案問題です。そして珍しく僕はこれを比較的余裕をもって解いていました。

問題としてはテトロミノの敷き詰めで結構見た目ギョッとするんですが、問題設定がいかにも怪しい (この怪しさがクリスマス風ですよね)。まず T は市松模様の塗り分けで簡単に分かるんだけど〜、というところから他のテトロミノの見分け方も考えていくと、様々な方法があるかと思いますが、最終的にマス目を適当に分類して数えて場合分け！みたいな感じで全部判定できて、おぉ〜ってなります。

いやぁ、この問題は優等生ですね……テストケースを作るのが超大変ということを除けば。ということで、この問題は snuke がとても頑張ってテストケースを作っていました (開催当日朝6時半)。感謝。

First AC は semiexp feat. GUMI さん (28分04秒) でした。これまたかなり早いですね！

J: Just a Single Testcase (原案: japlj)

クリスマスの最終問は特に変わった問題！ということで例年のクリスマスコンテスト最終問の出来栄えにプレッシャーを感じつつも色々考えて作りました。

最初は今の設定のほかに、接頭辞をとらずにピッタリ入力データとして使える場合にできるだけ多くの問題で valid な整数列、みたいなのもありました。が、どうしても小さい値をチマチマ配置するだけで、まぁパズル的に面白い点も結構あるのですが、複雑な制約を満たすものを選ぶのは作業要素も強く、これ単体での出題はどうか……？という感じでした。

そこで snuke が D, F, H に問題を絞るかわりに、できるだけ大きい (辞書順で) ものを考えるとどうなるか？と発案してくれたことで、現在の t=2 の問題ができました。こちらは複雑な制約 (特に問題 G) が減ったことと、辞書順最大という制約がついたことで、条件を満たすよう貪欲に当てはめていくというまたちょっと違ったパズル風問題になりました。

そう、最初は、貪欲当てはめを考えていくパズル風問題だったのです……コンテスト開催当日朝 9 時に H の入力形式が変更されるまでは……。

当時僕はさすがに疲労困憊で、ハイハイ変わったけどこれも適当に当てはめていけばいいよね〜と言ってデータを作り直しました。そして 9時半には新たな J のデータ作成を終え、10 時には眠りについたのです……。

言うまでもなく言うまでもなさすぎることですが、こんな状態で J みたいな問題が解けるわけがないです。解けていませんでした。夜の部のコンテスト中のリジャッジとなってしまいました、申し訳ありませんでした。皆様は絶対にコンテスト開催5時間前（徹夜明け状態）に問題が変更されるようなことのないようにしましょう。クリスマスコンテストも来年は絶対余裕をもって準備しましょう……本当に身をもって体感しました……。

First AC は rco-xmas2016 さん (131分24秒) でした。