ICPC2023模擬国内参加記

2023/06/24に開催された模擬国内にチームtsurataNで参加しました。

メンバーはN_haraさん、pitsuさん、僕(tardigrade)です。

ICPCはitigoさん、pitsuさん、僕で参加しますが、itigoさんが学会の発表で予定が合わなかったので、代わりにN_haraさんに来ていただきました。

結果はABCDEの5完で16位でした。

～コンテスト直前

大学内の図書館の一室を予約していたんですが、色々あって開始2分前くらいまでドタバタしていました。

なんとか時間通りに始められて良かったです。

コンテスト開始直後

pitsuさんが問題文を印刷しにいって、他二人がA問題を見るという立ち回りでした。

A問題

はい。N_haraさんが綺麗に実装してくれて難なくAC。

実装している間に問題文の印刷が終わったので、僕がB問題を、pitsuさんがC問題を眺めていました。

B問題

A問題を通した後ノータイムで実装に移ってこれも難なくAC。

普段US配列を使っている関係で、僕は実装をしない方針だったので、pitsuさんに考察を話して実装してもらいました。

実装しないならBをpitsuさんに見てもらったほうが良かったかも。

C問題

pitsuさんがB問題を実装している間にN_haraさんと二人でC問題を考えていました。

僕「上二つだけ使えば良さそうですね」

N_haraさん「あ、ほんとだ。じゃあ121212....111...みたいにするのが最適ですね」

僕「え、天才です」

B問題を通した後、これもほとんどノータイムで実装に移ってAC。

オーバーフローでペナを吐いたので、「本番はlonglongだけ使おう」という話になりました。

ちなみにこの時点で全体2位で、結構びっくりしていました。

D問題

N_haraさんがC問題を実装している間にpistuさんと二人でD問題を考えていました。

pitsuさん「DPっぽいな～」

pitsuさん「こんな感じかな～」

僕「すごい、良さそう」

pitsuさん「でも10**11くらいかかるね～流石に遅いかも」

この辺でCが通ったので、とりあえずpitsuさんに実装を始めてもらいながら、N_haraさんと高速化の方法について考え始めます。

僕「累積和を持ってこんな感じでこうすると256のループが一個削れて高速化できます」

N_haraさんpitsuさん「「ほんとじゃん」」

これでDが通って4完です。

E問題

幾何というよりは数学問題だね～という話に。

僕「傾きの近似みたいな感じ？上からと下からでいい感じに抑えたいですね」

↑が良くない方針で、かなり時間を溶かしました。反省。

～～残り20分くらい～～

僕「これ、最短は絶対1/a（厳密には違うけどお気持ち）になりそうで、そうなるとこの一次不定方程式が解ければよさそう？」

↑天才をしました。偉い。

N_haraさん「拡張ユークリッドの互除法ありますよ～」

pistuさん「実装しますね～なんか返ってきた値の絶対値を取るとよさそう～正当性わからないけど時間ないし絶対値とって出してみますね～」

N_haraさん僕「「まぁこんなテキトーで通らないですよね～」」

pitsuさん「通った！」

これで5完です（え？）

終わり

int型は使わないようにしよう。

模擬国内の運営に携わってくださった皆さん、急遽ヘルプで入ってくれたN_haraさん、ありがとうございました。

国内予選勝つぞー！