0. だいたいこんな記事
この14日であったのは、
です。
1. 模擬国内まで(まえがき)
ICPC、今年もアジアに行けたらな~そして今回こそは戦力になれたらな~という甘い期待を抱いていた私は、fineさんにチーム分けという現実でひっ叩かれて目を覚ましました。そしてチームOboeのリーダーとしてICPCに(主な)戦力として活躍することを求められました。
まずは抽象的な目標として 「殿軍の将となる」 という目標を定め、またそれを具体化したものとして 「本番でABC+1完」 を目標にして動くことに決め、後者だけをチームメンバーのNキチさんとArkさんに伝えました。*1
表面上は2位でアジア予選に勝ち上がることをにおわせつつも、実際にはアジア予選に進出できるとはほぼほぼ考えておらず、しかしそのことを伝えると士気の低下を招きかねないため伝えないという方針でした。まあ当人たちも気づいていたとは思いますが……
またそのためには適切な量の精進が必要だろうと考え、ICPCの模擬国内、国内予選、アジア予選の2010年以降の過去問のうちAOJ-ICPCでの評価が400点以下(青色帯です)かつ幾何でない問題をすべて埋めておくことにしました。これは順調に進み模擬国内までにほぼ終わらせることができました。
2. 予知夢
模擬国内では「適切に失敗する」ことを目標にしていました。失敗をしていれば本番でその轍を踏まずに済むからです。しかし、結果は こちらの想定を遥かに上回る大失敗 となりました。Arkさんがデバッグを成功させていなければ危うく1完でした。私はずっと後半の(解けない)問題を見ていて、これが完全に裏目に出た形です。コーチらからのアドバイスも受けて、このことから以下の教訓を得ました。
- 前半の問題は全員できちんと解く。問題の配点はすべて同じ。
- バラバラの問題を考えない。ひとりでICPCの問題が解けるほど我々は地頭ない。
- 後半の問題を開きすぎない。
この結果は大誤算であり大変打ちひしがれたのでさらなる精進をすることに決めました。黄色帯である550点問題まで解説ACでいいので埋めることにしました。
3. 雁字搦め
順調とは言えずとも450点、500点を埋めていたのですが、550点問題にチャレンジしたところ、3問連続で「解説を見て実装しても実装できない」という事態に陥り、1回の実装量が多く消耗すること、できなかった場合のデバッグが極めて困難なことの2点からどうしても精進に及び腰になってしまいました。その頃から英語がスムーズに読めなくなり英語問題を実装することも憚られ完全な停滞期を迎えます。
そのような中ABC133があり黄パフォを取って青コーダーに昇格しました。確かに嬉しかったのですが、どうしてもICPCのことがちらついてしまい振り返ったりするゆとりがありませんでした。 爆死の度合いが激しすぎた余り本番でもやらかすのでは? という思いが頭から離れませんでした。 だからといって何か動くこともできず非常に苦しい期間を過ごします。
後半1週間、前半に大量に解いた構文解析を忘れているのではないかという懸念からすでに解いた問題をやり直せばいいのではということに思い至り、それからはやり直しをいくつか行いました。それでも往時の勢いはすっかり失われていました。いくら好意的な解釈をしたにしても、私が無能であるという事実は覆しようもないのではないでしょうか。
そんなふうに打ちひしがれている間に、Arkさんはきちんと精進を進め(私がやらなかった幾何含む)、Nキチさんは幾何ライブラリを仕上げてきていました。結局使わなかったとはいえ、本当に大したものです。特に使われることのないライブラリを作ってしまったのはひとえに私の不勉強がいたすところであり、大変申し訳なく思っています。*2
4. 本番
最終的な精進記録は以下のようになりました。
期間全体のsummaryはこう
— Badlylucky (@Wklqtzsyei) 2019年7月11日
100*2から始まったので2ヶ月で65AC21400pts.
平均すると少なくて泣いちゃうけどチーム全体ではいちばん精進した!はず! pic.twitter.com/xUgM4EQ5A2
大学全体では最も精進した人でした。
模擬国内での反省を踏まえ、本番での方針は「NキチさんがA問題、私とArkさんでBとCのうち面倒なグラフもしくは構文解析が出たら私、残りをArkさん」としました。また、問題文が散逸してしまうことを防ぐために問題文全体をホッチキスで閉じました。これらの方針自体はよく機能していたと思います。
本番では面倒そうなグラフっぽいのがB問題で出たので私がBを担当しました。私は考察が詰めきれず書いている途中で間違いに気づく、ということをよくやるので実装を途中で投げ出して誰かに任せる、ということはしないことにしました。正しかったのかは判断できかねます。*3
AB問題を順調に通し、C問題を3n の本質までは気づきましたが、そこからがとてつもなく長く辛い2時間30分でした。
まず最初、追加する候補をsetに保持して全探索する方針でTLE(1010 くらいらしい?)。その後、逆にそれぞれで必要な候補をmapに記録して後で必要だった個数を満たしているものの最小を取るというアルゴリズム*4に切り替えて実装を進めていましたがこれを無限にバグらせていました。一度書き直すことを検討すればよかったかもしれません。
またD問題も見ましたが最初区間DPでやろうとしてO(N3)かかることが判明し断念、その後何となくDPが引っかかりつつも何も分からない状態が続いていました。僕のICPC2019はこれで終わりです。
粘ればF思いつけたかもしれないとか愚痴りつつも、結局Cが通ったところでDの想定解が思いつくかは極めて怪しく どんなに頑張っても3完止まりでした。
5. 屍
謝っても謝り尽くせるものでは到底ありません。
Arkさんは来年もあります。そのときは私のような戦犯無能を引かないことを祈ってください。また、貴重な失敗例として来年以降のcontestantの方は刻み込んでください。 特に「詰まったら書き直す」のくだり。詰まったら書く人を変えて最初から書き直す戦法はかなり有効です。
また、 精進は折れない範囲でやることと、折れない範囲では問題数を気にせずやることが大事です。一度折れてしまうと持ち直すのは困難を極めます。私の場合最初問題数を見て「これを全部解くのは無理だ」と決め打ったのがダメだったようです。それなり以上のスピードで自力ACできることを意識してください。
最後がこんな結果になってしまい、この先を暗く照らしています。嫌な思いをさせてしまったチームメンバーには顔向けできませんね。上に立つということがどれだけ難しいかを痛感します。そして私がそれにふさわしくないという、何十度目かの確信も。
6. 撰集
おまけとして、AOJ-ICPC精進をする過程で気に入った問題をいくつか紹介します。
差分パルス符号変調(模擬2010C, 250)
Differential Pulse Code Modulation | Aizu Online Judge
気づいてしまえば何ということはないのですが、気づくととても面白くなる問題です。
みさわさんの根付き木(模擬2016a:C, 350)
みさわさんの根付き木 | Aizu Online Judge
解説読んでもなお苦戦し、かなりオリジナリティあふれる実装を行いました。いずれ解説書きたいです。
鉄道乗り継ぎ(国内2012D, 400)
ICPCで数多く出題されるグラフ問題のうち、最も簡単な部類の典型です。これが解けると、自力ACできる範囲が一気に広がります。こういうのAtCoderに欲しい