どうにか全完。
A - メダル/Tokens
何回買えるかを求める。
B - 分数比較/Fractional Comparison
制約を見てなくてサンプル通らなかった。何も考えてない。これ未だによくわかってなくて、中学校で習ったことを思い出してしまう。等しいのは先に判定しておいて、両辺にB*Dを掛けるけど、それが負なら逆になるんでxorを使う。
C - 三つ組の積 / Triplet Product
3乗が100万（の1/6）なのでsetと思いきや、積自体も100万に収まるので、現れたかどうかを配列でチェック。
序盤が軽くて助かる。
D - 坊主めくり/Bozu Mekuri
怖そうな見た目だけど、手札の場札の枚数だけ持ってシミュレーションできる。
E - 括弧列/Parentheses
スタック。末尾に括弧が揃ったら消すやつ。これ、4問ABCのDでこういうのが出たときにも思ったんだけど、なんで自分はこれを通せるんだろう。かなり高級な（？）概念に思えるんだけど。
（解説を見て）あ、スタックに入れる前に判定すればよかったやん。
F - 平均順位/Average Ranking
整数で処理するために1000倍して考える（このくらいの整数はdoubleで誤差なしで扱えるのでroundしてからキャスト）。パッとはわからなかったので、数式をいじって、この量をX-1ずつ減らすことができるんだなと。最初から満たしてるのを場合分けして、1000倍していることに気をつけて切り上げ除算。
G - 区間和/Range Sum
ド典型だけど、よく思い出せないし、自分で考えても「こんなだっけ？」ってなる。長さ0の区間は許されないので、累積和の前回までの最小（最初は0）と現在の累積和の差をとる。その最大値が答え。
こういうのでなかなか確信が持てなくなっていて、つらい。
H - 桁差の和/Digit Diff Sum
これ数列でよくない？数が10種類なのを自然に出す方法ってことか。左右を見てプラスに寄与するのが何回かを掛けて足していく。サンプル合わなくて、そういえば絶対値が付いていたと思い出す。方針は立ってたけど実装で迷走した。左右やる必要があるから、何が何個という情報を管理する長さ10の配列を左を見ながら増やし右を見ながら減らしていけばいい。数が等しいものは、片方でプラス、片方でマイナスとすることで0にした。なぜか和をintで持っててWA。
で、今気づいたけど（左右を区別せず）まとめてできるね。左右を見るのは最初の勘違い方針に引きずられた。デバッグに時間かかったのも、左右で不等号の向きを変えていたせいだった。左右を区別しなくていいんだよ。問題文ではN*(N-1)/2個の和みたいに書いてるけど、A_iたちの登場回数は2倍のN*(N-1)で、自分自身のとの差（N個）も含めると、N*Nになる。
I - 背の順/Order of Height
atcoder::scc_graphを使って閉路の有無を確認するだけ。Nが小さいの気づいてなかった。
J - 横断/Crossing
いよいよ後半戦。ここまでだいぶ楽だった。Hで少し苦戦した程度で、9問を通すのに1時間弱しか使っていない。
かなり難しそうな見た目だが、結局、直線が分ける2つの領域についてS,Tの2点が同じ側に入っているかを判定できればいい（直線上にないことは保証されている）。直線に垂直なベクトルとの内積をSとTと直線上の点で比較すればいいと最初に思った。そこからよくわからなくて色々式をいじっていると、その内積というのがP*x+Q*yで、直線上の点ならそれはRなのだった。いやあ、なんだろうね（わかってる人からすると迷走する理由が全くわからなそう）。あとは大小関係をxorして、その結果でWを0にしたりして、ソートして小さいほうからK個とる。
K - 整数屋さん / Buy an Integer
ここでトイレに（難しくなってきた）。桁和毎に最大値を求めるのかなとか思ってたけど、よく考えると難しそう。10の冪を考えてみると、桁和はどれも1で同じ。もうちょっと考えると、実は上から決めていける。買える最大の10冪を求めて、それが10000であれば100000以上の整数は買えない（100000以上の整数の中で、100000がそれ自身も桁和も最小なので）。そうして探索範囲が狭まったら、20000,30000と順に調べていく。30000が買えて40000が買えないとき、100000未満かつ40000より大きい整数は40000より高いので買えない。オーバーフローする恐れがあるので、doubleで概算してやる。なぜか1ケースだけWA。わからないので飛ばす。
Oまで解いて戻ってきた。10^9以下と書いてあって笑う。そういえば問題文にそんなこと書いてあったなあという太古の記憶。ひょっとしてオーバーフローの心配もなくなりますか。10^9より大きいものが買えるなら10^9も買えるのでminを取って出力した。AC、全完。
え、解説が桁和決め打ってるが。これを読む体力は残っていない。
L - 区間 / Segments
区間スケジューリングみたいな。とりあえずLでソートしてみると、（Lが等しいときはRの逆順にして）Rを逆から見たLISになる。またchokudai speedrunでググった。今回は広義単調増加でいいので、書き換える必要があった。lower_boundをupper_boundにする。
M - 木と区間 / Tree and Intervals
辺番号がバラバラで解けるわけないので逆に思いつきやすかったかも（頂点数を数えるのではなく、頂点から見て何個の区間からカウントされるかを数える）。頂点1からDFS。頂点1のカウントは手動でやるとする。そこへ行くまでに使った辺番号を含む最小の区間を管理する。この区間を含む区間を数える。左右それぞれ伸ばし方が何通りあるか調べて掛け合わせる。辺の個数は（Nではなく）N-1なのでやや怖い。
N - 数列と関数/Sequence and Function
実行時間制限と制約がだいぶやってる。クエリが多いので愚直は間に合わないだろう。まあNが小さいのでmultisetでMoやっても間に合うだろう。更新が重めのMoやるの初めて。伸ばすのと縮めるのが似た処理になるのも実装して気づいた。デバッグで苦戦した。先頭かどうかの判定はst.begin()でできるが末尾はst.end()から1個戻す必要があって面倒だなあとか思いながら実装を考えていたのに、実は最初にしれっとst.end()を使った判定（間違い）を書いていて、それにずーっと気づかなかった。
O - シフトとシフト/Shift and Shift
結局、ACするまでに100分以上を要した。時間がたくさん残っていて助かった。
平方分割できそう。計算量も、10進法の10が定数倍で付くけど、10^5だし行けるやろ（結果、実行時間制限の半分近くかかってしまった）。長さ9のarrayを持ち、全ての回転パターンを保持する。平方分割は、総xorを9通り保持する。数列の回転はまあやればできるというところ。ずれて境界をまたいだら2回やる。整数の回転が厄介。書き上がったと思ったらサンプルが合わず、そういえば親を回転させたら次に子をいじるとき全部の子を回転させて合わせる必要があるのだった。どんどんコードの定数倍が重くなっていく。最後、さすがにサンプルも通らないのはおかしいというところまで行って、めちゃくちゃ悩んだ。子を回転させる処理をなんかD回やっていて、結果無回転になっていた。
（解説を見て）遅延セグ木に乗らないと思ってしまったけど乗るんか（考えてない）。
（追記）考えてみたら普通に遅延セグ木でできた。こんなに簡単だったのか。
