ARC 198
Table of Contents
A. I hate 1
https://atcoder.jp/contests/arc198/tasks/arc198_a
考えたこと
$x$, $x+1$ を選んだ場合は $x+1 \equiv 1 \mod x$ となってしまうため隣接した数字は選べない。 N が $1$ より大きいときに $1$ を入れる他の数字との mod で確実にあまりが1の状況を作れるので入れられない。 そうすると 1 より大きいときは $N, N-2, \cdots$ と選べば良さそうと思ったが WA.
反例として $N=7$ のときに $7, 5, 3$ が選ばれるが $7 \equiv 1 \mod 3$ となってしまうため不適。
全ての要素が偶数であれば何を選んでもあまりが1になることはないし、$\floor{\frac{N}{2}}$ 個の要素を選ぶことができる。隣接する数字を選べないことと 1 が選べないことを考慮するとこれが構築できる最大個数であるから $N \neq 1$ のときは $N$ 以下の偶数を全て選ぶことが最適
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
if (N == 1) {
cout << 1 << endl;
cout << 1 << endl;
return;
}
vint ans;
for (int i = 2; i <= N; i += 2) {
ans.push_back(i);
}
cout << ans.size() << endl;
print(ans);
}
B. Rivalry
https://atcoder.jp/contests/arc198/tasks/arc198_b
考えたこと
012012…. という並び (0 は連続して置いて良い) しか条件を満たす数列はないと思った。 だが色々実験しているうちに 012101210… という並びも条件を満たすことがわかった。 これで終わりだと思ったが 0110 という並びも条件を満たすことがわかった。
直線に並べて書いていたときは迷走したが、0 を円環状に並べて考えたら条件を満たす数列が満たすべき条件が見えてきた。
解放
$0$ は隣接するように並べることができる。 そこでまずは $0$ を円環状に並べる。 $X$ 個の隙間に $2$ を差し込んでも条件を満たす数列を作ることができる。 逆に $2$ の数が $X$ 個を超えると条件を満たすような数列を作ることはできない。 よって $X \geq Z$ である。
$0$, $2$ を並べた後に残りの $1$ を挿入していく。このとき $1$ の挿入方法は以下の2パターンが考えられる。
- パターン1: $00$ の間に $11$ を挿入する。すなわち $0110$ を作る
- パターン2: $20$ の間に $1$ を挿入する。すなわち $210$ を作る
パターン1のときは常に $1$ を2個同時に挿入する必要がある。挿入できる隙間の数としては $X - Z$ 個ある。 パターン2のときは $2$ の左右どちらの隙間でも $1$ を挿入できるのでパターン1よりも自由度が高い。
よって挿入する必要がある $1$ をパターン1の方式でできるだけ挿入して、残りの $1$ をパターン2の方式で挿入すれば良い。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
rep(_, t) {
ll x, y, z;
cin >> x >> y >> z;
if (x < z) {
yesno(false);
continue;
};
if (y <= 2 * (x - z)) {
y %= 2;
} else {
y -= 2 * (x - z);
}
yesno(y <= z * 2);
}
}
C. Error Swap
https://atcoder.jp/contests/arc198/tasks/arc198_c
D. Many Palindromes on Tree
https://atcoder.jp/contests/arc198/tasks/arc198_d