DEが解けなかった。悔しいけど、最近のARCはいい問題ばっかりで嬉しい。
A - Two Choices
昨日のABC196Fに似ている。まず、2人の解答が異なる問題の数が偶数だったら「正解した問題の数が等しい可能性」があるし、奇数だったらない。で、この偶奇が実は1の個数でわかる。コンテスト中に考えてた証明は、まず2人の解答がソート済みとして片方だけを並べ替えれるとして一般性を失わなくて、スワップするときにどっちも01が異なる場所じゃないと意味なくて、そういうところをスワップしても違う解答の個数の偶奇は変化しない。ということで、1が偶数個の人を数えて奇数個の人数を掛ければよい（人をソートしても答えは変わらないので、偶数の人のあとに奇数の人が並んでいると考える）。
こういう面白そうな証明（というか数理構造みたいの）を、じっくり楽しむ時間がないのがコンテスト中の悪いところだけどまあコンテスト後にやりましょう。今考えると、まあなんかよくわからんけど証明はできるね。いやコンテスト中はほんとに時間ないから面白そうっていう感情だけ残るけど、実際考えてみるときれいに説明するのは自分には難しかったりする。（解説を見て）なるほど、1の個数の差の偶奇を直接（？）計算するのね。なんか同値な条件を考えてるのに頭の中では向きがあって、逆は考えにくくなってるな。
B - Plus Matrix
ABCのCあたりで既出な気がするけどいつだっけ（追記 : ABC088Cだった）。存在する必要条件がきついので楽。各行が「同じ形」をしている必要があるので、それをチェックしつつ最初の行との差をA[i]に保存する（仮にA[0]を0、BをC[0]とする）。A[0]を決めれば他も決まるので、残った自由度はA[0]がいくつになるかだけ。Aが非負であればそれでよし。負の数があれば、それが0以上になるようA全体に何か足す必要がある。このとき、足す数はできるだけ小さいほうがいい。なので最小値を求めてAとBに足し引きして改めてその最善の頑張りでも負の数が生じてないかチェックする。
C - ℕ Coloring
「iがjの約数」は「jがiの倍数」と言い換えられる。いつもの調和級数。各iから全倍数に対して自分より1大きい数をセットする。コード自体はこれで正解に近いだろうが、正当性をどう考えるか。BFSっぽいと思った。1以上N以下の各整数を頂点とするグラフを考え、iからはiより大きいiの倍数に対して有向辺を張る。このとき辺で結ばれた2頂点は違う色で塗られる必要がある。で、コンテスト中はよくわからなくて、実際に倍数と違う色になっていることを確認するコード（これは元の実装とほぼ同じなので簡単）を書いて最大ケースで確認した。あとは最大値がどうかだが、まあ1, 2, 4, 8, 16 みたいな列を考えると全部違う色にする必要があり、それなら大丈夫だろうと考えた。また、値を更新するときに値が小さくなるケースがあることを確認しており、不安だった（小さくならないようにしても結果は変わらないようだった）。しばらく悩んで進展がないので提出してしまった。AC。
（解説を読んで）いやそれは天才だろ。
（追記）自分のコードも素因数の個数になってるのか。素数倍以外は間違った値だけど、合成数倍なのでそこへ行くまでには正しい値に更新される。線形篩を理解していませんでした。
D - Odd Degree
全部の頂点を選ぶというだけで、辺はあってもなくてもい。辺を1本追加したとき、次数が奇数の頂点数は偶数個しか変化しないので、Kが奇数のときは0。
全くわからない。制約を見ると2乗っぽいけど、1乗か3乗しか生える気がしない。
E - LEQ and NEQ
包除っぽいけど全然できないので別の方向から考えてみる。前から見て初めて条件を破る場所を固定するか。それもできないので真正面からやってみる。前から何通りあるか見ていって、A_iが小さければDPできる。で、実際はクソでかいけど、DPの更新は自分以外の場所の和でしかないので、全体の和がわかっていれば差分はDPが進んでもパタパタ変わるだけ。A_iが大きくなる場合は簡単で、上に付け足す。小さくなる場合は頭を適切に削る。処理を書こうとして20分あっても無理だったが、解ける問題には見えた。
最初からEだけに注力していればとも思うが、これは後から考えても判断のしようがないなあ。今回だったらDE交互にやるのが無難ってことか。
