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 日に、お誕生日コンテストというコンテストを開きました。
ふつうのコンテストではあまり見ないような変な問題を集めたコンテストなので、知らなかった方は是非解いてみてください。時間を無駄にできること請け合いです。
ところでこのコンテスト、解説記事をほぼ準備していたにもかかわらず最終的に完成しなかったので長い間解説がありませんでした。そこで、これを機に解説を完成させ公開しました。
こういう変なコンテストに出たいと思っているので誰か開いてください。
ICPC のチーム戦略について
この記事は Competitive Programming Advent Calendar 2015 - Adventar の1日目の記事です。
はじめに
私 (JAPLJ) は今年の 5 月にモロッコで開催された ACM-ICPC の世界大会で（世界大会出場は 2 回までのルールにより）現役選手を引退となったので、ICPC についてなにかを書いておこうと思いました。
ICPC といえば特筆すべきルールはやはり 3 人で 1 台の PC を使うチーム戦というところで、これまでにも様々なチーム戦略に関する記事が書かれています：
- ICPCに向けたUECodersの戦略 - とどの日記
- ~shiokawaのICPCに向けたチーム練習、コンテスト直前の準備について - しおしおたのブログ
- ICPC のチーム体制について - (iwi) ｛ 反省します - TopCoder部
（少し探して見つけたものと覚えていたものを順不同に挙げただけなので他にも探せばあるかもしれません）
そういうわけでチーム戦略についての記事を書こうと思いますが、一般的な話をしても仕方がない（というより iwi さんの記事がたいへん役に立ちます）ので、自分の経験に基づいたチーム戦の話をしたいと思います。つまり、特殊な例についての記録ということになるので、これがそのまま他のチームの戦略に役立つことはあまりなさそうですが、一部でも参考になれば幸いです。
対象
この記事で対象になるチームは以下の条件を満たしているようなチームです。
- チームメンバーにりんごさん (rng_58) がいる。
おっと、りんごさんも既に現役選手を引退となったので、対象チームがなくなってしまいました。ここまで読んで頂いてありがとうございました。明日の記事は 1_000_000_007 さんで「悪問の具体的事例とどうすればその問題をよりよくできるか」です。楽しみですね。
というわけにもいかないので、粛々と続きを書きます。
チーム構成
ここからは基本的にモロッコへ行った際のチームをもとにします。
- rng_58 (りんごさん)
チームの司令塔です。問題の概要をいち早く把握し、迅速に解法を導き、それら解法の複雑さや現在の順位表をもとにどの問題から手をつけるべきかを判断し、適切なコーダーに仕事を割り振ります。
- semiexp (準急)
コーダー 1 です。圧倒的なデータ構造力とタイピング速度、自身も TopCoder の target である強みを活かして、序盤の簡単な問題・データ構造を活用する問題・複雑な DP の問題などを担当することが多くありました。
- japlj
コーダー 2 です。TopCoder のレーティング等では上 2 人に遠く及ばないところがあるので、その分を練習量でカバーし、幾何・探索・複雑な実装を要する問題を多く担当しました。
チーム戦略
とにかく、実際のコンテストでどういう戦略をとるかについて書きます。
開始時
計算用紙を 1 枚使って、現状の記録を行います。10問のコンテスト (A問題からJ問題まで) の場合は、まず大きく A から J までのアルファベットを紙に書きます。
コンテスト中は、問題の簡単な分野や内容を表す語句、既に担当コーダーが決まった場合はその名前 (うちの場合は s か j)、解き終えた場合にはそのアルファベットに大きく丸を書いていきます。この問題はどういう解法で時間がかかる、この問題をまずやって次はこれ、などといった相談はこの紙を使って行います。
最序盤
ICPC において最序盤の問題選択は非常に重要です。最初の 1 問を解くまでに余計な時間を 5 分かけてしまうと、その後解く全ての問題に +5 分ぶんのペナルティがかかることになってしまい、これは無視できない量です。特に World Finals のように問題の並び順と難易度に関係がない場合、簡単な問題を迅速に探しだす必要があります。
タイピング速度のある準急にテンプレートの準備などを行ってもらっている間、急いで問題文を読んでいきます。ここでは明らかに幾何のような図がある問題や問題文が長すぎる問題は一旦放っておいて、短くて単純そうなものを直感的に選んで読んでいきます（この辺の選択は経験がモノを言う場面でもあります）。準急が一通りの準備を終えた段階で、簡単な問題を渡すことができればベストです。
また、りんごさんは問題文の短いもの、数学の要素が強そうなものを優先して読みます。数学の問題は解法は難しくとも実装が容易であることが少なくなく、またりんごさんは数学の問題が非常に得意なので最序盤にこういった問題を通すことも多くありました。
序盤
開幕が落ち着いたら、序盤の比較的容易な問題を片付ける作業に入ります。ここをいかに滞り無く行えるかがかなり大切です。
この段階では、基本的に semiexp, japlj のどちらか片方が PC 前で実装を行い、もう片方がまだ読めてない問題文を読んで概要（とすぐに分かれば解法）をりんごさんに伝えていきます。りんごさんは自分で読んだり受け取ったりした問題概要から、次にどの問題をやるべきかを判断します。このあたりではまだ問題が比較的容易なためコーダーがどちらでも大差なく、また効率の観点からいっても同じコーダーが連続しないようにします。
あまりに簡単な問題という場合を除いて、りんごさんが問題を担当コーダーに任せるときには「何分ぐらいかかりそうですか？」という質問をします。これに正確に答えるのは非常に難しいですが、5 分や 10 分ぐらいの単位で大まかな値を申告します。解法がわかっている複数の問題のうちどれを優先して解くかを考えるときに、同じコーダーが連続しないことに加え、この申告時間の短い方を優先することになります。（この申告が間違っていることももちろん往々にしてありますが、申告より短く終わった場合はそれでよし、申告より長くかかった場合はその時点で戦略を考えなおして交代するなりの処置をとります）
中盤
だいたい全問題の概要がわかり、容易な問題が片付いたあたりです。コンテストの難易度にもよりますが、この時点で開始から 1〜2 時間程度、解いた問題数が 5〜6 問であることが多かったと思います。
このあたりに来ると、コンテスト終了時の順位表の推測が行えます。「この問題はまずどこのチームも解かない」「上位の間ではこれを解けるかどうかが重要になる」といったことから、「あとはこの 4 問にこういう順で挑戦して時間内に全て解ければベストで、5 位以内には入れる」のようにコンテスト終了までの大まかな見通しを立てます。
semiexp, japlj はそれぞれ担当する（わりと重めの）問題があってそれに取り組むという状態になっています。りんごさんは、難しい数学の問題があってそれに取りかかっているという状態になると良いですが、問題セットによってはこの時点ですでに暇になっている（残った問題はとても解けるものではない or コーダーが考えるべきことしか残っていない）ことも多くなります。
終盤
コンテストの残りが 1〜2 時間ほどになってくると、WA が出てしまってとれないといった問題も出てきます（中盤までにこういう問題を出すとかなりまずい）。このときデバッグに印刷は積極的に行いますが、コーダー交代は比較的慎重に行います。printf デバッグ等明らかに PC を使ったほうがデバッグが捗ること、コーダーの交代は頻発するとそれによる時間のロスも無視できなくなってくることが理由です。
手元で WA が出るケースを探して、見つけたら printf デバッグ等の結果も含めて全部を印刷し、それについて吟味している間はコーダーを交代する、といったケースが多かったように思います。手元でどうしたも WA になるケースが見つからずどうしようもない（もはやソースとにらめっこするしかなく、PC を使うメリットがない）と判断した場合もコーダーを交代します。
コンテスト後
コンテストが終わったあとは反省会を行います。
まず全問題を振り返って、それぞれについて吟味します。このとき、コーダーはもう一方のコーダーが担当した問題を（概要も含めて）全く知らない状態が良いです。これはりんごさんの采配と、その後のコーダーによる実装が詰まらず上手くいったということを意味しているためです。逆にバグが出て詰まってしまい印刷などをした場合、デバッグに協力するためにもう一方のコーダーにも問題概要と解法が伝えられる、といったことが起きてしまいます。
また、全問題のアルファベットを大きく書いた紙を使って全体の流れを確認します。解く問題の選択ミスはなかったか、順番は正しかったかの確認や、実装に申告より長い時間がかかってしまった問題についての検討などを行います。
練習について
個人練習
このチームの戦略は、それぞれの人がどういった能力を発揮するかが分かりやすくなっています。たとえばりんごさんは 5 時間の間、PC には全く触れません。一方僕や準急はふつうのコンテストと比べ、問題の解法を考える時間というのが圧倒的に少なく、ひたすらコーディングに偏った時間を過ごすことになります。
そのため個人としての練習もわかりやすく、たとえば僕は AOJ-ICPC の問題を全て（当時）埋めるなどの練習をしていました。
チーム練習
このチームの戦略はやはり明快で、コンテスト中の各人の動きはかなり分かりやすくなっています。そのためチーム練習に特別に時間を割くことはほとんどありませんでした（JAG の開催する模擬大会に出る程度）。
しかしモロッコに行ったときだけはチーム練習を行いました。序盤の戦略で「容易な問題をいかに滞り無く片付けられるかが重要」と言いましたが、りんごさんの分析により「序盤で詰まったコンテストでは最終的な成績も悪く、序盤がスムーズにいった場合最終的な成績もよい」ことがわかったためです（これはあくまでもこのチームの話です）。
確かに、これまでに調子の良かったコンテストを振り返ると、序盤の容易な問題を片付けた段階で 2 位に 2, 3 完の差をつけて 1 位ということが少なくありませんでした。一方、調子の悪かったコンテストでは、序盤にそこまで他チームをぶっちぎることが出来ていなかったように思われます。
そこで、モロッコにて「5時間コンテストの最初の1時間だけ練習」を行いました。これはその名の通り、5時間コンテストの過去問をひとつ選んできてそれで練習をするのですが、開始1時間が経った時点で終了とします。もちろん、戦略としては 5 時間コンテストに挑むつもりで行います。
つまり、直前になって 5 時間フルで使って難しい問題に取り組んだところで、いまからそういった実力を底上げするのには無理がある。だったら、コンテストに重要な序盤の動きだけを集中的に鍛えればよいし、そういった立ち回りなら直前からでも改善できる、という発想です。5 時間の練習で得られる成果を 1 時間で得ようという最高の練習です。効率 5 倍、スゴイ！
