K以外を通して94点。PASTバチャってどうしても直前に食事をとることになるんで、トイレに行きがち。今回は牛乳飲んだのがアホだった。4回くらい行った。トイレで考えるの効率いいので普通はそんな気にしないけど、4回手を洗ってるわけでさすがにロスが大きい。
A - うさぎとかめ / The Tortoise and the Hare
複雑そうに見えるがタイムを比較するだけでいい。タイムにA*Bを掛けたもので比較する。
B - 2文字 / Two Letters
mapで文字列をカウントして、mapは辞書順に列挙できるので前から最大値を求める。
C - オーダー/Order
10^9以下のところだけ'o'に変更。llでやれば初めて超えたところではオーバーフローしないしそこでループを抜けるので大丈夫。
D - 似ている文字列/Similar Strings
ややこしいけど連結成分内は自由に変更できるのでUnionFind。
E - 変わった数列 / Strange Sequence
なぜか、i=2のとき1個目の操作で2を追加しないと思い込んで混乱した。見た目は怖いけど、再帰的な要素もなく、1 212 32123 ... と繰り返すだけ。何個目の塊かをまず求める。M個の塊でM^2項になるので、平方根を求める。誤差があったときのために、NがM^2以下となる最小のMになるまでwhileを回す（最初間違っててグダグダ実装）。(M-1)^2を引けば今の塊だけの話になるのでそうして、塊の真ん中より前かで場合分け。
F - シューティングゲーム / Gun Shooting
よく読めばだるま落としするだけ。メインの処理はO(N*H)で済む。都度落下させないとどれを消すかわかんなくなる。
G - 木の判定 / Is it a tree?
N-1辺なのでUnionFindするだけ。mergeされないことがあったらダメ（全体を連結にするための辺が足りなくなる）ってしたけど、最後に頂点1を含む連結成分のサイズがNかで判定してもよかったな。
H - 2つのナップサック/Two Knapsacks
問題名の通りナップサック。2次元になったことでin-placeに更新できるかというのが関心事。後ろから貰っていけばできる。また、DPテーブルをグローバル変数にしたので0で初期化されており、これは「重さがちょうどi,jのときの美味しさ合計の最大」ではなく「重さがi,j以下のときの美味しさ合計の最大」になっていて、dp[A][B]を出力するだけでいいので都合がいい（前者にするためにはdp[0][0]以外を全部-INFで初期化する）。
I - お片付け/Clean up
「倉庫番がこんな計算量で解けるの！？」と思ったけど、荷物が1個なら状態数少ないから全探索できるんだね。ABC289のEみたいにBFSするだけだが、1文字変数名を使っている弊害が出て沼に沈んだ。
どう書くのがいいか、他の人の提出を見たり自分で書いたりして頑張ってみたがあきらめた。
J - 完全週休二日制/Holidays
実装で沼った直後にこういうのはやめてくれ。2022年1月1日からの経過日数を求めればよい（2022年1月1日は0、2022年1月2日は1となるようにする）。月の日数を入れた配列を作り、累積和をとっておく。また、位置を指定して年月日を数値化しておく。あとは日数を寄せていく。まずその年のうるう年ぶんを加える（うるう年の3月以降であれば+1）。日と月を0-indexedに直し、累積和作っておいたやつを足してその年の1月1日からの経過日数が求まる。最後に、2022年から前の年までの日数を愚直に足していく。経過日数がわかれば、除算で先週までの週の数がわかり、あまりでその週に食べた数がわかる（土曜日で始まっているので都合がいい）（最大で2）（「最大で」という思考をしたのでmaxと書いてしまったがmin(d % 7, 2)が正しい）。
K - 部分列/Subsequence
部分列の個数というのがまず難しい。S=Tのケースが解けなければ話にならないのでそれを考える。少しして、部分列をとるときどこで拾っても同じなら最初のを拾うという固定の仕方を思い出す。スキップしたものを拾ってはいけないから26bitの情報を持つ？いやそれは無茶だろ。最後に使った文字を持っておけばその間にある文字はセグ木とかでもわかる。で、この問題を解くためにはS,T両方の部分列となっている文字列の数を求める必要がある（包除）。それがまともな計算量でできる気がしない。
（追記）復習をとりあえず終えたと思ってブログを投稿したら解けてないこれを放置していた。累積和でできそうだ。まずSの部分列の個数から。この文字で終わる部分列の個数を考える。直近でこの文字が出たのがいつかは、長さ26の配列を1文字毎に更新しておけばわかる。最後に選んだ文字がそこより前だったらダメ。そうじゃないやつの和が知りたいので累積和の形で持つ。空文字列も含めておき、どの文字も-1文字目で選んだ扱いにしておく。S,T両方の部分列の個数は、同様のことを2次元累積和でやる。SとTの文字が一致しないときは、そこで終わる部分列は0個。一致するとき、遷移元は長方形の領域になる。和がわかったら2次元累積和を更新する。かなり難しい。
L - だいたい最長共通部分列 / Almost LCS
普通に最長共通部分列を求めてKを足す（短いほうの文字列の長さでminをとる）という方法の反例が思いつかないけど、証明もわからないので普通にDPを書く。書き換え回数が大きいほうから貰っていく（今見たら向き関係ないか）。書き換え回数0は普通の遷移だけ。
上で反例思いつかないと書いたけど、サンプル2が反例だった。abcdefghとijklabcdみたいのだとKが中途半端に大きくても役に立たない。
M - 逆転/Reversal
N本先取なのつらい。とりあえず感じをつかむためにN本先取がN+i試合で終わる確率を足して1になるコードを書いてみる。さて、「逆転」は、2人の本数が同じになる状態を必ず経由する。また、本数が同じになったら1/2の確率で逆転が起こる。そこで、本数が同じになる回数の期待値を求める。i=1,2,...,N-1に対してi本ずつ取って同じになる回数の期待値は？同じになる前後の通り数を掛け算とか考えて無理になってたけど、期待値さえわかればいいんだからi本で並ぶ確率を求めるだけだった（前だけでいい）。和をとって1/2倍すれば答え。高橋くんと青木くんが対称なのでいろいろ考える必要がない。
N - 壁の建設計画/Building Plan
右上から左下へ壁を作る必要がある。ただし最適な壁はぐねぐねしてるかもしれない。H,Wがかなり小さいし、（直前の壁以外と隣り合わないなどの条件を付ければ）経路を全列挙できるのかとも考えたが。冷静になると単にダイクストラだった。Aさんの移動は4方向なのに（なので？）壁は8方向なんだな。
解説を見て。いやフローはちょっと思ったけどできるんかい！全然わからなかったけど、とりあえず解説通りに実装してサンプル通るところまでやることで少しずつわかってきた（フローっぽい提出見て修正できたけど、解説で容量∞の辺を張ってるのTからSが正しいよね）。イメージとしては、グリッドには上の世界があって、同じマスの中で上に移動することで隣のマスへ滑り台で移動できる。コストc_(i,j)を払うことでマスi,jでの上への移動をブロックできる。最小カットの塗り分けを考えると、スタートの色からゴールの色への辺を全て塞げば（スタート地点からはスタートの色にしか行けなくなるので）ゴールできないし、それは最小カットの容量ぶんのコストで実現できる。もっといい塞ぎ方があったとすると？よくわからん。
O - 面積クエリ / Area Queries
頭が壊れそうになりながら頑張る。面積は外積で求まるので、その相手の部分の和がわかっていればよさそう。偏角ソートをする（整数で頑張る）。クエリ先読みもやはり必要。i番目のクエリがソートしたあとの状態で何番目になっているかを持っておく。現在盤面に出ている点の座標の和をBITで管理（ソート済みなので誰かに対して外積が正になるやつらが区間になっている）。で、クエリを処理。偏角が180度未満かで場合分けし、自分のいる場所から180度先（外積が負になる境目）がどこにあるか二分探索する。先頭から二分探索すると外積の符号が先頭と異なる場所を一つ見つける必要があってそれは難しいが、自分の場所から始めれば問題が解決している。自分やちょうど180度先と同じ偏角の点がたくさんあったとしても、外積0で区間に入れても入れなくてもどうでもいいのでその点では楽。区間を求めたらBITで和をとってくる。これで変化量がわかるのでその累積和が答え。あと、BITに、追加（または削除）した点のぶんを入れる。K問題は半ば諦めていて、終了間際まで時間をたっぷり使って実装した。
