第16回PAST（バチャ）
https://scrapbox.io/files/656763cbd0ea7a00247ceb33.png
ネタバレあり感想です。
A：ツバメ
code:a.cpp
INT(M);
Yes(4 <= M && M <= 9);
tatyamさんのマクロを窃盗しているので2行です。
B：スロット
code:b.cpp
INT(A, B, C);
Yes(A == B && B == C);
同様に。
C：コンテスト
mapに入れて0で初期化せずに拡張for文でminを取ると、サンプル3でWAですね。
Cまでできるとエントリー認定。
D：相対評価のスコア
0.500000001を足して切り捨てるサボりをしました。
公式解説をやりましょう。
E：10 の n 乗
大きい数字を文字列で受け取って処理する典型 AND 例外を考慮する必要がある典型
F：式の評価
この問題文を渡してバグらせずにあっさり実装できるエンジニアがやってくれるチームは結構安心できる。
Fまでできると初級認定で、基本情報とかよりはかなり難しそう。
G：N個の三角形
再帰を実装できますか AND 重複を考慮できますか。
重複は最後に割ってもいいけど「新しい箱に入れる操作は1つの箱に対してしか許可しない」をすると入れるタイミングで重複除去できて速くなるという典型。
H：休暇
いわゆる耳DP。
I：アメ
優先度付きキューでシミュレーションするにはMが大きすぎるので工夫する。
最初にソートして、例えば「1人目に1回与えると2人目を超える」「2人目に2回与えると3人目を超える」「3人目に2回与えると4人目を超える」のであれば（9回以上与えられる場合）1人目に5回、2人目に2回、3人目に2回与えることになる。
このようにまとめて扱うことで解くことができるけど、9WA出した。
明らかに二分探索が楽。
J：除夜の鐘
直感的な気持ちを論理的に整理するやつ。
K：マス目
調和級数。
計算量間に合うはずなのになぜかTLEして解けないと思ったら、BFSがバグってました……。
移動可能は、「y列目の穴の位置をvectorで持ってx1, x2間に穴がないか二分探索で判定」よりも、「y列目のx1までの穴の累積個数とx2までの穴の累積個数が一致しなかったら間に穴がある判定」の方が、計算量もいいし実装も楽。
L：平均クエリ
最大値としてあり得る(l, r)を考察したあと、実装を頑張る。
Sはmultisetに入れて、あり得るf(l, r)をpriority_queueに入れる。ただし出力のために分子分母を持つ必要があるのと、priority_queueから取り出した時に既に無効な値の場合（Sからlかrが消えている場合）があるので、l, rも持つ必要があるので、4要素を持つデータ構造を作り比較関数を自前で実装する。
code:l.cpp
using P = pair<pair<ll, ll>, pair<int, int>>;
auto compare = [](P p1, P p2) { return p1.first.first * p2.first.second < p2.first.first * p1.first.second; };
M：線分の交差判定
灰コーダーの時に螺旋本を元に作った幾何ライブラリを貼ると誤差で落ちたので窃盗。
いい加減作り直しましょう、はい……。
N：ソートと関数
セグ木のお勉強枠。
追加削除をセグ木上の1要素更新で「起動・休眠」に対応させるテク、勉強になりました。
起動休眠は今回は単位元をセットすればよいし、ペアでフラグを持つ必要があることもありそう？
クエリ番号とセグ木上のindexは事前にクエリ先読みして対応付けておく。
O：数列の足し算
TODO