feature image

2023年7月9日 | ブログ記事

ICPC国内予選2023参加記(Nzt3視点)

概要

チーム acidrainで出場し、東工大内3位、全体13位。
想定外の高順位で嬉しい!

メンバー

otoshigo, Sotatsu, Nzt3
Python使いとC++使いが混在したチーム

チーム名 acidrain

チーム名決めよう通話をしているときに私がNとSとOを見て「酸性雨の原因になる」とか言ったら採用されてしまった。本当にこれでいいの?

当日までの準備

チーム確定後は毎週2回チーム練習をした。合計で7回+模擬国内の8回チーム練習をしたはず。

模擬国内の事故

コンパイルコマンドがわからなかったので g++ A.cppを使っていたらC++11以前になっていてusing ll=long long;constexpr も動かなくて厳しい気持ちになった。

国内予選当日

開始前

模擬国内の反省を活かしてコンパイルコマンドを印刷した。これでC++20が使えるし最適化もかかるようになる。リハーサルでWA,プログラム変更,ACを試す、コンパイルコマンドを試す、使いそうなヘッダファイルを入れてみるなどをして非アルゴ部分で死なないようにする。teeコマンドとか初めて使った。
私はまともなライブラリを持っていなかったので蟻本とthunder本とアルゴ数学本を持ち込んだ。写経の簡単なACLをくれ。

開始直後

開始と共にICPCディレクトリを作るが、開けない。一度VSCodeを終了して開き直す。

テンプレ写経~AB

画面を分割しVSCodeとA問題を映しながら私がテンプレを写経、コンパイルコマンドも最低限のC++20指定と最適化を写経。写経中にAが解けたらしいのでB問題を映す。
写経が終わり次第otoshigoがAを書き始める。SotatsuはBを解き、私はCを読み始める。
Aが通り、SotatsuがBを書く。
Aを通したotoshigoにCの考察を共有。
私 「市松模様に分けて、端から並べたら良さそう」
otoshigo 「良さそう」
BでWAが出る。実装方針を聞きに行くとすぐに自力解決したらしくAC。

C

市松模様の正当性はまだ証明できていないけどCの実装を始める。順位表を見るとSpeed Starが2ペナしていたのを見てジャッジも書くことにする。ジャッジで全て正しいことを確認して提出。AC。

C通した直後の会話
Sotatsu 「幾何(F)と2乗の期待値(G)どっちがいい?」
私 「2乗の期待値で」

D

otoshigoがDを実装。
Dの方針を聞いた私「(全探索は、やばくない?)」
その間にSotatsuがF、私がGを読む。
Sotatsu「Eが残ってた。こっち読んだ方がいいです」
私がGを捨ててEを読む。
Dが爆速実行され、通る。
Dが通った直後の私「(私の実行時間見積り、弱すぎ!?)」

E

Fの考察ができたらしいのでSotatsuがFを実装する。
otoshigoと私でEを考える。
Eのnの総和に関する制約がキモすぎるが、2乗が通りそうに見える。5乗のDPなどを生やしていると、2乗のDPが生える。
Fが実装完了しテストケースを回す。かなり時間がかかりそう。
Fを裏で回しながら私がEを実装。途中でFの実行が終わり提出するがWA。

Eのサンプルが合わない、遷移の数が足りませんでした。修正してサンプルを合わせる。そのままAC。

コンテスト終了まで

Fの考察漏れを3人で共有し、Sotatsuが実装する。
3人でFの実装を詰める。
書き上げ提出するがWA。
実行速度を考慮してotoshigoがC++で書き直す。
GHを通せるような時間はなかったので私とSotatsuは応援に回る。

Fの実装が終わらずコンテスト終了。

コンテスト後

何もなければ予選通過なのでthunder本と一緒に写真撮影

反省点

幾何ライブラリを作ろう!
アジア地区までに使えるライブラリを用意する。

Nzt3 icon
この記事を書いた人
Nzt3

23B algo|CTF|SysAd 競プロer

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2023年9月26日
traP コンペ 2023 夏 sponsored by ピクシブ株式会社 運営後記
abap34 icon abap34
2023年7月13日
アルゴリズム班はやとき王選手権「競(けい)プロ」を開催しました!
abap34 icon abap34
2022年10月11日
アルゴリズム班にKaggle部を設立し、初心者向けデータ分析体験会を開催しました!
abap34 icon abap34
2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2023年7月5日
Kaggle部で機械学習講習会を開催しました!
abap34 icon abap34
2023年4月29日
CPCTF2023 PPC作問陣 Writeup
noya2 icon noya2
記事一覧 タグ一覧 Google アナリティクスについて