6完。なんかみんなEまで速くない？自分はまあ順調に解いていった感じ。
A - ab
なんか簡単な書き方ないかなあと思ったけど、普通にif文をコピペして逆にした。ショートコード見ても「abかbaを含む」で判定してるし、しょうがないか。
B - A^A
オーバーフローがなければB以下の範囲で試すだけ。実験してみると15^15までは10^18以下で、その次はオーバーフローする模様。ということで、16未満の範囲を全探索。
今気づいたけど16^16って2^64か。いやこれはコンテスト中に気づきたかったな。
C - Number Place
数独。やりたくねーって言いながら実装したらそこまで時間かからなかった。長さ9の配列が全部1か判定する関数を書いておく。1引いておくと0以上9未満になってカウントしやすくなる。
D - Good Tuple Problem
問題文を読むのが大変。二部グラフっぽいとはすぐ思ったが、ちゃんと認識するまでは時間がかかった。それでそっちがNなのね。頂点数Nのグラフがあって、A_iとB_iを結ぶ辺があって、各頂点を2色で塗って、辺の両端は違う色である必要がある。普通に二部グラフか判定する。
この判定ライブラリにしたほうがいいかなあ。書けるけど分量からして一瞬では書けないわけで。ライブラリにするかどうかは難易度で決めてる感があるけど、競技としては時間で考えるべきだよな。
E - Maximize Rating
AtCoderのレーティングシステムを簡略化したようなやつ。実装経験がある。これまでの値を0.9倍して足してくみたいな処理でできる。参加順で見ればそれまでに何回分選んだかが同じならその値を比較できる。DPは選んだ回数毎に値を持って最大値を更新していく。0から0と1へ、1から1と2へ、2から2と3へ遷移するみたいなやつ。配るならこの通りでいい。貰うならちょっと面倒。しかし、同じ回数への遷移はin-placeなら何もしなくていいので、回数が多いほうから順に1回少ないところから貰っていくだけでいい。回数毎に最大値が求まったらそれぞれレーティングを求めてその最大値が答え。
-INFに0.9を掛け続けて0に近くなってしまう罠があったらしい。自分は必要なところだけ処理していたので大丈夫だった。値の-INFが変更されるときの処理は（全て）認識していたのでまあ。
F - Apples
長方形の領域にいくつか点があって、D*Wの長方形で最大いくつの点を覆えるか。有名問題っぽいのに意外とできない。まあ時系列で考えて、BITかなんかで指定した位置に+1とか-1とかすれば情報としては持てるけど、どの区間が最大値かというのがわからない。最大値が知りたいならセグ木、遅延セグ木で区間加算更新と区間最大値取得ができればいい。ノーマルセグ木で（BITのいもす法的に）なんとかできないかと考えるができなさそう。ということで遅延セグ木でさっきのができるか試してみると、できる。区間に定数を足すだけなので、最大値もその定数を足すだけ。各時刻について、足したり引いたり。全ての時刻について処理するのでしゃくとり的な部分の処理は不等号ではなく等号でいい。これちょっと見慣れないので二度見したけどシンプルにできる。運良くAC。
G - Many Good Tuple Problems
二部グラフの0側と1側と孤立の3つにどの頂点が割り当てられたか決めれば簡単。よって簡単そうに見える。しかし、なかなか包除がまとまらない。これだけしか解かれてないのは「難しいんだろうなあ」って感じだけど、提出して不正解の人の割合がこれだけ多いのは意味がわからん。
