ABC 200
Table of Contents
https://atcoder.jp/contests/abc200
A. Century
https://atcoder.jp/contests/abc200/tasks/abc200_a
B. 200th ABC-200
https://atcoder.jp/contests/abc200/tasks/abc200_b
C. Ringo’s Favorite Numbers 2
https://atcoder.jp/contests/abc200/tasks/abc200_c
D. Happy Birthday! 2
https://atcoder.jp/contests/abc200/tasks/abc200_d
解説 AC.
鳩の巣原理で解くというのは全く思いつかなかった。 総和の余りが $R$ になるような個数を DP で調べて、2以上のやつがあれば復元するという方法で最初解こうとしたが WA がどうしても取れなかった。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vll A(N);
rep(i, N) {
cin >> A[i];
A[i] %= 200;
}
map<int, vvint> mp;
int n = min(N, 8ll);
rep2(i, 1, 1 << n) {
vint v;
ll sum = 0;
rep(j, n) if ((i >> j) & 1) {
v.push_back(j + 1);
sum += A[j];
}
sum %= 200;
mp[sum].push_back(v);
}
for (auto [k, vv] : mp) {
if (vv.size() >= 2) {
Yes();
rep(i, 2) {
cout << vv[i].size() << ' ';
print(vv[i]);
}
return;
}
}
No();
}
dp 版でも実装できた。解説や解説放送と違い、dp[x][r] を x 個使って総和の余りが r となる場合の数とした。
WA になっていた原因は愚直に dp[x][r] を計算すると int64 に収まらないので、2個以上になったら2に抑えてしまうようにすればよかった。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vll A(N + 1);
rep(i, N) {
cin >> A[i + 1];
A[i + 1] %= 200;
}
// dp[x][r]: x 個使って余りが r となる場合の数
vvll dp(N + 1, vll(200));
dp[0][0] = 1;
rep2(i, 1, N + 1) {
vvll dpn(N + 1, vll(200));
rep(x, i) {
rep(r, 200) {
dpn[x][r] += dp[x][r];
chmin(dpn[x][r], 2ll); // 2個あれば十分なので頭を抑える
ll nr = (r + A[i]) % 200;
dpn[x + 1][nr] += dp[x][r];
chmin(dpn[x + 1][nr], 2ll); // 2個あれば十分なので頭を抑える
}
}
swap(dp, dpn);
}
ll rem = -1;
rep(r, 200) {
ll num = 0;
rep2(x, 1, N + 1) {
num += dp[x][r];
}
if (num >= 2) {
rem = r;
break;
}
}
if (rem < 0) {
No();
return;
}
vvint ans;
auto dfs = [&](auto dfs, int now, int num, ll r, vint ids) -> void {
if (ans.size() == 2) return;
if (now == 0) {
if (num == 0 && r == 0) ans.push_back(ids);
return;
}
ll nr = (r - A[now] + (ll)1e9) % 200;
if (num - 1 >= 0 && dp[num - 1][nr]) {
ids.push_back(now);
dfs(dfs, now - 1, num - 1, nr, ids);
ids.pop_back();
}
dfs(dfs, now - 1, num, r, ids);
};
rep2(num, 1, N + 1) {
if (dp[num][rem])
dfs(dfs, N, num, rem, vint());
}
Yes();
for (auto v : ans) {
reverse(all(v));
cout << v.size() << ' ';
print(v);
}
}
E. Patisserie ABC 2
https://atcoder.jp/contests/abc200/tasks/abc200_e