2022/07/08に開催された ICPC 2022 国内予選に、大学の先輩2人とチーム【thorny castle 】を組んで参加しました。
そして、結果は4完で47位。
https://icpcsec.firebaseapp.com/standings/
公式の発表はないので手計算での集計ですが、おそらく国内予選を通過しました！
ICPC 2022 国内予選 結果 | ICPC 2022 Asia Yokohama Regional
国内予選を通過したと正式に発表されました！（7/14更新）
私は今回先輩に誘われてのICPC初参加でしたが、こうした大舞台で結果を残せたのは本当に嬉しいです。
この記事では、その思い出の記録として、大会での大まかな進行や私が関与した問題での会話の内容等を書いていきます。（先輩2人の呼称は「先輩A」, 「先輩S」とします。）
大会の参加形態
本大会はオンライン開催と言うことで、まずチーム3人で集まるか各自自宅等で通話しながら参加するかを選ぶことができました。
最初は大学の理学部棟で一部屋借りようかという話でしたが、昨今の大学全体のwi-fiの不安定さを考慮して各自自宅から参加ということになりました。（こんな理由で集まるのを断念しているチームはうちだけなのでは？？）
作戦
初動でA,B,C問題を3人で並列して担当し、以降は流れで解けそうなやつを頑張ろう、という感じ。
AtCoderのレート順で、私はA問題を担当することになりました。ゴリッゴリの早解き勝負です。ﾑﾘ…
問題のページ↓ （問題の内容把握は記事内では省略します。）
大会中の私がやったこと
- A問題-全部
- D問題-考察
A問題
やるだけ問題。一目見た瞬間から実装開始。しかし、往々にしてこういうやるだけ問題では実装の速度が顕著に表れるもの。お隣の46位、48位のチームはどちらも3分台でACしていますが、私は6分弱かかってしまいました。反省。
何はともあれ初動の並列パートを突破したので、とりあえずD, E問題を眺めることにしました。
D問題
しばらくして両先輩もB, C問題を突破。ここからは先輩SとD問題を考察し始めました。以下は会話形式で考察の過程を書きます。
私「tを後ろから見ていけば入場する列が構築できそうな気がします。」
先輩S「あー、行けそう。」
先輩S「なんかdpやりたくなるけど遷移ヤバそうじゃない？」
私「いや、縦に置けるのはsで連続で並んでるときだけなので、高々遷移は2通りです。」
先輩S「確かに。じゃあdpには『今何列置いたか』を持って…ああでも『それまでの各列の先頭にある値の最小値』を超えていると横には置けないから、それも処理しなくちゃいけないのか。」
私「あー…」
先輩S「dpの状態に『それまでの各列の先頭にある値の最小値』を持ったとしても、もしその最小値を隠すように大きい数字を縦に置いた場合、そのとき『各列の先頭にある値』がわからないから最小値の更新ができない。困った。」
私「うーん…」
私「『縦に並べるときに最小値が更新できない』のは、今置いた数が先に置かれてた数よりも大きいときですよね？」
先輩S「そうだね。」
私「その場合って、横にも置けないですよね。だったらなんか事前に処理しておくこととかってできませんかね？こう…ニコイチに纏めるとか…」
先輩S「つまり、tで単調減少の部分がsでも連続しているなら縮約しておく…？」
私「縮約…それって操作後はtが単調増加列になったりしません？」
先輩S「例えばt = [3, 1, 2] で考えると、3, 1を縮約してt = [3, 2]になる。これをまた縮約してt = [3]になる。確かに単調増加列にはなると思うけど、こんな操作していいのか？よさそう（自己解決）」
私「ええっと…確かによさそうですね。」
先輩S「単調増加列になると何が嬉しい？」
私「後ろから見れば単調減少列なので、最小値とか気にせずとも必ず横に並べることができます。」
先輩S「なるほど！じゃあ列の数だけ持ってdpできる！」
私「勝った！！」
というわけで、先輩Sが実装して無事ACしました。
ベンチ温めタイム
E問題で先輩Aと合流。
先輩S「これ無理くないです？」
私「なんですかねこれ…線形計画…？」
先輩S「いやー、こんなキモい牛ゲーやりたくない。」
私「カッコ列…」
先輩S「二次元カッコ列dpとか聞いたことない。」
先輩A「二次元カッコ列dpwww」
と言った雑談をしつつ、
先輩A「1の列または行は、最初は確定で+、最後は確定で-。」
私「0の行と列の交差点は-にしてよさそうです。」
先輩S「あとは『枝刈りdfs書いて実は間に合います』くらいしか思いつかないですね。」
と考察を進めつつもタイムアップ。
感想
個人的な出来栄えについては、そこそこ頑張れたんじゃないかと思っています。特にD問題の考察パートは全てを出し切った気がします。
ただ、実装についてはダメダメでしたね、A問題は早解きと言えるスピードではありませんでしたし、D問題は自分も実装してはいましたが、あまりにも遅すぎて結果的に先輩に任せてしまうような形になってしまいました。
先輩方には頭が上がりません。B問題は実装がかなり重そうで、C問題はなんだか難しそう（小並）。もし私が担当していたら通せた自信は正直ありません。
全体の感想としては、通話での思考の共有の難しさを実感しました。D問題の考察を会話形式で書きましたが、実際あれを口頭で実行していました。なんで意思疎通できたんでしょうね？
アジア地区大会への意気込み
アジア地区大会は、12月に横浜にて開催される予定です。
ここで、重大な問題が一つあります。アジア地区大会での問題文は全て英語なのですが、チーム全員が英弱と言うことが発覚しました。終わった…。
昨年度の問題をちらっと見た限り、正直僕レベルのなんちゃって競プロerでは手も足も出なさそうな雰囲気がありますが、まあ出るからには全力を尽くしたいです。頑張ります。
それではこの辺で〆ます。最後までお読みいただきありがとうございました。
