2ペナ全完。こういうABCがいいよなって思う、好きなセットだった。
A - ツバメ/swallow
4以上9以下。
B - スロット/Slot
ソートして最初と最後を比較というのをまず思いついたが、比較を2回書けばいいだけだと気づいてそちらへ。
C - コンテスト/Programming Contest
カウントして最小値。
D - 相対評価のスコア/Relative Score
整数演算だけで四捨五入する方法がパッとはわからなくて時間を使った。解説の式には辿り着いたが、四捨五入に切り捨てのイメージがなくて（だって、どっちでもいいときに切り上げを選ぶんだよ）、なかなか感覚的に正しいと思えなかった。まあ切り捨ても、3を2.9999だと思って2にしてもいい（？）わけだしな。
E - 10 の n 乗/<=10^n
桁数でわかりそうだが、等号が付いているのでちょうど10冪のときは1小さくなる。
F - 式の評価/Evaluate Formula
実装してみると思ったより素直。'*'または終端が来たら現在の数を掛けてまた0から。
G - N個の三角形/ N triangles
12の階乗は間に合わない。3個ずつN色に塗り分けてnext_permutationで回せばいいんだ。問題の意味をよくわかってなかったけど、棒全部を使い切ってそれが何通りあるかだから、さっきの方法だと配色でNの階乗倍にカウントされてしまうので割り算する。
サンプル2に最大ケースがあるが、15400回で済む方法はあったのかな。普通にDFSか？DFSでできた。N個のグループを用意し、DFSで1個ずつどれかを選んでいく。ただし、空のグループに入るときは最も左のグループに入る。これで、問題文の分け方に対し色の塗り方が一意に定まる。
H - 休暇/Vacation
この辺りから難しくなってくる。DPだ。これまでに宿題をした日数と昨日宿題をしたかを状態に持ち、現在（今日どうするかはこれから決める）の楽しさの最大値を値とする。宿題をM日より多くやるメリットはないので、ちょうどM日やったときの最大値を求める。楽しさを得るのは遊ぶほうなのに連続してできない制限がかかってるのは宿題なのでちょっと混乱した。DPはin-placeでもできた。
I - アメ/Candies
嫌だなあ（きっちり考えるのつらそうだなあ）と思ったけど、二分探索が使えた。個数T未満のこどもがいる間配り続けるとして、操作回数がM回を超えない最大のTを二分探索で求める。二分探索の範囲が非常に難しく、K*M+2*10^12とすることで、確実にM回の操作が必要なところまで行けてかつ操作回数がオーバーフローしない。そしたら実際に配って、M回まで残りはN回以下（1人1回ずつ配ればM回を超えるようなTだから）なので愚直にやる（愚直というかMが小さい場合の解法でpairをソートしてとかする）。二分探索に気づけば難しくはないが、2問分のコードを書く感じになりけっこう大変。
J - 除夜の鐘/Joya no Kane
一瞬なにこれってなるけど、最大公約数だ。階差はGCD(A_i - A_1)の約数である必要がある。約数を列挙して、ソートして、小さすぎると端から端まで届かないのでそういうのは削除する。
K - マス目/Grid
TLが8秒だし、BFSがN-1回も必要そうだし、やばそうな問題。しかし、kが大きいときのBFSは高速に行えるので、ちゃんとO((N/k)^2)で初期化とかできればいけそうだ。計算すると300万とかなので間に合う（あとから気づいたけど、全部やっても定数倍にしかならんやつだ）。ちゃんとmod kが同じマスだけ初期化してBFS。queueを毎回初期化する必要があるのにループ外に置いたままで、はまった。移動途中の穴も検出する必要があることにあとから気づいたが、面倒だけど2次元累積和で対応できる。
L - 平均クエリ/Average queries
ラスト3問のお楽しみに速く到達したいが、最強の中ボスが待っていた（解けるけど大変ってやつ）。分数の大小を比較するには10^19程度までの整数を扱う必要があり、符号付き64bitでは足りないが符号無し64bitなら足りる。よく考えると、f(l, r)の最大値は極小な区間だけ考えればいい（混ぜて大きくなることはないので）。区間はsetで管理する。追加削除したところだけ変更すればいい（かなり面倒だが）。最大値は、全部の区間の平均値を分数でmultisetに入れておくことで得られる。約分は最後にやった。
M - 線分の交差判定/Intersection of Line Segments
シンプルでいいね。ライブラリ持ってた気がしたけどdoubleでやるやつだったので参考にして整数で書き直す。2つの線分それぞれについて、端点から端点へのベクトルおよびそれを90度どっちでもいいから回転したものを求めておく。2つの線分が平行なときは、軸が合ってれば（これを忘れて1WA）区間が共通部分を持つかみたいな話になる。端点4つについて、線分の向きのベクトルとの内積をとって、あとは普通に区間の共通部分の長さ問題。ここでは長さが0でも接していれば交点がある扱い。平行でないとき、直線とすれば必ず交わる。あとはその位置。90度回転させたやつと内積とって、相手の直線と交わる位置が相手の2端点の間にあるか内積の値で判定。それを両側やる。
N - ソートと関数 / Sorting and Function
難しそうだけど、ちょっと考えると遅延セグ木でできる。mapを使うか迷ったけど、座標圧縮で。それぞれの値が最高で同時に何個Tに入っているか（実装は手抜きしてクエリでの'-'も含めた登場回数とした）を求めて、累積和にして遅延セグ木上での位置を予約する。遅延セグ木を複雑にしたくなかったので個数はfenwick_treeで管理した。追加するときは自分より右にKを掛ける。削除するときはKで割る（この問題の設定だと割れる）（実装上はK^-1を前計算しておいて掛ける）。自分を追加するときに、自分より左の個数を使う。
解説見たら、ただのセグ木でできるらしいうそだろ。書いてみると確かにできる。こんなことが実現できるのか。多項式みたいな感じかな。面白れー。
O - 数列の足し算 / Add Sequences
ここまで順番に解いてきて100分以上残ってる。しかしこれはボス問だ。少し考えると解けそうな気分にはなる。そしてめちゃくちゃ難しい。理想的な展開ではある。漸化式の部分をまとめて扱うというのが基本的なアイデア。途中から始まって途中で終わるというのが難しさ。まず区間を開始地点と終了地点に割り振る。長さK以下の区間はここで処理してしまい追加しない。他の区間も、最初のK個は処理してしまう（Kだけ短い区間となる）。区間が始まる処理はまだ簡単で、漸化式に使う列に対応するBを足す（現在の位置を含まず直前のK個に足す）。区間を終わらせるには、その段階での対応するBが直前でどうなっているか求めて引く必要がある。行列累乗で10^4より多いかなくらい、これを2*10^5回やるのはさすがにTLEしそう。しかし、理解を進めるために書く。（高速化するアルゴリズムがないか調べたりして）かなり時間をかけて進行し、サンプルが通ったのでとりあえず提出してTLE。もう思考力がなくなってきたので提出したが、そういえば行列部分の高速化ができないか考えてなかった。できるじゃん。累乗してた行列はPにしか依存しないので常に同じ、何乗するかは毎回違うかもしれないが、そもそも最大でN乗くらいしか必要ないので全部前計算できる。これで行列累乗のlogが外れたので通りそう。526msでAC。
解説、言われてみればそうだ。なんかすごいアルゴリズムを使わなくてもそうだったね。これ行列累乗より速くなるんだなあ。感覚がない。自分のやり方と比べるとKが落ちている。
