ICPC2023 国内予選

icpccompetitive programmingparticipation log

作成日 / 最終更新日

Table of Contents

Loading...

今年も参加しました!ICPC2023 参加記です!

開始前

チーム決め

チーム募集をかける。先輩が抜けてしまったので自分が一番上。
ちなみに、Maximum 内では、私たち含め 4 チーム作られました。

私のチームは「Maximum-executive」。
というのも私が Maximum の代表、 through, kAsA02 は副代表なので「重役」です。
2021「seica is gone」に倣って「m_99 and regi are gone」を提案したけど却下された...コーチは m_99 ですが

システム

国内予選システムを模倣したシステムを React + WASM で作りました!
めちゃくちゃ単純な実装でバックエンドはないので GitHub Pages で動かしています。
バグあるかもしれないので、見つけたら教えてください。

https://github.com/saitamau-maximum/icpc-prelim-system/ (新しいタブで開く)

模擬

国内予選模擬に出場してみた。とはいっても最初の 1 時間半は用事があって参加できなかったんですが...。
結果は 2 完 66 位でした。うーん、本番はもっと頑張らないと...

ちなみに through がほかのチームにログインして 1 WA をするという事故がありました。

ほかの Maximum チームは、作った模倣システムで練習した成果が出たのか、なんなく模擬に参加できた~と言ってました。よかった。

当日

プリント

いろいろライブラリを印刷してきます。
プリンタが動かなくなって焦りましたが、 got kotonaki 。
プリントに加えて蟻本と E8 初本も持っていきました。

会場着

とりあえず応援してね~をいう。

3 限が終わったので、会場に向かいます。
もう何人か来ていたので、時間までだべる会を開催。

そこで ABC317 がゲームフリークのスポンサー回だとざわざわ。
しかも 8/26 、なんと Maximum-Cup の開催日...まじかよ
これは Maximum-Cup の参加者が減る気が...だいじょうぶか?

戦略として、私の PC を使うことになってて、 US 配列で慣れてるのが私だけだったので基本実装は私がやることになりました。

準備運動をして、いざ!ぞい!!

スタート

はい、まず A を見ます。

A

例年いつも通りの for 文使う問題。
まずはディレクトリ作って VSCode を開きます。
一通り書いてコンパイルするも、なんか合わない。

これ誤読してて、 aia_i が最小になる ii を求める問題だと思ってました...
でも実際は aia_i が 2023 に一番近い、つまり ai2023|a_i - 2023| が最小になる ii を求める問題でした。
if (a[minim] > a[i])if (abs(a[minim] - 2023) > abs(a[i] - 2023)) に変えてやると通りました...。

誤読はよくない、5:40 で解けました...。

B

今年も実装ゲーです。
あみだくじをシミュレーションして、 0 or 1 本の線を引くとき、 P → Q に行けるようにできるか、引くならどこかという問題です。

適当に入力を受け取って、シミュレーション関数を書きます。
そんで最初から行けるなら OK 、行けないなら線を引く場所を全探索して出力します。

このコードで提出です。通りました 🎉
時間は 17:12 でした。この時点で 9 位まで上昇!

#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) bool simulation(int n, int m, int p, int q, vector<int> &x) { int now = p; rep(i, x.size()) { if (x[i] == now) { now++; } else if (x[i] == now - 1) { now--; } } return (now == q); } int main() { while (true) { int n, m, p, q; cin >> n >> m >> p >> q; if (n + m + p + q == 0) break; vector<int> x(m); rep(i, m) cin >> x[i]; if (simulation(n, m, p, q, x)) { cout << "OK" << endl; continue; } bool printed = false; rep(i, m + 1) { if (printed) break; rep(j, n) { if (j == 0) continue; if (printed) break; vector<int> t = x; t.insert(t.begin() + i, j); if (simulation(n, m, p, q, t)) { cout << j << " " << i << endl; printed = true; } } } if (!printed) { cout << "NG" << endl; } } }

C

うーん、パリティが関係しそう。
(ij)modN(i - j) \bmod N が偶数かつ同じ値であるところを N2\lfloor \frac{N}{2} \rfloor ずらせばよさそう?
ということで実装して kAsA にテストをお任せすると、奇数の場合によくないらしい。。。
奇数の時は端っこを削ぎ落して偶数に帰着させればいいんじゃね?ってことで実装して提出。 WA でした。

偶数の場合
偶数の場合
奇数の場合
奇数の場合

よくよく見てみると、同じ値が含まれており、実装ミスが判明。
一応テストコードを書いて、直らないなーをしていると through が閃きました。

「偶数の場合は 4 分割して、パリティが偶数の部分を対角グループで swap すればいいんじゃね? 証明もできたで」(要約)

つまりこんなかんじ。
(i+j)mod2=0(i + j) \bmod 2 = 0 のとき、 (i,j)(i, j)((i+N2)modN,(j+N2)modN)\left( \left( i + \frac{N}{2} \right) \bmod N, \left( j + \frac{N}{2} \right) \bmod N \right) と swap する。

閃いた案
閃いた案

奇数の場合は、自分の案の「削ぎ落とす」感じで書いてみると、ちゃんとテストは通ったので提出。 AC 🎉
2:00:49 の 1 ペナでした。まずい!

D

C と並行して考えていました。
最初に思いつくのはやっぱり DP で、部分和問題っぽいなーと思ってました。
でもうまくいかない。。

2 進数で表現すると実は 7 まで?
でも NN に一致させなきゃだしなぁ...
(後に合っていることに気づくも、それは終了後)

上から順に見て分割する Greedy ?
サンプル通ったけど弱いよな... → もちろん WA

うーんだめだ...終了しました...。

愚痴

終了

お疲れさまでした~ 71 位、ギリギリボーダーに届かず...
3 チーム繰り上げ選抜になりませんか...... でもこれは願うしかできないので。。

繰り上げの可能性はかなり低いと思うので、来年度頑張ります...!
埼玉大学としては 2009 年以来 2 度目の予選落ち、残念であり申し訳なさがあります。。

皆さんお疲れさまでした!東大 5 チーム強すぎ!!

打ち上げ

せっかくなので、大学近くの某飲食店で打ち上げ。

いろいろ話が盛り上がっていると、なんだかんだ 23 時に。
終電ギリギリで何とか間に合いました。
駅まで走ったのでおなか痛い + 運動不足が露呈する結果に。。。