ICPC2019 アジア地区大会 参加記

 

TLDR

ICPC2019アジア地区大会に、チームPICOPICOPONとして参加して6完11位でした。結構エモい気持ちになったので、来年の自分がエモい感じを思い出せるように、参加記を書こうと思います。チームメンバーは、yamad, lgeuです。

 

大会前

チーム結成時(5月)

PICOPICOPONって、二郎系のラーメン屋さんの名前らしいですね。チーム名が決まって数ヶ月後に知りました（え）

 

5ヶ月前(6月)

チームメンバーのlgeuが黄色になりました。よって僕は、チーム内唯一の寒色コーダーになってしまいました。僕はレート1950くらいの頃でした。

 

2ヶ月前(9月)

2週間ほど競プロに沢山集中できる期間が出来たので、分野を絞って全力投球しました。選んだ分野のきっかけはこちらです。

具体的にはこんな感じで、クエリ関係の知見をまとめてました。

  1. 学習に使えそうなサイトまとめ
  2. 学習において実際に解いた問題, 知見のまとめ
  3. (途中で思い付いた、後でやろうと思った分野のまとめ)

自分用だったので公開しようか迷ってたら今になりました。正直beetさんの記事が強すぎるので。

f:id:toa25:20191119041458p:plain

 

2週間前(AGC040)

 なんとかギリギリ黄色になりました！これにてチームPICOPICOPONは全員黄色コーダーでアジア地区大会に臨めます！

 

 1週間前(全統一コン)

Q「What's this ?」

A「This is SOKUOTI NIKOMA」

 

大会1日目

朝

早解きの感覚を思い出すため、少し前に告知のあったPASTの問題を解いてました。既に解いていた問題ばかりだったので、2時間で88点取っておきました。最後2問やってたらICPC遅刻しそうなので解いてません。

 

昼

集中モードに入り始めました。うぉおおおおお！

環境構築で色々確認していたら、リハーサルは2完でした（完）

 

夜（ABC145）

本番直前大逆転勝利です。ちなみにチームメンバ―全員が全完して寝ました。lgeuはCodeforcesにも出るって言ってて凄いなぁって思いました（小並感）。

 

 大会2日目

朝

「あーたーらしいーあーさがきたー　きーぼーうのーあーさーだ」

珍しく目覚めが良くてびっくりしました。目覚まし無しで午前7時起きです。

1時間くらい時間があるので、なろう系の漫画を読んでました(ふざけてるように見えるので、チームメンバーからは隠れて読んでました)。俺つえー系の精神、僕の場合は競プロでプラスに作用する傾向にあったので、漫画を読むことで緊張を吹き飛ばしてました。実際精神が潰れそうな緊張じゃなく、心地よい緊張になりました。

その後はコンテスト開始まで無難に行動したので割愛。

 

0:00 (コンテスト開始)

初動は、yamadが環境構築、tomaがA問題、lgeuがB問題で臨みました。

以下、toma目線でのコンテストの模様です。

 

0:21(B問題AC)

A問題を速攻で書くと、高確率でミスってWAが出そうだったので、先にlgeuにBを書いてもらいました。本当に一瞬で凄いなぁと思いました（小並感）

 

0:26(A問題AC)

Bを終わらせたlgeuを巻き込んで、0WAでAのACを取ろうとしました。実は入力に1を足すことで、while文1個と、簡単な式5～6個が本質になる問題だったので、5分で書いてデバッグ入出力を見てAC出来ました。

 

1:38(H問題AC)

yamad, lgeuが頑張って解いてました。問題概要をコンテスト後に聞くレベルに何も知りません。3人で解くようなものではないとのことで、僕はCDGI問題をもくもく読んでました。

 

2:31(E問題AC)

このタイミングではEが一番容易なので僕も解いてました。物凄くDPなので、最長増加部分列などを調べながら、どういう遷移なのか考えてました。するとlgeuが「二部グラフ？」って呟いて、僕も特に反例は見つけられなかったので、yamadが実装しました。

 

3:28(G問題AC)

文字列問題だったので、初動で読んだ後、多分yamadの得意分野だろうと投げてました。実はダイクストラだったので、EH問題をyamadが解いている間にもっと考察を進めれば良かったと反省してます。

 

4:33(I問題AC)

初動

完全にグラフ問題です。実は大会前に、HL分解が出たら僕が頑張るみたいな話をしてたので考えました。木構造だと、根付き木にしたあとに経路上の必須順辺に1, 必須逆辺に-1のラベル付けをすれば良いので、HL分解をコピペすればやるだけに帰着できます。実は木構造じゃなかったのでHL分解は使えず泣きながらE問題などを読んでました。

 

転機

途中でyamadに概要を伝えると、queryをDAGにする提案を貰いました。それをlgeuに横流しすると、ループを作れば良いじゃんという話を貰いました。

その後、クエリによるDAG上のループを元グラフにパース出来ないかを考えていると、「9月に集中して解いてた帰省ラッシュが類題では？」という意味不明な閃きをしました。

f:id:toa25:20191119052619p:plain

 この問題はどういう問題かというと、二重辺連結成分分解をした後に、二重辺連結成分をノードとする木をHL分解して頑張ってくださいという問題でした。二重辺連結成分分解の後が木になることなどは、同じく9月にAtCoderの解説で学んでました。

f:id:toa25:20191119052933p:plain

そこでyamadに「二重辺連結成分において、任意の頂点から任意の頂点に到達可能なグラフの向き付けは可能か？」と聴いたらYesと返ってきました。そうなれば話は簡単ですね。初動で考えてた方針は木構造なら達成可能です。そしてグラフを二重辺連結成分分解によって木構造に落とし込むことができました。範囲に1や-1を加算するのは、HL分解の得意技です。これにて終了！以上をyamadに実装してもらいましょう！

 

実装

と思ってたのですが、流石にHL分解は不要だったらしいです。実際にはLCAまでのルートに+1, もしくは-1をするだけだとyamadに伝えると、いもす法で余裕という話だったのでその方針で実装してもらいました。

最終的にコードが完成したタイミングで終了30分前で、バグらせていたら5完終了の恐れがありました。怖かったのでWAが来たとき用に一応テストケースを8通りくらい作ってましたが、1発ACが来たので杞憂でした。

 

5:00(C問題まにあわない…)

I問題が上手く行きそうで喜んでいた所、C問題をlgeuが完全に解いてました。I問題ACは終了27分前ではあるものの、ギリギリ行けるのではという見込みでyamadが実装していました。結局間に合わなかったものの、後20分くらいあればACしそうという状況だったらしいです。

 

結果発表

 最終的に6完11位でした。昨年世界大会に行った同校のWAsedACが10位だったのでギリギリ勝てませんでしたが、十分健闘出来たと思っています。 

僕個人としては、A, I問題には貢献出来たので嬉しかったです。まさか9月に木上クエリ系を全力で頑張ったことで、人類に解ける問題のうち3番目に難しいI問題の考察が出来るとは思ってませんでした（リアル伏線回収）。

（ただ途中のEGHに全然貢献できず、最終的にC問題に時間を残せなかったのでそれが悔しいです。最後の最後でI問題のACを疑って反例検知やテストケース増産に執着しすぎて、C問題の助っ人に入れなかったのも悔しい）

f:id:toa25:20191119054948p:plain

 

景品

11位になれたので、いい生活さんとレトリバさんから色んなものを頂けました！特に、いい生活さんのホワイトボードが凄いんですよね。ホワイトボード4枚が上端だけ磁石でくっついているんですよ。そしてペンも4つ。

ICPCの実戦練習の際に、1人1枚ホワイトボードを使って考察や情報共有が出来て、残り1枚を全体進捗確認に使えるという丁度良い枚数なのです。これが全員に渡されているので凄い。

その後は直帰して寝ました（3日目の企業見学は朝10時集合なので）

 

大会3日目

楽しかった！イルカさん　ヾ(*´∀｀*)ﾉｷｬｯｷｬ

（写真撮影出来た分だけツイートしてます。）

 

あとがき

ICPC楽しかったです！

来年はもっと楽しくなるよね、ハム太郎？

 

ということで、来年がもっと楽しくなるように精進します！