AtCoder Beginner Contest 126

またUnrated回でした
参加者が5000人を超えた*1こともあるしだいぶきつそうですね

A - Changing a Character (100点)

A - Changing a Character
大抵の環境ではアルファベットの文字コードが連続しているので、'A' - 'a' を引けば大文字になってAC。 $O(1)$ 。

拙解 (C++14): Submission #5448637 - AtCoder Beginner Contest 126

B - YYMM or MMYY (200点)

B - YYMM or MMYY
2桁に分けて、0であるか12より大きかったらYYしかありえない。よって4通りありえて、場合分けしてAC。 $O(1)$ 。

拙解 (C++14): Submission #5452038 - AtCoder Beginner Contest 126

C - Dice and Coin (300点)

C - Dice and Coin
これは要するに「初期得点が１～６で同確率・無作為に決まり、 $K$ 以上になるまでコイントスで勝ち続ける確率」なので、すべての初期得点に対して倍プッシュ何回で $K$ に届くか数えてその都度初期得点ごとの確率を半分にして全部足せばAC。 $O(N \log {N})$ 。

拙解 (C++14): Submission #5457899 - AtCoder Beginner Contest 126

D - Even Relation (400点)

D - Even Relation
無向グラフで巡回がないので、 $d(u,v)$ と $d(v,u)$ は等しい。加えて、木なので、ある頂点 $r$ を根とすれば $d(u,v)=d(r,u)+d(r,v)-2d(r,{\rm 最近共通祖先} (u,v))$ というふうに定まって、偶奇は各ノードで独立に定まるとわかる。したがって、どれかのノード（０とか）をどっちかの色で塗ってそこからBFSで偶奇が入れ替わるたびに塗る色を変えてAC。 $O(N)$ 。

拙解 (C++14): Submission #5464301 - AtCoder Beginner Contest 126

E - 1 or 2 (500点)

E - 1 or 2
無矛盾が保証されている！したがって、カードの中身は１か２かしかなく偶奇だけ気にすればよく、 $A_{X_i}$ がわかれば $A_{Y_i}$ がわかる！もちろんその逆も然り。したがって、 $(X_i, Y_i)$ を辺としたグラフを張って、Union-FindやBFSなどで連結成分の数を求めればそれがそのまま答えとなってAC。BFSなら $O(M)$ 、Union-Findなら $O(Mα(M))$ （ $α(x)$ はアッカーマン関数の逆関数で、現実的な範囲内ではほとんど定数）。
無矛盾が保証されているので、 $Z_i$ は関係ない。ARC級の500点だったら無矛盾が保証されてなくて見る必要ありそう。

拙解 (C++14): Submission #5470040 - AtCoder Beginner Contest 126

F - XOR Matching (600点)

F - XOR Matching
まず $K\ge 2^M$ の場合はどうやってもXORでKを作れないので不可能。そうでない場合、 $M, K$ が小さい場合でいろいろ実験すると、（ $K$ 以外昇順）, $K$ ,（ $K$ 以外降順）, $K$ という数列を作れば条件を満たしそうとわかる。 $K$ 以外については、挟まってる中身に $K$ 以外が2項あるため、XORするとすべて0になって*2、総XORが $K$ になる。 $K$ については、中身は $K$ 以外の負でない整数すべてがあるので、この総XORは $K$ *3。サンプルにあるように $M=1$ の場合がコーナーケースとなって、これを考慮してAC。 $O(2^M)$ 。