ICPC 2023 Asia Yokohama Regional 参加記
この記事は TUT Advent Calendar 2023 の 11 日目の記事です。
10 日目の記事はじょっかさんの『推しは創れ ～理想を追い求めて～』でした。
I はじめに
polylogK といいます。競技プログラミングをしている 3 系の B4 です。
先日 ICPC Asia Yokohama Regional という競技プログラミングのコンテストに TUT のチームとして出場してきました。
この記事では，その参加記録と，来年度のチームメンバーの募集をしたいと思います。
よろしくお願いします。
II チーム
ICPC は三人一組のチームで参加するコンテストです。
私達は TUTankhamun というチーム名で参加していました（ちなみに，去年も同じ名前で参加していました）。
チーム練習とかは一切せずに，本番だけ集まるという感じのチームです。
他のチームメンバー視点の記事もあるので，以下からどうぞ。
III コンテスト day-1
受付が 13:00 開始だったので，それに間に合うように新幹線で豊橋から横浜に移動しました。
そのまま会場の横浜産貿ホールまで移動すると，会場があるので受付を済ませて ICPC グッズ等を頂きます。
day1 は，受付のほかにはリハーサルやチーム紹介等をするだけなので，かなりリラックスしながら過ごしていました。
day1 のスケジュールが終わると，すぐにホテルに向かいました（かなり疲れていてすぐに休みたかった）。
ホテル近辺の店で夕食を食べてから，すぐに就寝しました（他のチームメンバーは起きて ABC に出ていたらしい，すごい）。
IIII コンテスト day-2
コンテスト本番です。
前日は随分早めに寝たので体調はかなりよかったです。
遅刻をすると大変なため，会場の横浜産貿ホールにあるドトールで朝食を食べました。
少なめに見えますが，コンテスト時にメロンパンや弁当を貰えるので問題無いという判断です。
コンテストが開始します。
チームの戦略としては，基本的にチーム内で一番 AtCoder レートが高く，また US キーボードに慣れている私がすべての実装を行い，他のチームメンバーに問題文の翻訳（ICPC では問題文は英語で提供される）と考察を任せていました。
以下時系列順に箇条書きです。
問題文等は公式サイトから確認できます。
9:30 開始。PC を起動して VSCodium の設定をしてから A 問題を読み始める（ICPC 参加者向け情報：takeout を作業ディレクトリにすると便利）。
9:45 A 問題を AC する。全探索するだけの挨拶問題。
#include <bits/stdc++.h>
int main() {
int h, w; scanf("%d%d", &h, &w);
std::vector<std::string> s(h); for (auto& v: s) std::cin >> v;
const std::string yoko = "YOKOHAMA";
int ans = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] != 'Y') continue;
const int LEN = 7;
for (int k = 0; k < (1 << (2 * LEN)); ++k) { // 4^7
bool ok = true;
int ny = i, nx = j;
for (int l = 0; l < LEN; ++l) {
const int pat = (k >> (2 * l)) & 3;
if (pat == 0) nx++;
else if (pat == 1) nx--;
else if (pat == 2) ny++;
else if (pat == 3) ny--;
if (nx < 0 or ny < 0 or nx >= w or ny >= h or s[ny][nx] != yoko[l+ 1]) {
ok = false;
break;
}
}
if (ok) ++ans;
}
}
}
printf("%d\n", ans);
return 0;
}そのままチームメイトから B 問題の概要を聞く。セグメントツリーがあればやるだけだが，書くのが面倒くさいなあと思いながら BIT を書く。まだ頭が回っておらずやたらと時間がかかる。
10:27 B 問題を AC する。
#include <bits/stdc++.h>
using i64 = long long;
struct BIT {
int size;
std::vector<int> bit;
BIT(int n): size(n), bit(n + 1, 1 << 30) {};
int fold(int i) {
int ret = 1 << 30;
while (i > 0) {
ret = std::min(ret, bit[i]);
i -= i & -i;
}
return ret;
}
void update(int i, int x) {
while (i <= size) {
bit[i] = std::min(bit[i], x);
i += i & -i;
}
}
};
int main() {
int n, c, p, q; scanf("%d%d%d%d", &n, &c, &p, &q);
std::string s; std::cin >> s;
std::vector<i64> a(s.size());
for (int i = 0; i < n; ++i) a[i] = (s[i] == 'Y' ? p - q : p);
std::vector<i64> b(s.size() + 1, 0);
for (int i = 0; i < n; ++i) b[i + 1] = b[i] + a[i];
std::vector<i64> vec(b);
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
auto idx = [&](i64 val) {
return std::lower_bound(vec.begin(), vec.end(), val) - vec.begin();
};
// printf("A: "); for (auto v: a) printf("%d ", v); puts("");
// printf("B: "); for (auto v: b) printf("%d ", v); puts("");
// printf("v: "); for (auto v: vec) printf("%d ", v); puts("");
BIT bit(vec.size());
std::vector<int> next(n, -1);
for (int i = n - c; i >= 0; --i) {
{
int index = idx(b[i + c]) + 1;
bit.update(index, i + c);
// std::cout << "update: " << idx(b[i + c]) << " " << i + c << std::endl;
}
int index = idx(b[i]) + 1;
next[i] = bit.fold(index);
// std::cout << "query: " << idx(b[i]) << " " << next[i] << std::endl;
}
// for (auto v: next) printf("%d ", v); puts("");
std::vector<int> dp(n + 1, 0);
for (int i = 0; i < n; ++i) {
const int to = next[i];
if (to < dp.size()) dp[to] = std::max(dp[to], dp[i] + 1);
dp[i + 1] = std::max(dp[i + 1], dp[i]);
}
printf("%d\n", dp[n]);
return 0;
}順位表を確認すると F 問題が多く解かれていたのでチームメイトから F 問題の概要を聞く。縦と横で独立に考えて区間の個数を掛ければ解けることはすぐに分かるが，ここで実装方針をミスって std::set で区間を管理する中実装を開始してしまう。
11:04 F 問題に提出するがデバッグ出力を消し忘れて OUTPUT-LIMIT で 1WA 稼ぐ。
11:05 デバッグ出力を消して提出して F 問題を AC する。
#include <bits/stdc++.h>
using i64 = long long;
struct sakina {
using P = std::pair<std::pair<int, int>, int>;
std::set<P> set;
std::vector<int> col;
sakina(int n) : col(n) {
for (int i = 0; i < n; ++i) {
set.insert({{i, i + 1}, i % 2});
col[i] = i % 2;
}
}
void flip(int i) {
auto it = set.lower_bound({{i, i + 1}, 0});
col[i] = 1 - col[i];
if (it != set.end() and it->first.first == i) { // leftmost
const int l = it->first.first;
const int r = it->first.second;
set.erase(it);
if (r == i + 1) {
set.insert({{i, i + 1}, col[i]});
} else {
set.insert({{i + 1, r}, col[i + 1]});
set.insert({{i, i + 1}, col[i]});
}
} else {
assert (it != set.begin());
it = std::prev(it);
const int l = it->first.first;
const int r = it->first.second;
set.erase(it);
if (r == i + 1) { // rightmost
set.insert({{l, i}, col[l]});
set.insert({{i, i + 1}, col[i]});
} else { // inside
set.insert({{l, i}, col[l]});
set.insert({{i, i + 1}, col[i]});
set.insert({{i + 1, r}, col[i + 1]});
}
}
// merge
it = set.lower_bound({{i, i + 1}, col[i]});
int l = i, r = i + 1;
auto lit = nullptr, rit = nullptr;
if (it != set.begin() and it->second == std::prev(it)->second) {
l = std::prev(it)->first.first;
set.erase(std::prev(it));
}
if (std::next(it) != set.end() and it->second == std::next(it)->second) {
r = std::next(it)->first.second;
set.erase(std::next(it));
}
set.erase(it);
set.insert({{l, r}, col[i]});
}
void print() {
for (auto p: set) {
printf("{[%d, %d)%d}, ", p.first.first, p.first.second, p.second);
}
puts("");
}
i64 size() {
return set.size();
}
};
int main() {
int n, q; scanf("%d%d", &n, &q);
sakina X(n), Y(n);
while (q--) {
std::string s; std::cin >> s;
int x; scanf("%d", &x); --x;
if (s == "ROW") {
Y.flip(x);
} else { // COLUMN
X.flip(x);
}
printf("%lld\n", X.size() * Y.size());
// X.print();
// Y.print();
}
return 0;
}順位表を確認して次に多く解かれていた D 問題の概要をチームメイトから聞く。構文解析っぽく見えるが区間 DP するだけなので，区間 DP をする。ローリングハッシュが必要になるが kactl のライブラリを持ち込んでいたので，そこから写経する。
11:49 D 問題に提出するが WA になる。ここでコミュニケーションエラーが発覚して，条件がうまく伝わっていなかったことが判明する（繰り返し数は 1 桁のみという条件）。
11:51 修正して D 問題を AC する。
#include <bits/stdc++.h>
using i64 = long long;
struct H {
typedef uint64_t ull;
ull x; H(ull x=0): x(x) {}
#define OP(O,A,B) H operator O(H o) { ull r = x; asm \
(A "addq %%rdx, %0\n adcq $0,%0" : "+a"(r) : B); return r; }
OP(+,,"d"(o.x)) OP(*, "mul %1\n", "r"(o.x) : "rdx")
H operator-(H o) { return *this + ~o.x; }
ull get() const { return x + !~x; }
bool operator==(H o) const { return get() == o.get(); }
bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (long long)1e11+3;
struct HashInterval {
std::vector<H> ha, pw;
HashInterval(std::string& s): ha(s.size() + 1), pw(ha) {
pw[0] = 1;
for (int i = 0; i < s.size(); ++i) {
ha[i + 1] = ha[i] * C + s[i];
pw[i + 1] = pw[i] * C;
}
}
H hashInterval(int a, int b) { // [a, b)
return ha[b] - ha[a] * pw[b - a];
}
};
void chmin(int& x, int y) {
x = std::min(x, y);
}
int main() {
std::string s; std::cin >> s;
const int n = s.size();
std::vector<int> keta(n + 1);
for (int i = 1; i <= n; ++i) {
int j = i;
while (j != 0) {
keta[i] += 1;
j /= 10;
}
}
std::vector dp(n + 1, std::vector<std::string>(n + 1, ""));
for (int i = 0; i < n; ++i) {
dp[i][i + 1] = std::string(1, s[i]);
}
HashInterval sakina(s);
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 2; j <= n; ++j) {
// [i, j)
// split into two
{
int min = 1 << 30, argmin = 1 << 30;
for (int k = i + 1; k < j; ++k) {
// [i, k) + [k, j)
if (dp[i][k] == "" or dp[k][j] == "") continue;
const int tmp = dp[i][k].size() + dp[k][j].size();
if (tmp < min) {
min = tmp;
argmin = k;
}
}
dp[i][j] = "" + dp[i][argmin] + dp[argmin][j];
}
// repeat
{
int min = 1 << 30, argmin = 1 << 30;
for (int k = 1; k < j - i; ++k) {
if ((j - i) % k) continue;
const int rep = (j - i) / k;
if (!(2 <= rep and rep <= 9)) continue;
if (dp[i][i + k] == "") continue;
H hash = sakina.hashInterval(i, i + k);
bool check = true;
for (int l = 1; l < rep; ++l) {
const int nl = i + k * l;
const int nr = i + k * (l + 1);
H agoshi = sakina.hashInterval(nl, nr);
if (hash != agoshi) {
check = false;
break;
}
}
if (!check) continue;
const int tmp = keta[rep] + dp[i][i + k].size() + 2;
if (tmp < min) {
min = tmp;
argmin = k;
}
}
if (min < dp[i][j].size()) {
dp[i][j] = std::to_string((j - i) / argmin) + "(" + dp[i][i + argmin] + ")";
}
}
// std::cout << "[" << i << ", " << j << "): " << dp[i][j] << std::endl;
}
}
std::cout << dp[0][n] << std::endl;
return 0;
}順位表を確認して次に多く解かれていた E 問題の概要をチームメイトから聞く。結構悩んだが bitDP っぽく，すでに出現したものの集合を管理しながら，禁止順序を確認しながら DP すれば良いことが分かる。ここで，ゼータ変換必要そうなのにライブラリ持ってない！みたいなことを喋ったが，結局ゼータ変換は必要なかった。
12:32 E 問題に提出して OUTPUT-LIMIT で 1WA 稼ぐ。デバッグ出力をちゃんと消したかどうかは毎回確認すると良い。
12:33 E 問題に改めて提出するが TLE で落ちる。DFS していたところを for で書き直す。
12:41 E 問題を AC する。
#include <bits/stdc++.h>
using i64 = long long;
int main() {
int n, m; scanf("%d%d", &n, &m);
std::vector<int> a(m), b(m), c(m);
for (int i = 0; i < m; ++i) {
scanf("%d%d%d", &a[i], &b[i], &c[i]);
--a[i]; --b[i]; --c[i];
}
std::vector<int> bans(1 << n);
for (int i = 0; i < m; ++i) {
bans[(1 << a[i]) | (1 << c[i])] |= (1 << b[i]);
}
for (int i = 0; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
bans[i | (1 << j)] |= bans[i];
}
}
const int MOD = 998244353;
std::vector<int> dp(1 << n); dp[0] = 1;
for (int v = 0; v < (1 << n); ++v) {
for (int i = 0; i < n; ++i) {
if (v >> i & 1) continue;
if (bans[v] & (1 << i)) continue; // ban
const int rev = ((1 << n) - 1) ^ (1 << i) ^ v;
if (bans[rev] & (1 << i)) continue; // ban
const int to = v | (1 << i);
dp[to] = (dp[to] + dp[v]) % MOD;
// std::cout << to << " += " << v << ": " << dp[v] << std::endl;
}
}
// for (int i = 0; i < (1 << n); ++i) std::cout << std::bitset<5>(i) << "(" << i << "): " << dp[i] << std::endl;
printf("%lld\n", dp.back());
return 0;
}K 問題の概要をチームメイトから聞く。インタラクティブ問題。三分探索かと思ったがすり抜ける可能性があるので難しい。とりあえず等分割して網掛けして引っかかるのを待つという案が浮かぶので実装してみる。
13:00 K 問題に提出するが WA になる。区間の幅が広すぎてすり抜けているので，区間幅を狭めるがそうするとクエリ回数が足りなくなる。ここで，邪法を思いつく。円の中心座標をある程度絞ったあとは，中心座標を全探索し，これまでのクエリとの誤差を最小化するものを選択することにする。
13:43 K 問題に提出するが WA になる。バグが見つかるので修正する。
13:59 K 問題に提出するが WA になる。バグが見つからずに，落ちるケースも見つからないので，ランダムテストをすることにする。今回の ICPC ではインタラクティブ用のジャッジプログラムが配布されていたので，これを python の subprocess で呼ぶことにする。このランダムテストプログラムを書くのにも結構手間取った，検索ができないので PC に用意されている python の公式ドキュメントをにらみながら実装した。
import subprocess
from pathlib import Path
from random import randint
import sys
while True:
r = randint(100, 50000)
x = randint(r, 100000 - r)
y = randint(r, 100000 - r)
print(x, y, r)
with Path("in.txt").open('w') as f:
subprocess.run(f"echo {x} {y} {r}".split(), stdout=f)
subprocess.run("bash /opt/problems/K/run.bash in.txt ./a.out 2> /dev/null".split())14:24 ランダムテストを動かすと落ちるケースが見つかったので，それを元にデバッグする。x と y の間違えだった。すぐに修正して提出すると AC する。
#include <bits/stdc++.h>
using i64 = long long;
int counter = 0;
double query(int x1, int y1, int x2, int y2) {
printf("query %d %d %d %d\n", x1, y1, x2, y2);
fflush(stdout);
++counter;
double d;
std::cin >> d;
return d;
}
void answer(int x, int y, int r) {
assert(counter <= 1024);
printf("answer %d %d %d\n", x, y, r);
fflush(stdout);
}
const int N = 100'000;
const int STEP = 199;
const int ST = 40;
int main() {
using namespace std::placeholders;
auto queryX = std::bind(query, _1, 0, _1, N);
auto queryY = std::bind(query, 0, _1, N, _1);
int lx = -1, rx = -1, ly = -1, ry = -1;
std::vector<double> dxs(N + 1, -1), dys(N + 1, -1);
{
for (int i = 0; i <= N; i += STEP) {
dxs[i] = queryX(i);
dys[i] = queryY(i);
}
const int argmax_x = std::max_element(dxs.begin(), dxs.end()) - dxs.begin();
lx = std::max(0, argmax_x - STEP);
rx = std::min(N, argmax_x + STEP);
const int argmax_y = std::max_element(dys.begin(), dys.end()) - dys.begin();
ly = std::max(0, argmax_y - STEP);
ry = std::min(N, argmax_y + STEP);
}
for (int i = lx + ST; i < rx; i += ST) {
dxs[i] = queryX(i);
}
for (int i = ly + ST; i < ry; i += ST) {
dys[i] = queryY(i);
}
fprintf(stderr, "[%d, %d]x[%d, %d]\n", lx, rx, ly, ry);
double min = 1 << 30;
int ans_x = -1, ans_y = -1, ans_r = -1;
for (int x = lx; x <= rx; ++x) {
for (int y = ly; y <= ry; ++y) {
std::vector<double> rs;
for (int i = lx; i <= rx; ++i) {
if (dxs[i] <= 0) continue;
const double dy = dxs[i] / 2.;
const double dx = std::abs(x - i);
const double tmp = sqrtl(dx * dx + dy * dy);
rs.push_back(tmp);
// std::cerr << i << ": " << dx << " " << dy << " " << tmp << " " << dxs[i] << std::endl;
}
for (int i = ly; i <= ry; ++i) {
if (dys[i] <= 0) continue;
const double dy = dys[i] / 2.;
const double dx = std::abs(y - i);
const double tmp = sqrtl(dx * dx + dy * dy);
rs.push_back(tmp);
// std::cerr << i << ": " << dx << " " << dy << " " << tmp << " " << dys[i] << std::endl;
}
double mean = std::accumulate(rs.begin(), rs.end(), (double)0) / (double)rs.size();
double var = 0;
for (double v: rs) var += (v - mean) * (v - mean);
// std::cerr << "mean: " << x << " " << y << " " << mean << " " << var << " " << rs[0] << std::endl;
// for (double v: rs) std::cerr << v << " "; std::cerr << std::endl;
if (var < min) {
min = var;
ans_x = x;
ans_y = y;
ans_r = (int)std::round(mean);
}
}
}
std::cerr << counter << std::endl;
answer(ans_x, ans_y, ans_r);
return 0;
}14:27 もう新しく問題を解く時間が残っていないので G 問題に記念提出をして終了。
コンテスト終了後は，順位表発表があったのち懇親会があります。
懇親会では，古の JOI 同期に会って雑談をしていました。
ホテルに戻ったあとは UFA 2023 を軽く観てから就寝しました。
IIIII 結びと，来年度のチームメンバー募集
ICPC に（実地で）参加するのは二回目だったので，ホテル予約など基本的に去年と同じ行動をしていました（使いまわしすぎて英語で書くところを日本語で書いたりしていました）。
コンテストでは，問題文の翻訳と読解をチームメンバーに完全に任せることができたため，今回は A 問題以外の問題文を読むことはなかったです。
この戦略は，当日決めた一発勝負だったので，うまくいってよかったです。
来年度の ICPC にも参加するつもりなのですが，チームメンバーの一人が今年度で卒業するため，来年度のチームメンバーが一人足りていません！
TUT に在籍中の競技プログラマーで ICPC に参加したい方がいればぜひ連絡してください！ よろしくお願いします！
連絡先は，私の Twitter もしくは bluesky にお願いします。
おまけ
最近好きな曲です。