3完。一生青パフォしか取れない。つまんなすぎる。
A - Chocolate
「ルジンの問題」（名前は知らなかったので今ググった）みたいなやばいのも存在するので怖い。ただ2冪ということでそんなに変なことは起こらなそうでもある。とりあえずサイズ毎にカウントしておく。左上から貪欲に取っていくというのはどうか。しかし貪欲といっても右に行くか下に行くかがあるし、小さいのを取ったら長方形がどんどん増える。1個チョコを取って3個の長方形に分割されたとして、長方形をまたぐような取り方が必要になることはおそらくないと思うが。
AとBを交互に考えて途中から順位表も見ながら。全く解ける気がしない。
横だけ見て、4+4+4+2+1みたいに分割できる。縦にも同じことをすれば？もう少し考えて、HとWのビットが立っているところを全探索。例えばHで8、Wで2のビットが立っていたら、8*2の長方形が取れるが、2*2が4個として使う。これで、1から2^29までのチョコに分割できた。あとはこれを大きいほうから貪欲に使っていく。余ったものは4つに割って一つ小さいチョコにする。小さいチョコを使えるのは小さいのだけだから、小さいほうからというのもありそうで、両方が正しい方法であるイメージができず困ったが、大きいほうからのを書いてACした。
レーティングのことを考えると、未証明の貪欲をいかに素早く何も考えずに通すかというゲームになり、クソゲーが過ぎる。
B - AtCoder Language
Kが小さい順に考えていくが、なんかやばそう。K=4くらいで頭が限界になる。かなり色々考えて法則性が全然見えない。同じ文字2つが両端じゃないといけないK=2と、K=3の様子が、まとめて処理できる気がしない。
左からK-1文字選んだら、そこより右は全部違う文字でないといけない。ここから更に進んで、左右から合計K-1文字選んだら、その間は全部違う文字でないといけない。これは必要条件だけど、十分条件にもなってたりしませんか？つまり、連続するN-(K-1)文字をどこから取っても全部違う文字、これは1個ずつ掛け算していけば求まる。例外は思いつかなかったし、サンプルは通ったし、ACもした。ゴミ。俺は何もできなかった。
C - Election
開票結果の列が同じでも得票数の差の変動は違うこともあるわけじゃん。難しそう。とりあえず差のグラフを描いてみて、隣り合う2つの異なる票が入れ替わったときの様子を見る。あれ、これって端からN-1回入れ替えることで全部列挙できてるね。ということで、累積和（得票数の差）を用意して端から実際に入れ替えていく。開票結果の列が変わったとき、それは新しい列だ。0票のときとN票のときの差は順番によらず一定。それ以外のN-1個は、それぞれ変化したなら変化した場所が異なるので同じ文字列は現れない（たぶん）。比較するとき、負0正の3通りに直してから比較しないとサンプル通らないね。あっさりACした。
D - Distance Ranking
順位表見てEへ。問題はざっと読んだけど2次元だと思ってた。終了後少し考えたが、次元をどう使うんだ。今気づいたけど、次元を使い切るには1個ずつ追加して毎回新しい次元を使うことになるんだな。しかし格子点しか使えないから、ななめも必要な可能性もあるか。距離の条件がイメージしづらい。こういうのコンテスト中にやりたいんだよなあ。
（追記）解説のヒントを見たが、Nが3より大きいときどうすればいいかわからず。そもそも点がN個だとN-1次元しか張れないんだな。この立方体の正三角形見えないのもひどい。解説の微調整のところを見て自分でもやってみると、なるほど。急に昔の話をするが、高校の物理の実験で、振り子の長さを測ったとき、振り子の先端の玉には大きさがあるので重心にものさし（何使ったんだろ）をあてがうことはできない。そこで横にずらして測ったが、真横ならほとんど誤差が出ないことはわかっていた。このN次元空間では、微小な距離だけ動くとき、相手がいる方向に動けばそのまま相手との距離に寄与するが、それと垂直な方向へ動けば距離はほとんど変わらない。実際計算してみてもそういうのは全部2次の項になる。実装自体は単純だが、ステップ数があるし理解に時間かかったし、思いつくのが今の実力じゃ無理だし全部思いついたとしてコンテスト中に書けたかあやしい。
E - Last 9 Digits
2分くらいかけてチェックしたところ、被りがなかった（つまり条件を満たすnは常に存在して10^9未満）。なんだその性質。フェルマーの小定理でググってみたけど数が大きくてあんま役に立たない。ワンチャン、t=t^tを繰り返して短時間で見つかったりしないかなとか思ったけどダメそう。けっこう手は動かせたが、何かできたかというと。
（追記）3^3=27 mod 100というところから、103^103=27 mod 100とかも言えると嬉しいが、オイラーの定理を使ってもφ(100)=40だから100で戻ってくるとは言えない（実際には100で戻ってくる）。この40の計算も自分ではやってないし。そこでまた全探索してみる。これも2分くらいかかるけど10^2から10^9まで全部確認できた（10^1のときは例えば3^10=59049なので10乗ではダメ）。あとは下から1桁ずつ決めていく。最初の2桁は全探索。解説の、Pythonで数十分というのを見て思ったけど、今回のケースは実行速度10倍の違いが致命的だったんだな。自分はコンテスト中に2分くらいかけて全探索したが、これが20分だったらコンテスト中には試せない（10^8まででいい？いやー10^1は例外だったじゃんか）。
（追記）カーマイケル関数というのでわかるらしい。WolframAlphaにCarmichaelLambda[10]と入れると4が返る。100なら20。
