3完。時間かかった。昼間のコンテストは外がうるさいことがある。
A - Area Sum
1行だけだったら、左端と右端の平均でいいが。長方形の場合は、四隅の平均でいいのか考えてみるとそれでよさそうだ。長方形の縦横のサイズを固定して、どこに置くかを考える。まず左上隅に合わせて置いて、そこから右に1うごかすと平均が1増える。下に1動かすと平均がM増える。ということでサイズを固定したら高々1通りしかない。Vを2倍したいのだけど、単に四隅の和で考えることにしてVを4倍にした。できるかどうか判定するが、ここで無限に混乱した。簡単に見えて、知らない処理なんだよな。
B - Best Strategy
これは不可能でしょ。Nが20万なのにN!通りの中から最適なものを選べって。とりあえず式変形すると、後ろから足して掛けての繰り返しになる。だいぶ経って、隣接する2要素の入れ替えを思いつく。元が何であっても、足して掛けてを2回分やったときの元の量の減り方は同じ。ということでソート。あとはこれがちゃんと順序になっているかだけど、わからん。
C - Count Dividing XOR
まず実験をする。2進法で、A=101101, B=101000, A^B=101 みたいなパターン。とりあえず実装してみる。A^Bを10^6通り試す。2重ループになるが、logが付くだけで済む。10^6でlogが付くのは珍しいけど、普段の2*10^5は入力を(時間がかかるので)増やせない都合からくるものでしかなく問題ない。実装しているうちに、さっき見つけたパターンが正しいかとか関係なく全探索すればいいと気づきそのように書いていく。詰めることができるところまで行っていたがあまり詰めずに提出してしまった。
D - Dual Rotation
順列はN!通りあるがそのうち高々N^2個だけ(ダブりがあるかも)。隣との差のsuffix_arrayでできそうだと思ったけど同じパターンがたくさん現れるとTLEしそう。lcp_arrayとかも使ってうまくできそうな気はするが、具体的なことは全然見えない。先頭が思ったより楽に決まる。そこから、指数関数的に候補が減っていくなら全探索できるんだけど。実際はそうとかぎらないので。