これは夢日記ではありません*1。 夢日記は これ と これ。
チームメイトは夢日記と同様、monkukui と TAB とえびちゃんです。 チーム名は tsutaj で、これは去年までチームメイトだった先輩に由来します。
tsutaj 抜きのチームに tsutaj と名付けるの、余因子展開とかで出てくる、行列 \(A\) の \(i\) 行 \(j\) 列抜きを \(A_{ij}\) と書くやつに似ている気がします。
See also: monkukui の参加記、TAB の参加記。
前日
バチャ をしていました。やや冷え気味ですね。
それからは、有名なライブラリをローカルに落とす遊びをしました（結局使いませんでした）。
去年のことを思い出したりしていました。去年の参加記は これ。
当日・本番前
リハーサル
模擬地区のときはリハーサルに出そびれたので、今回はちゃんと出ました。 ちゃんとと言いつつも、AC はしていません。
せっかく「まれに見られる悲しい状態」*2になったので、おふざけの画像を生成したりしました。
リハーサル、失敗！ pic.twitter.com/vqPTqGmbaf
— えびちゃん (@rsk0315_h4x) 2020年11月6日
矢印で表現するやつかわいくてすき。この生物には名前がついているようですね（ふににちゃん？）。
ジャッジ結果の URL を少し改変するといろいろなジャッジ結果を見ることができ、（少なくとも？）20 個あるようです。 プログラムと解答ファイルの両方にプログラムを指定すると以下のような結果になります（ペナなし）。
Program as answer.
You submitted a program source file as an answer file. Enter a file name of an answer file in the box.
両方に解答ファイルを指定すると Correct answer. と言われ、二つ目のケースで困ってしまいます。 たぶん、こういうお助け処理は correct 以外のときだけ行われるのでしょうね。
Binary program. というジャッジ結果もあるようなのですが、C++ をコンパイルした実行ファイルを提出したり、Java のクラスファイルを提出したりしても Correct answer. になってしまい、条件がよくわかりませんでした。
他にもいろいろ試そうと思っていたんですが、試し終わらないうちにケースを使い切ってしまいました。
そういえば、国内予選のジャッジ結果では、紫と緑が AC 時に出てくる背景色なのですよね。 そのことはわかっているのですが、文字色が赤なので、AC のときも一瞬焦ってしまいます（警告色を感じるので）。
20 種のジャッジ結果たち。
興味ある人がいるかわからないですが、せっかく調べたので載せてみます（載せない方がよかったら消えます）。
Congratulations!
You have successfully finished this problem.
Correct answer.
Proceed to the next data.
Correct answer.
Proceed to the next data.
Recall that to finish a problem, you need to correctly answer two data in a row, with the same program.
Correct answer, with a program different from the last one.
BAD NEWS: You can no longer finish this problem, because you would need to answer the next data correctly with the same program, yet there are no data left for this problem. Recall that to finish a problem, you need to correctly answer two data in a row, with the same program.
Correct answer, with a program different from the last one.
Proceed to the next data.
Recall that to finish a problem, you need to correctly answer two data in a row, with the same program.
Empty answer.
You either specified a wrong file name which does not exist, or an empty file. Enter a correct file name in the box.
Empty program.
You either specified a wrong file name which does not exist, or an empty file. Enter a correct file name in the box.
No answer file.
Enter a file name in the box.
Missing problem.
Select a problem in the list.
No program file.
Enter a file name in the box.
Wrong answer.
Try again.
Wrong answer.
Try again.
You need to correctly answer two more data. Recall that to finish a problem, you need to correctly answer two data in a row, with the same program.
Wrong answer.
BAD NEWS: You can no longer finish this problem, because you would need to answer two more data correctly, yet there is only one data left for this problem. Recall that to finish a problem, you need to correctly answer two data in a row, with the same program.
The contest is over.
You can no longer send your answer.
Binary program.
You specified a binary (executable) program or compiled Java class file. Enter a file name of a source program in the box.
Program as answer.
You submitted a program source file as an answer file. Enter a file name of an answer file in the box.
Input as answer.
You submitted an input file as an answer file. Enter a file name of an answer file in the box.
Input as program.
You submitted an input file as a program file. Enter a file name of a program file in the box.
Previous answer.
You submitted an answer to the previous data. You should run your program with a new input file.
Submits in too short time.
The server stopped processing your submit since you made submits in less than 0.5 seconds.
以上 20 種です。
間違ったファイルを指定してしまったとき用のジャッジ結果が用意されていて優しいと思います。 Wrong Answer. 以外はペナがつかないようになっていると思います。
リハーサルおわり
暇なので、バチャをしていました。 肩慣らしに簡単な問題を解こうということで、チームで これ をしました。
えびちゃんが H を AC した後に monkukui が H に RE を投げていたりして面白かったです。 J は苦手そうだったのですが、ひらめいて、書いてすぐ投げました。数秒後に monkukui が WA を投げていて危なかったです。
当日・コンテスト
ざっくりとした戦略は次のような感じです。
- monkukui が A、えびちゃんが B、TAB が C を見て、各々できたら書く。
- 構文解析はえびちゃん、幾何は TAB、その他つらそうなのは monkukui に変わる。
- できるなら一人でやるが適宜話し合う。
- デバッグが必要になったらえびちゃんに聞く。
A や B でペナを出すとつらいので、油断した実装をしないようにしましょうという話をしたり、「まぁ WA を出しても後半でもう 1 問解いてくれたらいいからね」とか言ったりしました。
問題内容はあまり説明しないので、必要に応じて 問題文 を読んでください。
開始
あの、はじまりません。
no status information for team ###### in contest are found (database broken or not initialized?)
と書かれていたので、たぶん database broken or not initialized だったんだと思います。
「れれれ冷静になっていいい一旦コーチに連絡しましょう」とか言っていました。えびちゃんが一番焦っていたかもしれません。
今度こそ開始
B を読みます。union-find を貼りそうになりますが、必要なくて、std::set で処理して、AC です。
数秒差で A も AC して、5 分くらいで 2 AC です。この時点で 6 位です。
C、え、これ、何するんでしょうね。
D は構文解析らしいので、うれしくなって、読みます。 え、これ、何するんでしょうね。
E は monkukui が解けそうと言ったり、解けてないことがわかったりしました。
正直なところ、2 完でお通夜まであるかなと思いました。 最初は「全チーム高々 2 完で終わるからペナ差で通過でしょ」と思っていたのですが、めちゃくちゃ C が通されていて焦ります。
D は、愚直には階乗通り試せばいいんですが、指数時間に落としたい気持ちです。 階乗モノは bit DP でできがちというのがあったので、変にハマってしまいました。
C が謎なんですが、TAB が愚直を書いて回してくれて、時間は掛かったものの AC してよかったです。 この時点で 68 位とかになっていて、ボーダーギリギリで通過かなと思っていたんですが、どうやら学内 3 位らしく、あーとなりました。
D は TAB と話しながら決め打ちというワードまでは出てたんですが、なかなか時間がかかりました。 解法は以下のような感じです。
最終的な答えとなる変数を決め打ちする。
残った変数について、上記の変数より前に来るか後に来るかを決め打ちする（指数通りある）。
答えの変数には 0、前のものには -1、後のものには +1 を割り振る。
(x<y) は min(x, y)、(x>y) は max(x, y) として計算する。
どちらかの式の値が 0 以外なら寄与分は \(0\)。
両方の式の値が 0 なら valid な順序であり、前のもの・後のものの個数をそれぞれ \(f\), \(b\) とすると、寄与分は \(f!\cdot b!\)。
これを、各決め打ちに対して足し合わせたものが答え。
各順序に対して、それが答えに寄与するのは（ある変数が全体の値となる）1 回だけで、両方の式の値が一致するときのみ加算されるので、うまくいきます。
コンパイルが一発で通り、サンプルも一発で合い、テストケースも二発（国内予選なので）で通り、気持ちよかったです。 頭と手がふわふわしました。 「D、サンプル、通った」「あ、correct って出てる」とか、かなり口が不自由になっていたと思います。
31 位くらいになっていて、さすがに通過したかなと思いました。
TAB が F の概要を説明してくれましたが、頭がふわふわしていたので半分くらいしかわかりませんでした。非常にごめん。
前後関係をあまり覚えていませんが、monkukui が E をがんばっていて、TAB がサポートしたりしていたと思います。 桂馬なので二部グラフになるとか、一つ飛ばしで動くので偶奇で分けていいとか、左右に動く（まっすぐは動かない）のでそこでも半分にできるとか言っていて、賢いなぁとなりました。
monkukui ががんばってデバッグして、えびちゃんが手伝って、結局えびちゃんの PC で計算して、E を AC しました。 この時点で 12 位とかで、夢かと思いました（夢地区ではないです）。
頭がふわふわしていて、Congratulations! を見ながら「あ、E 通ってますね（他人事）」と発言してしまいました。 自分でも意味不明すぎて二の句が継げなかったのですが、想像以上にチームメイトを混乱させてしまったようです（それはそうか）。ごめんなさい。
うっかり「通過したでしょ」と口走ってしまったのですが、ここから弊学の他チーム全てに抜かされると不通過になるはずなので、それらのチームに対して失礼な発言だった気がします*3。ごめんなさい。
F を TAB ががんばっていたもののバグっていそうで、デバッグを手伝うも、うまくいかず、そこで終了しました。
提出した問題については一つも WA を出さなかったのもよかったと思います。
最終的な順位は 18 位でした。
これ、毎年同じ URL なので、来年には見れないんですね。
コンテストおわり
「もう TweetDeck 開いていい？」とか言っていました。やばい人じゃん。
Twitter 中毒者という意味です
— えびちゃん (@rsk0315_h4x) 2020年11月6日
2 完を覚悟したタイミングから各々 1 問ずつ AC していて、喜ばしい気持ちになりました。 あれこれ話し合ったりしてチーム戦っぽさもあったと思います。 特に E は TAB が考察・monkukui が実装・えびちゃんがデバッグ（と提出）をしていて、面白かったです。
今回の国内予選は今までの国内予選で一番気持ちよかったと思います。 理由は以下のものが主です。
去年までできなかったことがいろいろできたので、うれしかったです（通過自体はできていたけど 4 年連続は初めてなので）。 三人コーダーのチームなので並列 OK のルールだと有利なのかなとも思いますが、最近の人たちはほとんど三人コーダーだったりするかもしれません。 何にせよ、うちのチームにとってはやりやすかったと思います。
TAB が「あまり仕事できなかった、愚直しか書いてない」と嘆いていましたが、後半 3 問の AC は TAB のおかげだと思います（愚直のやつ含む）。
毎年、終わってしばらくぼんやりしてから「どうやら例年通り通過したらしい」という実感が湧いている気がしますが、今年もそうなりました。
tsutaj ありがとう。
おわり
おわりです。やっぱりうれしい。
今年は弊学からは 2 チーム通過はならなかったように見えますが、来年も出場資格がある人はぜひがんばってほしいと思います。
*1:念のためほっぺたをつねっておきました。
*2:ICPC 予選システム ユーザマニュアル にある表現。
*3:それらのチームがここから十分な個数の AC をすることはないと発言しているように聞こえるので。