AGC014 A, B 考察

agc014 A - Cookie Exchanges

未証明 AC 。パッと見だと A, B, C <= 10^9 なので指示通りのシミュレーションはまずそうに見える。ただ足して 2 で割る操作を繰り返すので差 (?) がなだらか (?) になる時間計算量は O(logN) になりそうだ。無限ループになる条件は全部が偶数で操作を繰り返しているのでどれもほとんど同じ値になっているはずだ。交互に値を入れ替わって……というのはなさそうだ。前の値と同じなら無限ループだと思って良さそう。

上記の推測から指示通りにシミュレーションして AC 。解説によると最大と最小の差が 1/2 になっていくらしい。それを繰り返すのだから O(logN) 。無限ループになるのは全部が同じ値のときらしい。

https://atcoder.jp/contests/agc014/submissions/16477949

agc014 B - Unplanned Queries

解説 AC 。未証明なら可能性はあるけど……。これが緑とは……難しい。

r を根とする根付き木を考えると a <-> b のパスは a -> r と r -> b と解釈して良い。根を通るときはもちろんそうでないときも偶奇の判定だけなので問題ない。あとは a の出現回数と b の出現回数が偶数になっていれば YES そうでなければ NO になる。奇数のときダメな理由としては奇数のうちもっとも深い頂点とその手前の頂点の間の辺は奇数回になってしまうから。

https://atcoder.jp/contests/agc014/submissions/16487996

『ずうのめ人形』を読んだ。面白かったよ。

リングフィットアドベンチャーを続けている。