NOSSの雑記

主に競プロでやったことを書きます。

ACPC2018 参加記

参加記 AOJ

ACPC2018

9/19~9/21の3日間会津合宿に参加してきました. 運営の会津大、立命館、北大のみなさん、スポンサーのfixstarsさんありがとうございました.

Day1

会津大の会場に集合30分前に到着. 名札を受け取って空いている席へ. この時点では参加者の中に知り合いがまったくいなかったのでめっちゃ不安に思いながら座ってました.

13時になるとほとんどのひとが到着したようで自己紹介フェイズに入りました. 全員一通り終わると今度はチーム分けが始まりました. チーム分けは実力が平均的になるように参加者を青上位以上、〜水上位以上、その他のレートで3つのグループに分割して各グループから1人ずつランダムに選ぶという方法で行われました.

コンテスト(立命館大学セット)

コンテストのリンク

  • チーム名: acpc_dnb (drkenさん、べるさん、NOSS)

    • チーム名は3人の頭文字をとってシンメトリーに. まさかdrkenさんと組める日が来るとは思っていなかったのですごくびっくりしました. コンテスト前にべるさんと談笑しているうちに緊張もほぐれてきました.

  • 方針: べるさんがA, NOSSがC, drkenさんがEから読む

    • べるさんがAを通す.
    • 交代のときCの概要をチームに投げたところ 奇数+奇数=偶数 だから片方は必ず2だよねという話で解法がわかりCを書く. AC
    • 他のチームがBを高速でACしてるのを見て簡単な解法があるのでは？と2人が考察しているとA<Bの制約を発見したようでべるさんが実装しAC.
    • drkenさんがEの考察を詰めAC. この間ぼくはDをよむ.
    • Dは右手法で島の縁をマッピングすればいいのでは？と思いつく. が、実装難易度が高いとみて断念. (解説によるとこれが想定解だった)
    • DFSで島全体のマッピングなら実装が楽なのではないかと思い僕が実装に入る.
    • その間2人がF,G,Hの考察. その結果、F虐殺 G実装激重 H解答0人ということで残り通せそうなのはDだけということになった.
    • 一通り実装を終えてデバッグするが思い通りに動かず. べるさんとひとつずつバグをみつける作業に入る.
    • drkenさんもデバッグに加わり必死の修正の結果動くようになったので提出. が、0.3sec超過しTLE. coutが遅いのではという話になりprintfに変更し提出. TLを0.01sec下回りAC!!

CDを担当. 結果はABCDE 5完でオンサイト1位でした!! すごく嬉しかったです. 最後まで一緒にデバッグしてくれたべるさんとdrkenさんほんとにありがとうございました.

コンテスト後

べるさんにB2の早稲田の方々を紹介してもらいました. お互い切磋琢磨しているようでとてもいいなあと思いました.

解散後、駅前のホテルにチェックインし休憩. 近くの富士の湯という温泉でコンテストの余韻に浸りながらゆっくりしました. 富士の湯最高なのでオススメです.

Day2

会津大学10時集合. 1日目同様ランダムにチーム分けされました.

コンテスト(会津大学セット)

コンテストのリンク

  • チーム名: acpc_o3 (tomaさん、oct3さん、NOSS)

    • チーム名は3人とも名前にoが含まれているので.

  • 方針: oct3さんがA, NOSSがC, tomaさんがDから読む.

    • oct3さんがAを通す.
    • 僕がCを通す. oct3さんがB、僕がEをよむ.
    • 続いてtomaさんがDを通す.
    • Eの制約が読めずまあ穴は内包してるだろうと提出するとWA. 内包されない場合もあるとわかり修正. HとWを逆にするバグを埋め込むがtomaさんにデバッグを助けてもらいAC.
    • Bに難航. 3人で考察し実装をoct3さんにやってもらうもWA. オーバーフローを恐れ #difine int long long など悪魔を行う 互いのチームが忖度する考察が誤っていることが発覚. 勝者を決め打ちする方法でAC
    • ここで12:30になったので昼食. 会津生であるoct3さんに学食を案内してもらいチームみんなでカレーを食べる. 食べながらFとGを考察したりoct3さんにグラフの最短経路問題のアルゴリズムを説明したりしながら過ごす. ここでtomaさんがGの解法を思いつく.
    • 会場に帰ってtomaさんがGを実装しAC. その間僕とoct3さんでFの考察を詰める.
    • 代わって僕がFを実装. 制約をよく見ずRE(よくない). 配列を大きくしてAC.
    • Hを考察していると強連結部分分解では？と思いつく. 一応ライブラリを写す.
    • Iがフローだとtomaさんが気づく. 蟻本の写経にはいる.
    • 残り1時間、僕がHの考察をバグらせ永遠にWAがとれない.
    • 残り30分でtomaさんがIをACしていた. プロ
    • 最後はみんなでHをデバッグするも僕の頭がバグっているので叶わず…

CEFを担当. 結果はABCDEFGI 8完でオンサイト6位でした! tomaさんが難しい問題をACしてくれたおかげでかなり順位が上がりました. 僕はEとHのデバッグでチームに負担をかけてしまった(特にEは避けれた)ので反省です. 終盤otc3さんに座るだけをさせてしまったので申し訳なかった.

解説後fixstarsさんのスポンサーセッションがありました. まだインターンを経験したことがないので今度挑戦してみようかな...

懇親会

競プロerが集まって懇親会をやるとこうなるんですね. 基本的な常識をみんなわきまえているのでやばくないウェイみたいな感じでした(?) 僕はお酒を飲まなかったので未飲酒erと話していました.

Day3

会津大学9時集合. 懇親会で二日酔いになっているひともいたようですね. 懇親会のおかげでみんながより仲良くなっていたような気がした.

コンテスト(北海道大学セット)

コンテストのリンク

  • チーム名: acpc_NOSS (hajiさん、reminさん、NOSS)

    • 3人とも青コーダーでレートが近いというチームでした. 一番レートの高い人の名前をチーム名にするはずが偶然にもreminさん=hajiさんだったので間をとって(?)僕になりました.

  • じゃんけんの結果 reminさんがA, hajiさんがB, NOSSがCから読む.

    • hajiさんにCの概要を話しているうちにループが高々1つしかないことに気づき2点がループ内にあるかどうかで判定すればよいという考察に至る. ループ判定も葉をDFSで消していけばいいと思いつき紙実装.
    • reminさんがAを通す
    • 僕がCの実装にはいる. が、途中で実装ミスに見つける. ここでhajiさんのB実装に変わりその間に紙実装を修正する.
    • 修正が終わったので実装を代わってもらいCを通す.
    • hajiさんがBの重い実装を終えAC！これがBのオンサイトFAとなる. その間僕とreminさんはDとEの考察をする.
    • hajiさんにDの概要を話すと見たことのある問題だと言いそのままDPを実装しAC. プロ
    • hajiさんにEの考察を話すと橋の列挙が必要だということで二重連結成分分解のライブラリの写経に入る. これには時間がかかるようなのでその間僕とreminさんはF,Gの考察を進める.
    • reminさんがFの考察を完了させる. 実装も軽いようなのでhajiさんと交代しFを実装してもらいAC.
    • hajiさんがEの実装を完了させ提出、しかしWA. そこでループ内の辺を削除したときの結果も考慮する実装を加えるとAC!
    • 残り1時間で残った問題はGのみ. 3人でGを考察する.
    • 「回文をつくるときは範囲内の同じ文字で一番左と一番右のペアのみ考えればいいのでは?」と思いつきhajiさんに伝えると閃いたようでそのまま実装にはいる.
    • 残り30分でhajiさんが実装を終える. しかしサンプルが合わずDFS内の弾く条件式を変えたり、返す値を±1したりデバッグに悪戦苦闘. 僕はテストケースを生成したりしていました.
    • 刻々とコンテスト終了が近づく中、残り1分でhajiさんがやばい挙動を発見. 急いでそれを弾く条件式を追加しサンプルが通ることを確認して祈るように提出…そしてAC!!! 残り1分で全完し激熱でした.

Cを担当. 結果はABCDEFG 7問全完でオンサイト2位でした! hajiさんが重い実装の問題をやってくれました. ありがとうございます. 最後の1分で3チームがAC、そのうち2チームが全完という激熱コンテストでした.

コンテスト後

解散後goodbatonさんと一緒に駅の途中まで話しながら歩きました. 途中で別れた後、僕は東京行のバスに乗り帰路につきました.

感想

濃密で刺激的な3日間でした. このような合宿に参加するのは初めてで不安だったのですが参加してよかったと思っています. 来年参加できればまた会津に来たいと思います.