tinumu's reminder

競技プログラミングについて書いてあります。

今日解いたAGC-Aの問題たち

競技プログラミング AGC

生活をしようとすると競プロのやることが断片化するんじゃ

AGC030 - A - Poisonous Cokkies(200)

解毒剤入りの美味しいクッキーは必ず食べられるね
毒入りクッキーは食べて他のクッキーを食べてみたいに繰り返すと、 $A+B+1$ 個まで食べられるので
答えは $B + \mathrm{min}(A+B+1, C)$ となる。

AGC033 - A - Darker and Darker(300)

操作を $1$ 回やると黒いマスが四方のマスに伸びるのでシミュレーションした時に一番到達が遅いところを見つければいい
これは幅優先探索で簡単に見つかる。
なんかABCみたいな問題だな

AGC034 A - Kenken Race(400)

なんで上の問題が緑上位Diffでこっちが茶下位Diffなんや
$C \lt D$ の時は自明にふぬけくんから動かすと人が交わることがないので連続で $2$ マス '#' が無いことをそれぞれ確認すればよい
$C \gt D$ の時は $[B-1, D+1]$ の中に連続した $3$ マスがあれば順序を変えられるので、追加でこの条件が必要になる
AGC、普通にこういう条件が複雑なやつがでるので A だからといって侮れないな

AGC035 - A - XOR Circle(300)

$x_i$ を $i$ 番目のラクダの被っている帽子の整数とすると、
$x_{i-1} \oplus x_{i+1} = x_i$
であるため、式変形すると、
$x_{i} \oplus x_{i+1} \oplus x_{i+2} = 0$
である。
$i+3$ 番目のラクダを考えると、
$x_{i+3} = x_{i+1} \oplus x_{i+2} = x_i$
となり、 $x_i = x_{i+3}$ が言える。

つまり、整数の種類はたかだか $3$ 種類以下である必要があり、以下の条件のいずれかを満たしているとかぶせ方が存在することになる。

すべての数字が $0$
$N$ が $3$ で割り切れるかつ

数字が $3$ 種類あるとき、これらの xor が $0$ であり、それぞれ $N/3$ 個ずつある
数字が $2$ 種類あるとき、 $0$ の数が $N/3$ 個ある (もうひとつの数字は任意であり、 $2N/3$ 個ある

これを調べるためには map とか set とかで数字の数を管理していけばいいので、 $\mathrm{O}(N \log N)$
でこの問題を解くことが出来る。

嘘解法があり、全ての数字の xor をとって $0$ になるかどうかという解法があるが、

7

1 2 3 4 5 6 7

などは明らかに"No"だが、この解法では"Yes"になってしまうという反例がある。
必要条件は満たしているみたいだけど…

感想

AGCはABCと比べてはいけない(戒め)