Asa's Website

ICPC2024 国内予選

icpccompetitive programmingparticipation log

作成日 / 最終更新日

Table of Contents
開始前チーム決め練習模擬前日当日ABCDEF終了打ち上げ

ICPC 4 度目の参加です！

開始前

チーム決め

去年 は 71 位でギリギリ通過できずでしたが、今年こそは勝ちたい！
ということで今年も through, kAsA02 と 3 人でチームを組みました。
チーム名は「executive is deprived」。
去年「Maximum-executive」(Maximum 執行部) で、世代交代したので「executive is deprived」(執行部剥奪) です。
2021 の「seica is gone」にも倣ってます。
(文法的には "executives are deprived" が正しいのかもしれない。知らんけど)

埼玉大学からは 10 チーム参戦です。 多すぎんか？

練習

Maximum の活動で何回か過去問を解いていました。
が、ほとんど見覚えある問題でなんか解きごたえもなく... (何度も解いてしまっている弊害)

模擬

JAG の模擬国内予選にも出た。
順位 は 3 完で 60 位。
何とか選抜通過できてる判定だけど、 D も E も思考ロックされなければ解けてそうだったのでよくない。

ついでに今回の模擬国内予選でシステムの仕様が分かったので、去年作った国内予選模倣システムも今回のルールに合わせて変更。
6 分制限 + テストは 1 ファイル、提出の操作が減ってうれしい？
https://github.com/saitamau-maximum/icpc-prelim-system/

前日

実は SC を受験していて合格発表日だったので緊張していました。
無事合格しました～！やった～ 🎉
このまま ICPC も勝ちたい！

受験記 (?) はこちら

その日も前日のルール確認とかするために大学に行ってきました。
なんか七夕飾りがしてあって、短冊に ICPC Regional に行けるよう祈願を 書かされて 書いてきました。

当日

やるぞ！

A

今年は事前セットアップが許可されていたので、 A 問題は以下のテンプレを用意しておいた。 (include とかは略)

int main() {
  while (true) {
    int n;
    cin >> n;
    if (n == 0) break;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    int ans = 0;
    rep(i, n) // todo
    cout << ans << endl;
  }
}

開始してすぐ問題を開き、問題をざっくり読み。
はい、今年もこのテンプレ通りの形式でした。
10 秒で実装に取り掛かります。
チームメンバーからは「もう読んだの！？」って言われた。
プリンタは 10 チームで 1 台共有しているので、まだまだ時間がかかりそう。
画面半分でメンバーに B 見せながら、 A を実装。

前から順に足していって、 300 を超えなければ採用を繰り返していく。
最初個数を出力するものだと思っていて合わない！？をしたが、サンプルを見てみるとこれは金額だな～と理解 (問題はちゃんと読んでない)
はい、 AC 🎉
1:57 でした。

B

これもなんとなく理解。
前から順に見てシミュレーションすればよさそう。
並走した場合「追い抜き」にカウントされるのか？になっていたので、実装しながらメンバーに確認してもらう。
どうやら並走は追い抜きにカウントされないらしいので、不等号は等号なしでよさそう。

サンプルは合ってそう。
一応チームメンバーにレビューしてもらい、良さそうなので提出。
AC 🎉 6:09 でした。
ちょっと詰まった気もしたけど、ほかのチームも詰まっていそうで 4 位に！

C

この辺でプリントアウトした問題文が到着。

えーハニカムかよ～ってみんなで言ってた。
ABC359 C - Tile Distance 2 の解説 に出てきたな～とか話し合ってたが、内容を覚えていないので、ふつうにグラフに落とし込めばいいんじゃね？となり、実装に取り掛かる。

(i,j)(i,j) に隣接するのは (i,j+1),(i,j−1),(i+1,j),(i−1,j),(i+1,j−1),(i−1,j+1)(i,j+1),(i,j-1),(i+1,j),(i-1,j),(i+1,j-1),(i-1,j+1) っていうのをチームで確認し、盤面も 2001×20012001 \times 2001 でおさまりそうなのでよさそう。
BFS で (0,0)(0, 0) からの最短距離を求めたらあとは O(1)O(1) で出力するだけ。
いつも Copilot に inRange とか id (= i⋅w+ji \cdot w + j) とかの実装を任せっきりだったので、めんどくせ～とか言いながら実装。

AC 🎉 16:16 でした。

D

C を実装している間にメンバーが読んでいたので、話を聞く。
障害物があるのは 100×100100 \times 100 の範囲なので、そこまではふつうにシミュレーションできそう。ループに入ったら余りを求めればいいね～ということを確認。
自分は問題の 3 割くらいしか読んでいなかったので、ちょくちょく問題を確認しながら実装。
メンバーは E へ。

ふつうのシミュレーションはできた。 あとは方向ごとにメモしておいて、周期性を見つける。
障害物ない範囲に出たら、その方向に進むだけなのでそれも実装して、完了。

サンプルを試してみると、全然合わない。
始点がずれていた。直してみても、合わない。
ちょっと悩んでいると、どうせ x,yx, y 軸逆なんじゃね？ということで、入力の x, y を逆にしてみるといくつかのケースで合ってきた。
なんか無限ループしてるケースがあるので、メンバーに見てもらう。
方向メモと方向転換の順序が逆だったので、それを直してみるとよさそう。

サンプルもまあ強いんじゃね？ということで提出すると、 AC 🎉
39:03。かなり詰まってしまった...

E

先に読んでいたメンバーから説明を受ける。
cc の最初と最後が一致していれば、それを外側に配置するだけ。
それ以外については考察中とのこと。
とりあえず、このケースを実装しました。

いろいろごちゃごちゃしつつ、外側から順に見ていけばいいんじゃない～？と思って、ほかにやることないので実装。
外側から決めていって、どんどん使っていないところを見るようにしていくかんじ。
メンバーも E を考えます。ほかにいい方法がないか、反例はないか、などを任せます。

とりあえず時間をかけて実装はしたが全然うまくいかない。
しばらくすると今年も through がひらめきました。

「影に置きたいよね～ これ行けんじゃね？証明できたで」

  • 一番左 ll と同じ数字で最も右側にある index lplp と、一番右 rr と同じ数字で最も左側にある index rprp を見つける。このとき、 lp≠rplp \ne rp になる。 (最初と最後が一致している場合は除いているので)
  • lp<rplp < rp ならダメ
  • lp>rplp > rp なら、そこの間はなんでもいい
  • そしたら両端を削って いい感じに配置していく
  • 奇数の場合は 1 余るけど、これは真ん中に配置していけばおっけー

いい感じに配置をどうするのか微妙なところだったけど、見せてもらった図をもとに、こんなかんじかな～？を実装。

c=[1,2,3,1,3,2,4,4,3] のケース
c=[1,2,3,1,3,2,4,4,3] のケース
c=[1,2,3,3,3,2,4,1,3] のケース
c=[1,2,3,3,3,2,4,1,3] のケース

先に lp, rp を決めたらそこが影になるので、その後ろはうまく条件を満たすように十字に配置していく。
重なっている部分はどうでもいいので、画像 2 つ目のケースはクロスする部分は 1 と 3 どっちでもいい。

この部分の実装はこんな感じ。

deque<int> q;
rep(i, n) q.push_back(i);
int l = q.front();
int r = q.back();
q.pop_front(), q.pop_back();
int lp = -1, rp = 10000;
rep(i, q.size()) {
  if (c[q[i]] == c[l]) lp = q[i];
  if (c[q[i]] == c[r] && rp == 10000) rp = q[i];
}
if (lp < rp) {
  cout << "No" << endl;
  return;
}
int idx = 0;
while (true) {
  ans[rp][idx] = c[r];
  ans[lp][idx] = c[l];
  ans[n - 1 - idx][rp] = c[r];
  ans[n - 1 - idx][lp] = c[l];
  ans[n - 1 - rp][n - 1 - idx] = c[r];
  ans[n - 1 - lp][n - 1 - idx] = c[l];
  ans[idx][n - 1 - rp] = c[r];
  ans[idx][n - 1 - lp] = c[l];
  if (q.size() == 1) {
    int i = q.front();
    ans[i][i] = c[i];
    q.pop_back();
  }
  if (q.empty()) break;
  idx++;
  l = q.front(), r = q.back();
  q.pop_front(), q.pop_back();
}
cout << "Yes" << endl;
rep(i, n) rep(j, n) {
  cout << ans[i][j] << " \n"[j == n - 1];
}

through が kAsA02 に説明している間に実装してみた。
サンプル弱すぎるのでいくつか挙げたケースで実装してみると、良さそう。
もういいや、提出！ AC 🎉
2:20:27 でした。 through に助けられた～～～

F

見た瞬間に 45 度回転典型じゃね？となり、少し悩むとコインから逆算すればいいんじゃね？ということになる。
あとは x+y,x−yx+y, x-y が同じところをすでに通ったか判定しておけばよさそう。
だが残り 20 分しかないのに重実装っぽいし、ほぼ突破確定したのでもういいや～となり、順位表を眺めていました。
そして終了です。

終了

お疲れさまでした～ 今年は 31 位、危なげなく突破！
4 完だったとしても最初の早解きのおかげで突破できたみたい。
でも全然安心具合が違うので、本当によかった～！！

2 年ぶりの横浜、楽しみ！
予約がすぐ埋まりそうなので、ホテルの予約をすぐにとった。

メンバーが 2 人とも英語できないらしいので、英語頑張ってねっていうと丸投げ宣言くらった。そんな...

打ち上げ

今年も去年と同じく、大学近くの某飲食店で打ち上げ。
同学年みんなお酒に弱く、すぐに酔っ払ってしまって大変だった。
自称ホストが大量発生して、なんかすごい囲われてた。なんだこれ。

お疲れさまでした！

Asa
Asa
@a01sa01to
·Follow

プログラミング始めたばかりでもみんな 2 完できていてみんなすごいな～になった 👏 (1 チームはコード自体はできてたが提出がよくわからんかったっぽい) 中には 4 完もいて、もしかしたら 2 チーム突破してたかも？な状況だった 来年も頑張ってほしいですね～～ (もちろん自分たちも出る)

埼玉大学 プログラミングサークル Maximum
埼玉大学 プログラミングサークル Maximum
@Maximum03400346

ICPC本当にお疲れ様でした ご協力頂いた皆様に御礼申し上げます 今年は「executive is deprived」が5完！！ 初出場のチームも健闘し、全チーム1問は解くことが出来ました！ 予選通過チームの発表を楽しみに精進を続けて行きます 引き続き応援よろしくお願いします！

3
Reply
Read more on Twitter