3完。昼間にプロセカとMEGA39's+をやりまくって天気が悪いのもあり体調微妙になってたが、自覚してからはおとなしく過ごしてなんとか大丈夫だった。ARCの難しい問題を読むと迷路に入ったような感覚になり、普段自分が安心している世界がいかに狭いかを感じさせてくれる。
A - Digit Sum of 2x
正整数xを2倍することで桁和は高々2倍にしかならない。xとして1をN個ならべた数を採用すれば2倍は達成できる。そのMを達成する最小のxは、繰り上がりがあってはならないので、5以上の数字があってはだめで4以下なら大丈夫。桁数を少なくするため4で下の桁から埋めていく。
B - Gift Tax
たくさん操作しても意味ないやつ。なんか大きいのから小さいのたちへ渡すとき、小さいのを均等にするために小さいの同士でやり取りが発生する可能性を恐れた。が、二分探索が見えて400点であることを考えるとそんな複雑なやり方とも思えない。もう少し考えると、aを足すのとbを引くの両方やった要素があるとすると、その相手が同じなら明らかに無意味だし、違うならお前ら同士でやれという話になる。というわけで、最大値をx以上にできるかの判定は、xより小さいならaを足す必要回数をカウント、そうでないなら何回bを引けるかカウント、収支が負でないならOK。割り算でオーバーフローしないことは確認していたが、回数の和でオーバーフローして1WA。最初にソートしてもいいからソートしておいたけど、不要だと気づいても分岐予測で得するかもと思いそのままにしておいた。
C - K Derangement
サンプルにあるようなパターンを思いつくが、さすがにこんな簡単なはずはないので闇を探しに行く。K=1のときを考えると、Nは偶数なら隣同士スワップするだけでいい。K=2のときは、4個ずつ区切ってやれそうだ。最初の2個は 3 4 より小さくできないからそれが実現できれば最善、次の2個は 1 2 とすればNが4小さい問題に帰着できている。つまりK*2個で区切って 3 4 1 2 のようなパターンで埋めて、最後のK*2+R（RはK*2未満の整数）個だけを考えればいい。ここも最初はサンプルにあるようなパターンでいいかと思ったけど普通に例外が手で見つかる。最後のK*2個を残して今までと同じパターンを置いてよさそうだ。相異なる整数がK*2個残れば今までと同じパターンでK以上の差は確保できると期待できるし、K*2-1個しかなかったらできないんじゃないかな（これはひどい）。何も証明していないけど、ここらで周囲に何もなくなったので実装して提出することにした。実装はけっこう大変。まずK*2個ずつパターンを作って（あまりは放置）、最後のK*2個だけ昇順ソート、そのK*2個の中で同じパターンを作る。AC。
D - AND OR Equation
xとyで一致するビットを固定して考えると、それ以外のビットが片方だけ1になるように自由に決めることができてその和が全部同じになる。片方だけ1になる部分は反転したものと違うグループに入る。2個のグループがあってグループ内では同じ値になる。というのが糸口にはなると思ったんだけど、固定するパターンがたくさんあって絡み合うから無理。なのでEFも読んだ。
（追記）
D : モジュラ性のやつ
— tatyam (@tatyam_prime) July 16, 2022
f(x) - f(x & y) = f(x | y) - f(y)
に変形すると、同じ bit が増えたときの増分が同じ
1 bit ずつ増やすことを考えれば
f(1 + 2 + 4 + 8) = f(0) + f(1) + f(2) + f(4) + f(8)
と分解できる [ここまで典型]
ヤバすぎ。
