6完。今週は体調などの色々で競プロを全くやっていなかった。問題文が読めなかったのはそのせいか、あるいはBとかが難読だったからか、微妙なところ。
A - AtCoder Line
値が区間に含まれるかを簡単に書きたいよなー。まあ不等号2個で書けるのでそれを2個書こうと思ったんだけど、XYを必要ならswapして大小関係を揃えて1個で済ました。A問題にしては難しすぎる考察を入れたので、時間が（A問題にしては）かかってしまった（実装時間を10秒減らすために考察時間を30秒増やす行為）。まあ問題文がかなり複雑で、時間がかかること自体はしょうがない。
B - Typing
SがTの部分列になっているのだろうけど、答えは一意に定まるのか？と思ったけど、SとTを見れば高橋君の行動（バックスペースキーを押したかどうか）は決まるので大丈夫っぽい。結果的に、貪欲に部分列をとる実装に。SとTどっちでforを回すか迷ってTにして、答えのvectorにどちらのインデックスを入れるか間違えて、それを直すときインクリメントを付けたままにしてバグらせて、まあ酷かったけど問題が難しすぎるからしょうがない。
C - Standing On The Shoulders
頭の高さが巨人P_Nよりも高い巨人がいる可能性もあると気づいてえらい。まあそれは関係ない。肩の高さは順番によらず一定なので、肩と頭の差だけが重要になる。問題を見た第一印象の通りの簡単さで、本当に300点かと疑心暗鬼になってしまった。
D - Permutation Subsequence
いかつい問題文だが、連番ができるだけ狭い範囲にあるのを見つけるということで、しゃくとりみたいにできそうで、std::setを使えばできそうだ。本来なら最初のK個を入れてからN-K回ずらし、2個のfor文を書くところだが、区間の個数がN-KではなくN-K+1なのが気持ち悪くて1個のfor文にまとめてしまった（また時間がかかることをする）。jがK以上になったらj-Kを消して、jがK-1以上だったら最小値を更新する。末尾の要素は*st.rbegin()でわかる（今回は思い出して使えた）。
いやー、セグ木やSWAGで解けるの全く気づかなかった。
E - Clique Connect
最小全域木だけど、辺がめちゃくちゃ多かったりするからなんとかしてねという問題。普通にクラスカル法でできそうだ。intとvectorのpairを持ち重みのintでソートしておく（vectorのswapはO(1)だよね）。重みの小さい辺から追加していくが、K頂点にK*(K-1)/2辺を加えたとして順番にK-1本の辺でK頂点をつなげばその時点で連結になるのでそこだけやればよく（それ以外は愚直にクラスカル法やってもスキップされる）、これで計算量もOK。サンプル通らなかったけど、頂点1の連結成分のサイズがNでないなら-1を出力するんだ。
解説は間接ソートか。迷ったけどそっちのがよかったかな。
F - Estimate Order
ポテンシャル付きUnionFindでピースに分解できて、あとは各ピースについて置ける場所が一意かどうか（置けることは制約で保証されている）。そんなのできるのか？と思いつつとりあえず実装しようとしたら、Nの制約に気づく（2*10^5とかだと思ってた）。じゃあbitDPでできるんだろうなと思って考えるも、4^Nとかになってしまう。ピースが大きければピースの個数が少ないから間に合うし、ピースが小さければどこにでも入るから簡単そう、ということで、ピースを大きい順に並べてDFSしてみる。サイズが2以上のピースは高々8個、サイズが1のピースはどこにでも置けるから探索不要。8!はかなり小さいけど、サイズ2の初手は最大15通りあるし、でもまあ現実的には途中で置けなくなる配置が多いだろうから余裕で間に合うやつだよねと（終了後に計算したら大丈夫そうだった）。
最初は、初手を全探索して残りをDFSで可能か確認と思ってたけど、実装が面倒なので少し考えたら、単にDFSで全探索してそこに解が現れるか見ればいいということに。解の個数をカウントとか迷走していたが、ピース毎に可能な位置をビットで記録すればいい（今気づいたが、2箇所以上になったらループを抜けていて、これでは枝刈りした先のピースが探索されずまずいか？）。ピースのサイズが1になったら、そこから先も1なので、そこから先のピース全部、今置かれてない場所全部が可能。
実装はマジで重い。この実装を1時間できっちり終わらせてるの、5年前の自分よりはっきり強くなっていると感じる。苦手分野だし、あまり価値を感じないところでもあるけど。UnionFindして、leaderの列をサイズでソートして、leader毎にポテンシャルの最小値を求めてそれを0に補正してピースをビットで持ち、DFSが終わったら自分のleaderの番号を予め作っておいたテーブルで求めその可能な位置が1通りならその位置と補正したポテンシャルを足して答えとする。ソートと復元がマジでやばい。
G - Socks 3
めっちゃ簡単そうなのに難しいらしくて、嬉しくて笑っちゃった。なにもできずFに専念した。
（追記）言われてみれば典型だが、どれも全く思いつかない。解説の「タンスから靴下を i 枚取り出した段階でまだ同じ色の靴下の組が存在しない確率」を愚直に求めようとしてみるべきだったか（愚直にやったら計算量ハチャメチャに大きくなるんで考えもしなかった）。「タンスから靴下を取り出す回数が i 回以上である確率」を直接使えるのも、経験してるけど身についてない。一応差をとると「ちょうど i 回の確率」もわかるけど。分割統治はスタックでやった。
