国内予選に引き続きsuzukaze_Aobayamaの一員としてicpcに参加した.
チームメンバー
karinohito(私): 数学, 発想問担当
milkcoffeeさん: 最適化やDP等々担当
sotanishyさん: 幾何とか知識系データ構造等々担当
本番nか月前
大会のルールが出る. 並列実装禁止, 事前ライブラリ禁止. 去年の国内&アジア, 今年の予選を全て並列パワーで戦ってきたチームなので困ったねとチームメイトと言い合う.
練習
模擬地区
初めて実装1台ルールでやった.
結果: 実装キューが詰まりまくり.
慣れないキーボード, デバッグも実装PCでしなければいけない, ライブラリの仕様の理解の甘さなどがあり, 開始2時間で済ませた考察を最後まで実装しきれなかった.
順位は6完16位. 順位自体はまずまずなので練習を繰り返しして慣れようという話に.
模擬地区以降
(ほぼ)毎週末こどふぉのジムにチームで潜った.
面白い問題もあれば不快なコンテストもあって面白かった
実装に少しでも詰まったら印刷(練習中は別端末に共有)する, デバッグもまずは印刷, 基本的には考察→実装を各問1人で行うなどの戦略を立てていった.
並走に参加していただいたチームの皆様ありがとうございました.
その他暇な時に個人で5時間走ってみて途中で力尽きるということを2回ほどした.
ライブラリ周り
普段ライブラリはACLか人の先人の賜を改変して使っているので, 短いコードは持っていないし作り方の知識もなかった.
頑張って多少短くしていたらチームメイトがかなりまとまったライブラリ集を作っていたので私もそれを利用することにした.
本番2日前
2022年最後のセミナー発表終了. その後午後からチーム練習をして解散.
荷造りをしたら鞄がパンパンに膨れ上がってしまった.
本番1日前
起床チャレンジ成功. チームメイトもそれぞれ起床成功したらしく, 仙台駅に集合. 新幹線では爆睡して気づいたら東京付近に来ていた.
このあたりで東北勢で合流したので一緒にお昼を食べる.
写真は取り忘れたが, 高菜明太パスタを食べた.
そのままの流れで会場入り.
KOSMOSチームのモールス信号を手作業で解読していたらリハーサルが始まる時間になった.
リハーサルは過去問だったので記憶を頼りに解いてその後はキーボードに手を鳴らすため写経の練習をしていた. 深く押し込むキーボード嫌いだ～～
チーム紹介ではチーム名の由来を喋った.
スライドのロゴはチーム名の元の『NEWGAME!』をまねて作った.
夕食は中華街に繰り出して中華を食べた. 折角なのでという事で普段食べないようなものも食べた. 途中から写真を撮り忘れたので珍しい方(北京ダック, 鮑等)は何も記録に残っていなかった.
ホテルはチームメイトと相部屋.
することも無かったのでチームで赤diffの問題を考えた. 余りにも眠かったので半寝の状態で適当な事を言っていたらチームメイトが解き切っていた. すげ～.
その前か後かには散歩に行きハマスタの前まで行った.
本番直前
起床チャレンジ成功.
朝食はホテルのを食べる.
会場入りも特に問題は無し.
コンテスト本番
開始直後
事前の取り決め通り,
milkcoffeeさん: 環境セットアップ
sota君: A問題
kari: B問題
から手を付ける.
中盤に置かれると思っていたインタラクティブがいきなりBにいて驚いた.
インタラクティブにあまり慣れていないのでしばらく分からなかった.
経験上インタラクティブは制約から考えると考えやすいというのがあったため, をぐっとにらむと,
な気がする. 実際桁ごとに二分探索をすれば良さそう.
手元で試すために制約を変えていたのを忘れていたり境界をミスったりして2ペナ+50分弱かけてしまった.
1時間経過くらい
早々にAを通したSota君とmilkcoffeeさんがFを解いていてmilkcoffeeさんの考察がかなり筋が良いところまで行っているらしい. 自分は数え上げっぽいIを中心に色々な問題に一通り目を通すことに.
Iは自分が解けるなら積の和的な言い換えorFPSが出来そうな感じがするので色々式をいじってみる. かなり整った形の式を得られたものの, それ以上進展できない.
Dは判定を高速化したり処理をちゃんとやれば気合でなんとかなりそうという. 判定を高速化はハッシュとかで行けるか? とか考える.
そうこうしているうちにFが通った報告を受け, 一旦実装queueが空になる.
ここで考察を共有すると, やはりDは気合で何とかなりそうという感想になり, Sota君がそのままDを書いてみることに.
他のチームがGをかなり通していたのでmilkcoffeeさんと考える
2時間~3時間経過くらい
Gは大まかな方針がたったのでmilkcoffeeさんと共有.
大体良さそうでSota君が実装に詰まっていたので一旦現状の考察をもとにGを書くことに.
ここからは, 結果が合わない→考察漏れが見つかる→直すを2~3回繰り返す.
最終的に, かなり解けそうな部分問題が解ければOKな感じになったので, 共有したところSota君から解法を投げてもらえたので実装.
デバッグに苦労したものの, 自作サンプルも含めて全て合ったので投げる. 通る. 安堵.
3時間半経過くらいから終わりまで
順位表情報で残り通せそうなのがD,EのみっぽいのでEを考える.
まあDPだろうとはなるが, 遷移が面倒そう.
そこでまずは遷移先の判定のため文字列がICPC-ishとなる条件を考えると, 前から 文字中の 'I' , 'C', 'P' の数だけを見れば判定できそうだと分かる. さらに出て来た不等式を整理すると, 遷移前の位置に依らないパラメータによって判定できることが分かる.
よってこのパラメータ毎にDPの値が管理できて, 遷移が無事に行える.
解けた興奮そのままに解法をmilkcoffeeさんに伝え, ちゃんと解けていることを確信したため, 紙にcoding. その後, 実装をしたところ一部合わない. 似た処理をループでなくコピペで実装したため, そこだろうと思って印刷デバッグ.
見つけた修正点を直して提出.
計算量がギリギリなので中々ジャッジが返ってこない.
時間がもったいないので引き続きSota君がDの実装をする.
この待ち時間が本当に長く感じた.
待つこと数分(もしかしたら1分未満だったかもしれない), Correct Answerが返ってくる. 歓喜.
BやGで実装ミスで時間を掛けてしまったのでEで貢献できて本当に良かった.
最後は3人でDのデバッグをする. だいたいのサンプルが合うところまで行ったが, 落ちる原因を特定できずコンテスト終了.
コンテスト後
閉会式やスポンサーの話があったがずっと頭がふわふわしていた.
その後は解説を聞く. 順位表マジックによって想定難易度と実際のCA数はかなり相違があったらしい. 解説を聞くとH問題がかなりの可能枠だったらしく, 完全な結果論だがとても悔しい.
Yes/Noはかなりのチームが順位を上げていて焦るが, Suzukazeも凍結後にEを通したことによって順位UP.
最終的には5完13位であった.
懇親ではバチャで並走してくれたチームとかに挨拶ができたので良かった.
来年に向けて
来年も恐らく同じチームで出られるであろう.
学内トップに君臨していたAobayama_dropoutは今年で解散とは言え, 国内予選でsuzukazeと同じ完数に東北大チームが数チームいたので予断は許さない.
今大会は全体的に自分の実装力の甘さが出てしまった気がする.
普段の自分は大まかな考察ができた時点でとりあえず書いて, その後デバッグと考察詰めをするというスタイルである. 個人戦をする分にはこれが自分には合っているが, 共通PCだったりコードの共有する場合には向いていない. 来年はこのあたりの練習を早い段階で練習をしたい.
最後に
運営の方々及び応援してくださった皆様方, 共に戦ったコンテスタントの方々, ありがとうございました.
本年もsuzukaze_Aobayamaをよろしくお願いします.
