5完。DEが苦手寄りながら頑張れたと思うが、苦手寄りなのでEまでの順位は悪いし、FGも解けないのではぼんやりと暗い気持ちが残るのみ。
A - Integer Sum
ついにループ使わなきゃ解けない問題を出しやがった。個人的にはそれが悪いとは思っていない。さすがに簡単なので早解きできた。
B - Everyone is Friends
けっこう難しかった（「どの二人も少なくとも 1 回」のあたりが）。100*100の配列を用意しておいて、各舞踏会について参加した人のペア全てチェック。解説を見るとxが昇順で与えられることを使っている。忘れてた。
C - Max Even
簡単そうだと思いながら具体的には何も見えないまま入力部分を書く。和が偶数になるのは偶数+偶数か奇数+奇数のときなので、2個のvectorを用意しmod 2で振り分ける。あとはそれぞれのvectorについて要素数が2以上だったら大きい2つの和で答えの最大値を更新する。ソートしたけど最初からpriority_queueでもよかったな。
D - Root M Leaper
まあ円周上の格子点なんてそう多くはないだろうけど。仮に3乗になったとして一応耐えてるか。縦にi進んで横にどれだけ進んだら距離sqrt(M)にできるかを各iについて求める。BFSする。円周上の格子点は1/4強くらいしか列挙してないので、縦横それぞれ反転も含め4通りやる。行き先がマス目内で未到達なら更新。
E - Add and Mex
とっかかりがないので一旦飛ばすが、Fを読んで「考えたくねえｗ」と思い戻ってくる。まず、mexはそんなに大きくならないだろうという感覚がある（もちろんNにはなりうるがそういうのの個数は少ないだろう）。i回目の操作後Aに0が含まれるかという判定問題にしたら？平方分割もできそう。Aの後ろはガンガン足されるから調和級数みたいのも。色々考えているうちに気づく。答えはN以下でN未満の数しか関係しないんだから0以上N未満の数だけ見ればよくて、Aの各要素についてそうなる回数はA_i/i回くらいしかなくて全列挙が間に合う。
実装がけっこう大変だった。0以上N未満の列挙がけっこうきつくて、後回しにしてサンプル試すが通らない。途中経過を出力してみると、同じ数が複数ある場合をケアしてなかった。0以上N未満になる区間は、雑に計算して少し広い区間を見ればいいと思った。あまりやりたくない方針だが。が、そもそもN以上になった時点でループを抜ければいいと気づく。スタートだけ計算してマージンとっておく。
F - Two Strings
頑張って問題文を読むと、atcoder::suffix_arrayが思い浮かぶ。1列に並べれば、先頭から見ていって同じか小さい相手が何個あったかカウントしておいたのを足していけばいい。S+S+T+TとすればN*2個の対象文字列がsuffixのprefixに全て現れる。ここで、辞書順で同じになる場合が厄介。suffixは長さNより長いことがある。そこで、f(T, j)がf(S, i)より小さいものをカウントしてN^2から引くことにする（S+S+'@'+T+Tみたいのも考えたがややこしくて捨てた）。先頭のN文字だけ見て一致する区間を考える（atcoder::lcp_arrayが使える）。Tの個数は常にカウントしているが、その区間内では答えに足す変数への反映はしない。区間をまたいだときに反映させる。提出してWA。
自信はなかったけど、見直すとどう考えても正しい。かなり経って、文を入れ替えてAC。区間をまたいだとき次の区間の先頭がTだとそれをカウントして反映させてしまっていた。ソースの見た目が自然なので気づかなかった。
G - Yet Another mod M
FGが同じくらい解かれているので、そろそろいい結果が欲しいのもあり、Gをまず考える。過半数というのが何かありそう。ただ、全てのペアを考えても両方過半数側になるのは1/4くらいしか保証されないし、ペアじゃなくてもっと増やすともっと下がるし。差だけが重要というのはトイレで気づいていて、最小のA_iを選ぶと仮定すれば全部からA_iを引いてしまって何かの倍数シーケンスを見つければいい。見つける方法がわからない。終了後、乱択というキーワードを見るが、全然ピンとこない。
（追記）コンテスト中、なぜMが3以上なのかと考えて、2だとNが奇数のとき必ず過半数になってしまうからだと思ったが、そこから約数が上位互換になるということに気づけなかった。そうなるとMの候補が絞れるので乱択もできそうになってくる。基本的には2数の差の素因数を見ればいいが、2が使えないのでかなりややこしい。あーでも「3だとダメだが6ならOK」というケースはないんだな。2^u*3^v型の整数を考えると、2の代わりに4を考えればいいか。4の倍数でない2の倍数は、単に2で割って損しない。過半数判定部分は、そもそも選んだ2つが過半数に含まれるという仮定なのでそれとあまりが一致するものを数えるだけ。乱択部分は、運良く過半数に含まれる2つを取り出せればその差の約数を全部試せば答えが求まる。1/4くらいの確率でそうなるから、100回やれば十分すぎる。Aの中で同じ数が過半数を占めていれば場合分けしていいが、微妙に足りないくらいだと乱択が上手く働かない気がしてめっちゃ悩んでたら、そういえば「相異なる」って書いてあった（道のりが長いと忘れる）。
（解説を見て）2が使えなくて混乱してたけど、自分も最初思ってたけど約数を全部試すだけだった。Nが偶数のときはN/2個のペアを作ってどちらも含まれるものが存在するなあとは思っていた（それを利用する方法思いつかないのなあ）。Nが奇数の場合は輪にして隣同士を全部見ればいいのね。
