ゆらのふなびと

競プロ, Python, C++

ICPC 2017 アジアつくば大会 参加記

ACM-ICPC 2017 Asia Tsukuba Regional | 国際大学対抗プログラミングコンテスト2017アジア地区つくば大会

に参加した.

<= 0 日目

10 月に入ってから,できる限り週 1 回チーム練をしていた. ただし毎週 5 時間は長いのと,初動が大事ということで 3 時間でやっていた. 問題セットは Virtual Arena から会津大学の人が作ったセット等を使わせてもらっていた. 海外の ICPC 地区予選の問題が多かったが,アメリカのセットの "ワクワク" さに辟易したので他のセットを探すことに *1. ヨーロッパのセットの評判がよかった *2 ので,NEERC 2017-2015 をやった. 実際割とよかった. イエローに近いブルーくらいの人は解いて損はないと思う. 制約やジャッジが間違ってるとかいうことも特になさそうだった.

キーボードは Yazaten が US 配列を持ってきてくれたのでそれで練習をした.

本番は 5 完できたらいいなあとか考えていた.

1 日目(エクスカーション)

JAXA に行った.

でかい人工衛星・ロケット等を見れて楽しかった. 「きぼう」の管制室も見せてもらった(写真は禁止だったのでなし).

夜は懇親会&チーム紹介(1 枚のチーム紹介スライドを前に表示しながらチームメンバーが前に出て挨拶するというイベント)があった. 競プロ er というと Twitter でワイワイしている人種 && HN で呼び合うのが当たり前という認識だったが, スライドが写真+実名な人々もおり競プロ / ICPC の広さを知った.

寿司…….

2 日目(コンテスト)

早起きしてスタバにいたらライブラリのバグを見つける *3

ライブラリはちゃんと確認しましょう!

弊チームの初動は以下の通り.

  • Yazaten: テンプレを打つ
  • yurahuna: A を解く
  • ratea: B を解く

Yazaten がテンプレ担当なのは一番タイピングが速いからで, 僕が A なのは英語を読むのが一番速い(と認定された)ため.

A: 僕が読んだ. 「DP っぽい」と言うと Yazaten に「さすがになくない?」と言われたので考え直す. DP じゃない解法を思いついたので書く.AC. なお想定解は DP だったらしく,例年の難易度からすると A 問題から DP とは……と驚いた.

B: ratea が読んでいたが幾何っぽいとのことで幾何担当の僕に回ってきた. 幾何はそれほど本質ではないが,幾何だと伝えられたおかげで平行の判定を外積でやることを思い出せたのはよかった. 提出するが WA. typo があったので修正して再提出するも WA. トイレから帰ってくると嘘解法であることに気づいた*4ので bitDP の方針で考え直す. 計算量が大丈夫なことがわかったので書く.AC.

C: Yazaten が書いていたが答えが微妙に合わず苦しそうだったので一緒にデバッグ. 式が合わないと言っていたので二分探索したらどうかと提案した. それでも合わないので 2 人でソースコードとにらめっこしていたら, 0-index と 1-index が怪しいところを見つけたので直す.AC.*5

I: 順位表的に解かれていたので見る. この問題は 2 種類の答えを求める問題で,片方については ratea がは解法を出してくれていたので,もう片方を一緒に考えた. なんか言い換えると max_i {区間 i と共通部分を持つ区間の個数} を求めればいいことに気づいたので書く. 微妙に端をバグらせて困ったので,弊チームの実装担当こと Yazaten に書いてもらって AC.

F を Yazaten が読んで解法を出してくれていたが,終了 15 分前で実装する時間がないので終了.

結果は 4 完 30 位. F まで解けそうではあったものの,ABC が重すぎたので仕方ない感がある. I 問題は 3 人で解いた感があり,チーム戦ならではだった.

コンテスト終了後は順位発表と表彰式があった. Yes / No おじさんを生で見ることができ感激 *6. I が凍結後に通っていたので,弊チームも Yes! の :clap: をいただく.これは結構嬉しかった.

その後は懇親会その 2 +企業ブースがあった. 競プロに理解のある会社が来ているはずなので,競プロで就活したい人にとってはいい機会だと思う. 昨年は各企業がこぞってパズルを出していて,参加者は食事そっちのけで没頭していたらしいが, 懇親の妨げになるとのことで今年は縮小されたらしい.

寿司…….

3 日目(企業見学)

行ってきます.

>= 4 日目(これから)

僕は今回が初めての ICPC でしたが,年齢制限のため今年で引退です. 競プロを始めたのが B4 の 12 月と遅かったのですが,幸いにも ICPC アジア地区予選に出ることができいい経験になりました. 関係者の皆さんありがとうございました. チームを組んでくれた Yazaten, ratea, コーチの shora にも感謝します.

今後は JAG 等を通して ICPC / 競プロ界に恩返しをしていければと思います. 現役の皆さんは今後ともぜひ頑張ってください. ICPC 引退した皆さんは一緒にじゃぐじゃぐしましょう.

おまけ

昨年度 NJPC 2017 というコンテストを開催しましたが,2018 をやるかもしれない *7 のでそのときはよろしくお願いします.

寿司…….

*1:問題が虚無,出力にゴミが入っている,怪しい解法が通る etc.

*2:JAG 夏合宿 2016 のセットとしても使われていた

*3:作る時にコピペし間違えたらしい

*4:2乗和なので貪欲に大きいグループを作ればいいとか言っていた

*5:0-index, 1-index 問題は競プロ永遠の苦しみ

*6:Yes / No おじさんはサンタクロースと同じで,世界各地に偏在しているらしい

*7:検討中