ギリギリでノンペナ7完。ここ数日微熱があって少しずつしか回復していなかった。ギリギリで回復が間に合ったという感じ。今日は思いがけずたくさん昼寝した。睡眠はちゃんととっていたつもりが、体調が悪いから実は足りていなかったのかもしれない。8割の力を出せればいい、くらいの気持ちだったので、珍しくウンコも出なかった。前半は簡単で、緊張もしなかった。
A - Lexicographic Order
不等号で辞書順比較してくれるんだよね。それを利用して（同じ桁数の）数の大小を判定するとかはあっても、そのものを問われることは少ないので、逆にちょっと焦る。
B - AtCoder Quiz
これ好き。簡単なのは明らかだけど、いい実装方法がすぐに出てこない。楽しい。xorも思いついたけど普通にテーブル作って出現してない文字をACにはさんで出力した。
C - Inverse of Permutation
E問題辺りで当たり前のように使われる典型をシンプルな形で教えてくれる。用意する配列はPではなくQ。
D - Cutting Woods
左端からxメートルの地点に付いてる線が「線x」と呼ばれているの、けっこう混乱した。整数の添え字みたいなもんだからおかしくはないけど。最初に考えたのは逆から見てUnionFindだが、両端に番兵を入れてstd::setを使うだけでいいのでそちらを実装。
E - Sorting Queries
問題文を読んでからトイレ（おしっこ（ぷよぷよ観てたせい））に行ったけど、その時間ではわからなかった。図にしてみるとすぐわかった。priority_queueとdequeを使うアイデアは早くに思いついていたが、全体をその両方に入れるのではなく、ソート済みとそれ以外で分けて入れればいい。dequeからpriority_queueへの移動もO(Q)回しか起こらない。あとはクエリを処理するだけ。面倒なのが2番目のクエリで、priority_queueが空ならdequeから取り出す。
F - Make Pair
いきなり難しくなる。制約が区間DPだと言ってるけど、境界がふにゃふにゃしてるから合体させることができない。改めて正面から考える。一人固定して考えるとこいつとペアになれるのは距離が奇数の相手だけだ。そして相手も固定すると、はさまれたやつらを全部ペアにしてからペアにするしかない。内側の区間についての答えがわかれば外側（両端をペアにする区間をこう呼ぶことにする）もわかるし、外側同士は混ざり合わないので掛け算とかでDPが進む。問題は外側区間を組み合わせて区間を作る通り数が難しそうなこと。DPでできそうではある。左から見ていって、そこまで何通りかわかればどういう組み合わせでそうなったかはたぶん関係ないので。これを左右からやって合併させることを思いついたが、重複があるのでダメだった。内側と外側（当時は殻の有無みたいな捉え方だったかな）でとにかく混乱する。最終的には、区間の一番左の人と誰がペアになるかを固定して足し上げる方針に。DPテーブルは、区間の左端の位置と幅（偶数）の2次元。位置2Nから幅2Nは0通りみたいのを許容するかでかなり迷ったが許容しないことに。添え字ガチャになったときのためにもコードはできるだけ短くしたい。実装方針にも色々なトレードオフがある。内側と外側でDPテーブル2つ持ったけど、片方で済むかもしれないと途中で思った。でも時間もないのでこのまま。幅0の答えは1だと思うけどこれを入れてないので三項演算子や場合分けでどうにかした。2つの区間の合成は、少なくとも片方が"外側"なら混ざることはないので独立で掛け算できて、さらに混ぜるときの順番で二項係数が掛かる。ここで2で割るのを忘れてサンプルが通らなかった（区間の幅の半分の回数だけペアを作る）。
G - Groups
まず、M=Nの場合を考える。グループが区別されないのが厄介そうだが、区別して空グループも認めれば簡単。空グループは包除で処理できそう。もう少し考えると、グループをそこに属する人の最小番号でソートすれば順番は一意になる。つまりkの階乗で割るだけでいい（ほんとか！？（ほんとだったみたい））。さて、Mで割ったあまりを考えると、N=M*Q+R（Rは0以上M未満）として、長さQの列がM-R個と長さQ+1の列がR個できる。それぞれ同じ列の人同士は同じグループに入れない。列毎に入るグループを決める。入る場所は二項係数でわかるので、長さ毎にまとめてpowで計算。5000^2でループの中にpowでlog付くのは嫌だがとりあえずサンプルが合うまでこれでやろうとする。が、なかなか合わないので諦めて前計算するのを書く（どちらも好手）。入る場所をK個中Q個とか選んで決めたらそのうえで誰がどこに入るかを決めないといけないのだった。階乗にpowかけないといけなくてここも少し時間かかった。
Kが小さい順にやればその結果を利用して包除できるの全く思いつかなかったな。自分は愚直コードを書いてそれを見て前計算できそうなところをしただけ。
毎度のことながら、Hを読む時間がない。
