ICPC2023 国内予選 | 2023.07 | Articles

今年も参加しました！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 初本も持っていきました。

会場着

Asa

@a01sa01to

·Follow

Maximum-executive で参戦します！ぜひ応援してください！！

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

@Maximum03400346

本日16:30より、ICPC2023 国内予選が開催されます🎉 埼玉大学からは、「Maximum-executive」「Maximum.mum」「Maximum-mini_tomato」「touch_hogehoge」の4チームが参加します💪 ぜひ応援よろしくお願いします✨ 順位表はこちらに公開されているのでぜひ観戦してください👀: yamagula.ic.i.u-tokyo.ac.jp/icpc2023/

12:56 · Jul 7, 2023 (GMT+9)

Read more on Twitter

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

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

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

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

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

Asa

@a01sa01to

·Follow

ICPC2023 国内予選、ぞい！！！！

16:25 · Jul 7, 2023 (GMT+9)

Read more on Twitter

スタート

はい、まず A を見ます。

A

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

これ誤読してて、 $a_i$ が最小になる $i$ を求める問題だと思ってました...
でも実際は $a_i$ が 2023 に一番近い、つまり $|a_i - 2023|$ が最小になる $i$ を求める問題でした。
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

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

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

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

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