F以外の6完。昨日と同じで立ち回りは良かった。
A - A Healthy Breakfast
日本語の単語と英大文字の対応付けが3個もあって大変。各文字が何番目にあるかを配列に格納したが、これ配列じゃなくてmapでもよかったか。if文を書き殴るのとどっちが早いんだろね。やりたくはないが。
B - Vertical Reading
区切るの具体的な意味がわからない。サンプルでイメージをつかんでなんとなくでコードを書く。計算量を確かめて全探索。
C - Move It
難しくて緊張してオシッコ。さすがにトイレで解ける。荷物が入っている各箱について、最も重い荷物は動かさなくていい。当時どこまで考えてたかおぼえてないが、全部バラバラの箱にするためには1個を除いて動かす必要があるので下限にもなっている（下限と上限が一致するのでそれが答え）。各箱について最大値を求めて、N個全部の荷物の重さの和から引いていくと答え。実装上は、荷物が0個の箱の最大値は0とする。
D - Ghost Ants
0.1が足されているのは、ちょうど時刻Tに同じ位置になったのもすれ違い扱いということ。すれ違うのは違う向き同士のみ。右向きなら、自分より右で左向きの蟻を見ればよく、あとは時刻Tまでという制限を考えればいい。T*2だけ距離が詰まるので、距離がT*2以下のものを数えればいい。これは二分探索でできる。インデックスの情報は要らないので、座標は向き毎にvectorへ突っ込み、似た処理を2回書く。1回にするため反転処理を書くことも考えたが、めんどくさそうなのでやらなかった。絶対値が3*10^9程度になりうるので、座標関係は全部64bit整数にした。順序付きペアを数えたので2で割る必要があるが、忘れていてサンプルで気づいた。
境界でかなり神経を使うので疲れた。WAだったが、軽く見直して違和感がないのですぐEに行った。いい動き。あとで戻ってくると、Xがソート済みでないことは初期に認識したのに忘れていた。やはりこれだけしんどい実装だと抜けが出る。
解説を見て。あーしゃくとりできるのか。気づいたうえで二分探索を選びたかったね。
E - Random Swaps of Balls
よく読むと、1番目以外の位置に区別がない。なら簡単そうだが、考えていくとけっこう厄介そうな気配。1番目のボールが移動する確率は、求まるんだけど2/Nとは異なる式になる。当初の目論見では、一旦1からNのランダムになってしまえばその後はずっとそのままというのが使えるはずだったが、微妙に違う。1回目に1を選ぶのと2回目に1を選ぶのに共通部分があるのできれいな式にならない。仕方ないので、2からNのランダムを考える。Kが小さいし、行列累乗も面倒なので、DP。N=1をケースが大丈夫なことを確認しながら書き、サンプルが通ったあとでN=1のケースをいくつか実行して1を出力することを確認した。
1番目とそれ以外の2通りの確率を持っていたが、言われてみれば2通りなら片方だけ持てばいい。3通りを2通りに減らす意味はあんまないけど、2通りを1通りに減らせるのはでかい。気づかねえなあ。
解説見てO(log(K)+log(mod))で解き直した。この高校漸化式若干苦手意識ある。
（追記）N*N通り中、1番目のボールが移動するのは(N-1)*2通り。ここに、3番目と4番目を入れ替えるとか1番目と1番目を選んで何もしないとか、とにかく1番目のボールが動かない操作を2個選んできて加える。すると、全部でN*2通りになり、これらの中からランダムに選ぶと1番目のボールが（1番目の位置も含む）ランダムな位置へ移動することになる。ここまでわかればあとは簡単で、K回の操作で「ランダムな位置への移動」が1回も起こらない確率（(1-2/N)^K）を求め、1番目にいる確率と（1番目も含めた）ランダムな位置にいる確率から期待値を求めるだけ。なぜか、N=1でも正しい答えを返す。さすがにコンテスト中だったら場合分けしただろうな。最初の印象通り、簡単なコードで解ける問題だった。内容が簡単かはよくわかってないが。
F - InterSections
さすがに、LかRでソートする。rよりlを優先する問題なので、どちらでソートするといいかを観察する。lやrの候補の個数はO(N)になりそう。Lでソートして、lを決めたとき、Lがそれより小さいものに対してはrが大きいほどいい。Lが大きいものに対しては、小さいほどいい（と思っていたが、Gを通してから戻ってきたらそうとも限らなくてヤバ）。単調性みたいなものも見えないし、高速化できると思えない。ここで順位表を見てDとGに行った。
G - Suitable Edit for LIS
LISの問題で今度こそBITを使うかと期待してしまうが1個も見たことない。どんな作問がありえるか（あるいはありえないか）自分で考えておくべきかあ。やる気なし。
普通にLISの長さを求めるコードを持ってくると、前後からやるだけでいけそう（ここまでに相当長い時間がかかっているが、言語化できない、難しいこと考えるの嫌で悩んでただけかも）。明らかに（なら証明しろ）、操作によって高々1しかLISの長さは大きくならない。先頭か末尾をいじる場合は簡単なので別途処理しておく。先頭でも末尾でもない場所をいじってLISが1だけ長くなる場合、元のLISの隙間をつなぐ形になりそう（1 2 9 4 5を1 2 3 4 5にするみたいに）。LISを求める処理を前後からやって、途中経過（そこまでのLISの長さとその末尾としてありえる最小値）を記録しておく。あとは、前後をつないで元のLISの長さになっていてかつ間に入れる（差が2以上）なら1伸びる。自信はなかったし、どこが625点なのかもわかっていなかったが、ACしてた。
