23BのAstral__(19さい)です。国内模擬予選・予選に参加させて頂きましたので、それの参加記を書いています。書き終わりました。

追記：ヘッダー画像を追加しました。最近一人で行った由比ヶ浜、或いは太平洋、果ては地球の写真です。

チーム

ACORNというチームで出ました。チームメンバーはAtral__, cho57020, otoshigoです。ラストイヤーの方は居ませんでした。
私が初参加で、他の御二方はそうでは無かったと記憶しています。

結果

模擬国内予選が現役内8位(7完)で、国内予選は27位(5完)で落選です。ぐはぁ...

流れ

5月中旬 ~ 模擬国内直前

5/17にtrap内での希望者による割り振りによってチームが決定し、私の中でICPCが動き始まりました。
ICPCのチーム内の役割分担として、「構文解析・幾何・ライブラリ」の3つの役割があることは有名だと思う(自分調べ)のですが、普段からライブラリを弄ることを好んでいた私としてはライブラリを担当しようと思っていました。
そこで、チームを組んだ日からgithubにリポジトリを作り、暇とやる気が揃った時を見つけてはぽつぽつ更新をしていきました。
ライブラリを作る上では、

• 写経しやすいように短い実装にして...
• 写経ミスしないように、似た変数名を避ける/マクロを使用して...
• 使い勝手が良くなるようにdocumentをつける/一部には使用例をつけて...

等々の意識をしていました。
この作業は中々楽しく、ライブラリに想いを馳せている途中で謎アルゴリズムを思いついたりもしました。

こうして手塩にかけたライブラリはすくすく成長していきました。

しかし、6月頭頃に今年からルールが変わった旨の発表がなされ、これらの作業の意義が無くなってしまいました。とはいえ、ACLに無いライブラリを用いる && 幾何では無い問題は私が解く事になっていたので、それらの練習をしたり、また実践で解いていて実装が重く、嫌になった問題をライブラリにしたりしていました。

また他に、週に1, 2回ほど集まって過去の模擬国内予選を解いたりしていました。その過程で、チームメンバーにmacユーザーが多かった事・私が環境を良く整備していた事から、私のPCで本番を迎えることが決定されました。

模擬国内予選参加記

関わった問題について振り返りを軽く書いていこうと思います。

A

チームの合意の元私がAを見ることは決まって居たので、Aを見ました。問題文が短くて嬉しかったですね。

C

本来私は次はDを解く話になっていたのですが、問題文が届かず暇だったのでCに少し参加しました。

D

初手で寄与の分解はするだろうなと思い分解したのですが、そのあとがスッといきませんでした。そこで、誰かにとっての自明である事を祈りながらchoさんに「この先どうすれば良いと思いますか」と聞いてみた所、有難いことにスッと答えを出して下さったようなので問題をswapし、私がFを見ることにしました。

F

区間を区切って行く問題だと思いました。そこで纏められる区間を列挙する事を目的に、「区間を指定した時、その区間を1つに纏めることはできるか？」を $O(区間長)$ で解くシュミレーションを考えたのですが、これでは $O(N^3)$　かかってしまいますし、初期レベルが低い事も使っていません。　そこで、帰ってきたchoさんにどうすれば良いと思いますかと聞いた所、良さそうな解法を教えて貰ったので、Eの実装を横目に私がFの実装を詰め、程なくしてEが通ったので私がFを書いてACが出ました。

G

Fの実装が終わり、Gを解いていたotoshigoさんに進捗を聞き、自分の考察に取り掛かりました。私は過去の"K番目"問題の経験を元にそれらで使った手法を適応しようと思ったのですが、上手くいきません。その後とりあえずの全探索を考えたら配るdpが立ち、その後それを貰うdpに変えることでACが出ました。

模擬予選が終わった後は、なんか上手く行ったね〜と話していました。

それから予選まで

• 本番環境の確認
• ライブラリの充実化
• 都民の皆様の生活水準の改善

等に取り組んでまいりました。

予選

予選も、関わった問題について振り返りを書きます。

A

いつもより解きやすい感じがして安心しました。

C

最初にBFSで終わりという合意をしました。他、こういう実装が楽そうですというコメントをしました。

D

シュミレーションです。ループの存在と、後はとても長い直進にだけ気を付ければ良いです。具体的な処理も比較的楽に書けるものだと感じました。途中まで「左に曲がる」を「右に曲がる」と誤読していたのですが、それを修正したら通りました。

F

Dが終わりGを眺め始めて早々、choさんに「Fはシュミレーションして終わりではないか？」と確認を受けました。その後、正当性は良さそうですが、実装が本題に見えますとコメントし、実装を少し考えました。
そして手始めに、一度の直進で [1]ボールにぶつかる [2]穴に落ちる [3]壁にぶつかる　のどれが起こるのかの判定できれば良くて、計算量自体はメモ化で割と富豪的な解法が通ると思います、進み方的にx + y と x - yの両方が必要です、　ぶつかるボールはlower_boundで良いですと合意した所、この時点でEの実装が終わりました。
その後Fの実装にchoさんが向いました。

そこから暫くして、WAの出るコードをプリントしたchoさんが帰って来ました。筋は知っていたので正当性を確認しようとコードを見たのですが、再帰関数にすると再帰が深すぎてスタックオーバーフロウするらしく、その全てをループに展開した結果A4用紙3~4ページ程度に渡る実装が書かれていて、頭を抱えてしまいました。
この時点で残り時間が1時間弱程度で、Gもotoshigoさんがそれらしい予想解を書き始めていた事から、私がFを1から実装する or Gを詰める　の何方を取るかを迫られたのですが、Gに見通しの良い証明が無く、かつGの強そうな解が手に入った事から、いくつかのコーナーらしきものを口にして私はGを見ました。

G

ぱっと見では中々新鮮な感じのする問題で、過去の記憶を遡っても似た問題が思い当たらず、嫌な感じがします。
otoshigoさんは方程式にして解いていたので、私はそれらの考察に対する反例や「このケース考えていますか」という事を投げたりしながら全探索を考えていたのですが、半ば投げやりな仮定をしたとしても間に合いそうになく、これは綺麗な形の解を用意するしか無いかもなと思い始めました。
他に問題の言い換えや簡略化も思い当たらず、その時点で中々手詰まりになってしまい、otoshigoさんの考察を後追いする形で考えたりもしましたが、良い案が見つかりません。
その後、かなり雑な構築をする事で一部のケースが解ける事がわかり、続けてotoshigoさんの予想解が正しそうだとも思い始めましたが、特に軽い実装も思いつかず、どうしようも無くなってしまいました。
しかし、Gの実装もバグっているそうです。
その後、配列外参照のエラーに対して「デバッガはここら辺がバグっていると言ってます」と言ったり、考察の過程で作った強いテストケースを探しながらGのデバッグに参加していたのですが、デバッグを完了する事ができず、結果F, G抱落ちという結果に終わってしまいました。

追記:
(私基準で)似た問題を過去見た事が有りました...
ネタバレを含むかも知れません

感想

DPやデータ構造・グラフの問題等私が好む問題に向き合う事ができず、苦しい感じがしました。
そう言った意味ではFの重実装が唯一の得意枠だったのですが、それすらも余人に投げてしまい、かつ途中のswapチャンスも断ってしまったので、一体何がやりたかったのだという動きになってしまいました。思えば、実装が爆発した事によるswapの決断をどうするか、チームで合意しておくべきだったかもしれません。
どうしましょうか。それはともあれ、ありがとうございました。また、お疲れ様でした。