Xmas Contest 2017 C 問題 Revenge of Kurousa 解説
Xmas Contest 2017 の C 問題「Revenge of Kurousa」の解説です。
問題概要
a〜z の 26 個の 8bit 整数型の変数がある。はじめ a に入力の値が入っており、b〜z は 0 である。できる操作は
- ビットごとの論理演算: 16 種類ある論理演算のうち好きなものを選び、ビットごとの論理演算を行える（実質 Z = X NAND Y ができるのと同じ）。
- 加算
の計 17 種類。この操作だけを使って a の値をインクリメントする（255 は 0 にする）ようなプログラム（操作の列）を書け。
加算を使う回数が最小に抑えられていれば 100 点、最小の2倍以下に抑えられていれば 30 点が得られる。
解説
最初にネタバレをすると、必要な加算の最小回数は 1 回です。よって、30 点をとるためには 2 回の加算でインクリメントする必要があります。
部分点解法（加算2回）
最初に 1 を作って、それを a に加算することを考えます。よって、1 を加算 1 回で作れれば十分です。
1 を作るには、たとえば以下のようにします。
- 11111111 を作る（b = b 1111 b など）
- 11111110 を作る（c = b + b）
- 00000001 を作る（d = b 0110 c、つまり d = b xor c）
満点解法（加算1回）
以下では整数は全て mod 256 で考えます。要は 255 （2進数で 11111111） のことを -1 とか書きます。
まず、ビットごとの論理演算だけで入力値 A と 0 だけから作れる数はほとんどありません。具体的には以下の 4 種類しか作れません。
- 0
- A
- -1 （b = b 1111 b などとして作る)
- -A-1 （255-A と同じ、要は not A）
なので、ここで 1 回加算を行う必要があります。0 と何かを足しても意味がなく、A + (-A-1) = -1 はすでに -1 が作れる以上意味がないので、加算した結果として意味があるのは
- A-1
- -A-2
のいずれかです。
ここで not X が 255 - X = -X - 1 だったことを思い出せば
- not (-A-2) = 255 - (-A-2) = A + 1
となりインクリメントができました。
Xmas Contest 2017 B 問題 Hello, Xmas Contest 2017 解説
Xmas Contest 2017 の B 問題「Hello, Xmas Contest 2017」の解説です。
問題概要
長方形グリッドの各マスに文字を書いて（書かないマスがあってもよい）、そのグリッドを 0 度・90 度・180 度・270 度のいずれの角度に回転した場合でも "XmasContest2017" という文字列が読み取れるようにせよ。ただし文字列の読み取りは以下のように行われる。
- 上の行から順番に一行ずつ見ていく。
- 見ている行に文字が書かれたマスが1個もなければ無視する。
- 見ている行に文字が書かれたマスがあれば、そのうち最も左にあるものに注目する。そこに書かれた文字がアスタリスク '*' なら、この行を無視する。そうでなければ、その文字を読み取る。
グリッドのサイズも 100x100 を超えない範囲で自由に決めてよい。文字の書かれたマスが 32 個以下で満点 (100点)、100個 以上なら 0 点で、その間は 100 点から 0 点まで線形に点数が得られる。
解答
64 文字解答
17 17 *7102tsetnoCsamX* X...............7 m...............1 a...............0 s...............2 C...............t o...............s n...............e t...............t e...............n s...............o t...............C 2...............s 0...............a 1...............m 7...............X *XmasContest2017*
どう回転しても、各行の最初の文字に読ませたい文字を置いておけばそれを読んでくれることを使えば、四辺に読ませたい文字列を書くことで条件を満たす看板が作れます。
32 文字回答
16 16 *7.............. X.1............. .m.0............ ..a.2........... ...s.t.......... ....C.s......... .....o.e........ ......n.t....... .......t.n...... ........e.o..... .........s.C.... ..........t.s... ...........2.a.. ............0.m. .............1.X ..............7*
文字列を斜めに並べることで、1 つの文字列を 2 つの方向から読み取らせることができるようになります。
そのほか
共通する文字を頑張って省く、斜めに一本だけ文字列を置いて残りを辺で埋めるなど、32文字と64文字の間の解もコンテスト中にいくつか見られました。
Xmas Contest 2017 A 問題 Compressor 解説
Xmas Contest 2017 の A 問題「Compressor」の解説です。
問題概要
15 個の（数秒程度の）楽曲データについて、コンプレッサーを適用したものとしていないものの組（計 30 個の wav ファイル）が与えられる。15 個の楽曲それぞれについて、どちらがコンプレッサーの適用された音源かを当てよ。
コンプレッサーについて
問題文中にもあるように、コンプレッサーは「使いこなすのが難しいエフェクター」の代表格とも言える存在です。本問題の入力を聴いてもわかるように、適用したからといって音が劇的に変化するようなエフェクターではありません（もちろんコンプの種類やパラメタ設定によって劇的な変化を持たせることも可能ですが）。
難しいエフェクターということもあり、「コンプレッサー DTM」など適当に検索するとコンプレッサーの作用や使い方について解説しているウェブページがたくさん出てきます。今回の問題を解くにあたっては特に難しい使い方というよりも、コンプレッサーとはそもそも何をするエフェクターなのかという基本のところだけ分かれば十分です。
コンプレッサーは名前の通り「音量の大きすぎる部分を（なめらかに）抑える」効果を持ちます。要は音を小さくするエフェクター（乱暴）なのですが、コンプレッサーを使う目的はむしろ「音を前に出したい」「存在感を出したい」という方向性であることが多いです。元々大きい部分を先に潰しておき、そのあとで全体を持ち上げることで、全体的にはよく聴こえる＝存在感が大きくなるようにするという使い方です。
下に示すのは Waves 社の C1 というコンプレッサーの画面です。真ん中に出ているグラフが音量圧縮の形を表しています（横軸が入力で縦軸が応答）。大きい音を潰すという動作なので、基本的にこのような形のグラフになります。（今回のデータを作るのに使ったコンプレッサーは C1 ではないのですが、見た目がわかりやすいのでここでは C1 の画面を例にします）
このグラフをよく見ると、音量の小さいところはむしろ音量が上がっていることが読み取れると思います。これはコンプレッションによって下がったぶんのレベルを持ち上げるという機能がすでにこのコンプレッサーに含まれているためです （このコンプでは Makeup というパラメタで持ち上げを指定します）。C1 にかぎらず、コンプレッサーには元から下がったぶんのレベルを持ち上げる機能が含まれていることが多いです。
今回、問題文中で「同じ音に対して音量が著しく変化しないように」コンプレッサーをかけるという表現をしましたが、これはコンプレッションによって音を潰したあと、全体の音量が同じくらいになるまで全体を持ち上げて調整するというかけかたをするという意味です（「音量」にも色々あるのですが今回は RMS を揃えました）。
解説
解法1
耳で判断する。はいプロ。
解法2
コンプレッサーは「大きい部分を抑える」のですが、今回はその後で全体を持ち上げていますので、行われた操作としては「極端に大きい部分を抑えるかわりに、その他の部分を持ち上げる」となります。
すると、「抑えられた部分」と「持ち上げられた部分」のどちらが多いかが問題です。大抵の楽器は（特に打楽器では顕著ですが）鳴らした瞬間に急激に音が大きく出て、その後は比較的小さい音になります。なので、「抑えられた部分」はほかと比べてかなり少ないと考えられます。
つまり、波形の変化としては「ごく一部の音量が大きい部分」が抑えられたかわりに「その他大勢の音量が小さい部分」が持ち上げられることになります。実際にサンプル入力 (sample_mono_(dry|comp).wav) のサンプル値の分布を見てみるとかなり分かりやすいです。
もともとサンプル値が 0 付近に集中しているのが、（コンプレッション後の）持ち上げによって外側に広がっているのが顕著です。この例は問題文中にあるように極端にコンプレッションをかけているので明らかですが、実際の入力ではもっと微妙な変化です。それでも、同じような変化を認めることができます。
01_A と 01_B に対しても同様に分布を見てみましょう。画像ではかなり見づらいですが、01_A (紫) の方が 0 付近の山が低く、かわりに裾野 (絶対値 0.4〜0.5 あたり) では高くなっていることがわかります。
あとはこれを頑張って判定すればよいです。
サンプル値の絶対値をそれぞれ比較していって大きいものが多かった方とかそういう適当な判定法でも大体判別できます。この方法だと 04〜06 (EDM群)、特に 06 は少し微妙で誤判定があり得ます。他のケースだと結構大差になるのがここだと微差になっているので、この辺は答えを何通りか試してみることなどが必要になるかもしれません。
ｺﾝﾌﾟﾚｯﾔってよくわからんけど中心付近に分布が集まってるのをちらばすみたいな感じやろ～～～～て4次モーメントみたいの計算したら一発で通りました
— おめ (@omeometo) 2017年12月24日
中心に集中している分布が裾野のほうに広がるという変化を判定するには、omeometo さんがやったように 4 次モーメントを使うとより確実でしょう。
解法3
耳にも分布にも頼らない手法もあるようです。コンテスト後の Twitter では、スペクトログラムを眺めて目で判断するといった解法も見られました。
入力データについて
16 個（入力とサンプル）とも私が作りました（大変でした）。
ところで 音楽性の違いにより結成しました という同人音楽サークルが存在して、その1作目の CD (https://ongakusei.tumblr.com/001) が BOOTH でダウンロード販売中だったりして（露骨な宣伝）、サンプルとして使ったピアノ曲がこの CD に収録されているんだって！？ まずは是非クロスフェードデモをチェックだ！（露骨な宣伝）
本当の話をすると、15個のデータを頑張って作ったあとに、「アッ……サンプル用の音源もいるじゃん……」となってしまい、新たに1個作るのが面倒だったので既存の自作曲を持ってきました。
本番用の 15 個のデータはそれぞれ単一の音源を用いてテキトーに (それこそループ素材を重ねるだけとかで) 作りました。以下特に誰も得しない情報です:
- 01: Maschine Drum Selection (Komplete : ドラム : Maschine Drum Selection | 製品)
- 02, 03: Studio Drummer (Komplete : ドラム : Studio Drummer | 製品)
- 04, 05, 06: Nexus 2, EDM 3 (Nexus/expansion | reFX)
- 07, 08, 09: Cuba (Komplete : ワールド : Cuba | 製品)
- 10, 11: Ethno World 6 Voices (Ethno World 6 Voices | Best Service | bestservice.com)
- 12: Rise & Hit (Komplete : シネマティック : Rise & Hit | 製品)
- 13: Damage (Komplete : シネマティック : Damage | 製品)
- 14, 15: Action Strings (Komplete : シネマティック : Action Strings | 製品)
Xmas Contest 2016 C問題 Cutting Swiss Roll 解説
Xmas Contest 2016 C 問題「Cutting Swiss Roll」の解説です。
問題概要
N 要素の整数列 A が与えられ、これを使って 2 人 でゲームをする。ゲームは
- ひとりが A を好きなところで 2 つに切り分け、もうひとりが 2 つに分かれた整数列のうち好きな方を選んで捨てる。
という操作を、切る人と捨てる人を交代しながら交互に行う。最後に長さ 1 の整数列が残ったら終了とする。
先手が最後に残った整数を最大化、後手が最後に残った整数を最小化する戦略をとるとき、最後に残る整数を X とする。
先手の最適戦略 (後手が何をしても最後に X 以上の値を残せる戦略) を実装したプログラムを作成せよ。
制約
- 1 ≦ N ≦ 5,000
- 1 ≦ A[i] ≦ 10^9
解説
最適戦略は X の何になるかを示すときの証明から導くことができるので、X の値を求めよう。
まず、X の値を求めるために二分探索を行うことを考える。つまり、先手が X 以上の値を残せるかどうかの問題を解くことを考える。これは、A の各要素を X 以上なら +1、X 未満なら -1 に置き換えてゲームを行い、先手が +1 を残せるかどうか（残せるならば先手の勝ち）という問題になる。
ここで、この +1, -1 版のゲームの勝敗について以下の定理が成り立つ。この定理の内容は小さいケースを実験するなどして推測できる（何かこの定理に至る良い説明があったら教えてください）。
定理. 以下の 2 条件 (P), (Q) のうちどちらかが成り立つことと、先手が勝つことは同値である:
- (P) A の中にある +1 の個数が -1 の個数より多い。
- (Q) +1 の個数と -1 の個数が等しく、A の先頭 k 個の和 S[k] = A[1] + ... + A[k] が 0 になるような k が偶数個存在する。
この定理では A 全体やその接頭辞における +1, -1 それぞれの個数を問題としているので、定理中で導入した累積和 S を折れ線グラフの形で示したものをゲームの盤面と考えるとわかりやすくなる。
たとえば以下のような状況は条件 (P) が満たされている例である。折れ線の末尾が 0 より大きいところで終わっており、これは A 全体で +1 の個数が -1 の個数より多いことを表している。
また、以下のような状況は条件(Q) が満たされている例である。折れ線の末尾が 0 で終わっており全体としては +1 と -1 の個数が等しく、また先頭を除いた 4 つの箇所で折れ線が 0 と交わっているため、条件 (Q) における k が 4 つ存在している。
上記定理を証明する。証明は整数列の要素数 N についての帰納法による。
N=1 のとき
A = {+1} のとき、何もせず先手の勝ちであり、確かに (P) を満たす。A = {-1} のとき、何もせず先手の負けであり、(P) を満たさない。
N≧2 のとき
A の長さが N-1 以下のときに定理が成り立っていると仮定する。(P) ならば先手必勝、(Q) ならば先手必勝、先手必勝ならば (P) または (Q)、の 3 つを示せばよい。
なおこのゲームでは一回の手番のあと、+1, -1 をすべて反転することで、+1, -1 について対称に考えることができる。つまり、先手必勝であるとは、先手がある場所で切ったあと +1, -1 をすべて反転して、残った左右のどちらも (P), (Q) いずれも満たさない先手必敗の形を押し付けることができる、ということになる。
(P) ⇒ 先手必勝
2 通りの場合がある。まず、S (折れ線) が途中で 0 と交わる場合であるが、このとき先手は最初に S が 0 と交わるところ (青い線) で切ればよい。そうすると、切られた左側・右側のどちらも (+1, -1 を反転して) (P), (Q) いずれも満たさない形になっており、帰納法から両方ともに先手必敗の形である。よって青い線の部分で切れば相手に先手必敗の形を押しつけられるので、全体として先手必勝である。
次に S が途中で 0 と交わらない場合を考える。A の先頭と末尾が両方とも +1 のとき、全体として +1 は -1 より 2 個以上多い。なぜなら、S が途中で 0 になっておらず、最後に正になっているため、S の最後から 2 番目の値も正 (1 以上)であり、よって S の最後の値は 2 以上と言えるからである。したがってこのとき先手は先頭 1 要素だけを切り離すことで、左右どちらも +1 の方が多い形を相手に押しつけられて先手必勝である。
そうでないとき、必ず A の末尾が -1 である。なぜなら、A の先頭が -1 で S の最後の値を正にするためには、途中で S が 0 と交わる必要があるためである。ここで、A 全体を reverse してもゲームとしては全く同じであることに注意すると、A を reverse することで先頭を -1 にできる。reverse しても S の最後の値は正のままなので、reverse することで S を途中で 0 と交わるようにでき、前述のように最初に S が 0 と交わるところで切れば先手必勝である。
(Q) ⇒ 先手必勝
ここでは、S の最後の値が 0 である場合のみについて考える。そのような場合のみに限れば、(Q) と先手必勝が同値であることが示せる。
k=1 のとき、S は以下のような形 (あるいはそれを上下折り返した形) をしているはずである。
このとき、先手がどこで切っても、+1 と -1 の個数を均等に切り分けることはできない (そのように切り分けるには S が 0 のところで切らねばならない)。すなわち、左右のどちらかでは +1 の方が多くなり、もう一方では -1 の方が多くなる。よって相手が -1 の多い方を選択して残すことで勝つことができ、先手は必敗となる。
k≧2 のときは S が 0 のところで切る場合のみを考えればよい。なぜなら、そうでない場所で切っても +1, -1 の個数が均等でなくなり負けることが確定するためである。つまり、以下の図で青く示した点のみで切るゲームを考えればよい。
これはつまり、k 個の山 (以下の図で◯で示した部分) を切り分けていき、最後に山 1 個の状態 (k=1) を押しつけられれば勝ちというゲームである。
すると
- k が偶数のとき、k = 奇数 + 奇数 の形に切り分けることで相手に奇数を押しつけられる。
- k が奇数のとき、k = 偶数 + 奇数 と切り分けることしかできず、相手に偶数をとられる。
ことがわかる。k=1 (奇数) を受け取った側が負けることから、(S の最後が 0 という状況下に限れば) k が偶数であること、すなわち条件 (Q) は先手必勝であることと同値である。
先手必勝 ⇒ (P) または (Q)
(P) でも (Q) でもなければ先手必敗であることを示す。
まず (P) ではないので S の最後の値は 0 か負である。負のときは、どこで切っても -1 の多い部分を相手にとられてしまうので必敗である。したがって S の最後の値が 0 であるときを考える。
ところで、先程 S の最後の値が 0 のときに限れば、(Q) は先手必勝と同値であることを示した。ゆえに (Q) ではないことは先手必敗であることを意味する。
したがって (P) でも (Q) でもなければ先手必敗である。
以上で定理が証明された。最後に、具体的な戦略のみをまとめておく。
戦略
まず、上記定理に従って X の値を実際に求め、A[i] を X 以上なら +1、X 以下なら -1 に置き換えておく。すると A は先手必勝 (先手が必ず X 以上を残せる) 形になっているので、あとはこの上で必勝手順を行えばよい。具体的には以下のようにする。
切るとき
まず累積和 S を計算しておく。
- +1 の方が個数が多いなら、S が最初に 0 になる点で切る。そのような点がなければ A を reverse したときの S が最初に 0 になる点で切る。そのような点もなければ最初の 1 要素を切り離す。
- +1 と -1 の個数が同じなら、S が最初に 0 になる点で切る。
選ぶとき
上記定理によって勝敗判定は簡単に行えるので、勝てる方を残す。
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 時とかで、そもそも難易度を判定する脳の働きが停止していて何も考えてませんでした。ちゃんちゃん。
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秒) でした。
ICPC 2016 国内予選 G -- ワープ航法
問題文:
http://icpcsec.storage.googleapis.com/icpc2016-domestic/problems/all_ja.html#section_G
テストデータ:
http://icpc.iisf.or.jp/past-icpc/domestic2016/judgedata/G/
「二点を通る直線で切るパターンを全部試す」はよくありそうで、「円で切り分けられた領域ごとに考える（ために二円の交点を列挙する）」のもよくありそうだけど、このふたつの組み合わせは見たことがなかった気がする。
求めるのが最小値なので、領域を切り分けるといいつつ、各領域における包含のパターンだけが列挙できればよくて、計算するときはワープ位置は平面上の好きな点にとれると考えてもいいのも面白かった。
続きを読むお誕生日コンテスト 解説
この記事は Competitive Programming Advent Calendar 2015 - Adventar の 1 日目のものとして書かれました。
ICPC のチーム戦略についての記事を書きましたが、ICPC もう引退したよ、そもそも ICPC 出てないよ、ICPC って何、という人も多いと思うのでおまけです。
去る 2014 年 2 月 2 日に、お誕生日コンテストというコンテストを開きました。
ふつうのコンテストではあまり見ないような変な問題を集めたコンテストなので、知らなかった方は是非解いてみてください。時間を無駄にできること請け合いです。
ところでこのコンテスト、解説記事をほぼ準備していたにもかかわらず最終的に完成しなかったので長い間解説がありませんでした。そこで、これを機に解説を完成させ公開しました。
こういう変なコンテストに出たいと思っているので誰か開いてください。
