A - Find Multiple
さすがに、A以上B以下の整数を全探索。解説の方法はなるほど明快だ。ループが必要ないのがAだと思っていたら、いつの間にかループなしで解く考察難度がかなり高くなっている。
B - Base K
K進法の文字列を普通の数に変換する関数を書く。上の桁からK倍して足してを繰り返すいつものやつ。
C - Long Sequence
元の数列のブロックを引けるだけ引いて（割り算）、残りを愚直にやる。超えるのがいつかという問題なので、それで都合よく求まる（2周したほうがいいかなとビクビクしていた）。
D - FG operation
何もわからなくてびっくりした。5分くらい考えてEへ。この時点で、トーナメントみたいに右へ追加するものと誤読していた。
足し算か掛け算か選ぶけど、演算に意味がある場合とない場合があって、最初前者で考えていたが、後者で考え直すと普通のDPが見えた。最初に3があるとき、3が1通りで他の9つの数が0通りという感じで持つ。あとは10^2通り全部やれば合成できる。それをN-1回やればいい。サンプルが合わず、左に挿入するから簡単だったことに気づく。実装は流用できそうなので、末尾ではなく先頭に追加するように1行直して提出。
E - Distance on Large Perfect Binary Tree
2^N-1というのは見えていたのだが、意図がわかっておらず、なぜか下が揃っていない二分木を想像してしまう。それはあまりに難しそうなので、5分くらい考えてFへ。
LCAを固定して考える。そこから左右へ合計Dだけ伸ばす。通り数は分岐の数だけ2倍になる。足してDで両方0以上N未満になるものを列挙し、LCAが根の場合はこれで求まる。そうでないときも、両方の長さのmaxによってそれができるLCAの個数が2冪-1でわかる（計算はややこしいがコードは短い）ので掛け算するだけでよい。
サンプルが合わず苦しんだ。サンプル1で7を出力していてこれは正しい答えのちょうど半分。しかし、サンプル2の正しい答えがmodを取って小さくなっていて2倍であることに気づかなかった。2倍してみることを試さなかったのよね。それ自体はいいけど、結果的に今回はそれで少し時間食った。各パスに対して頂点の組は2通りずつあるんだね。
F - Distance Sums 2
全方位木DPをやれば解ける。しかしそれは不要であると思い正面からコードを書いていく。結果的に全方位木DPみたいになった。解説みたいな考え方は思いつかなかったね。何しろ全方位木DPで最初から解けているので、思考がそっちにしか行かない。
根付き木として考えて、各頂点について部分木のサイズと距離の和を1回目のDFSで求める。2回目のDFSで逆方向の部分木の情報を親からもらい、その頂点の答えが求まり、子のぶんを引いて子に情報を渡す。辺を移動するとき、部分木のサイズだけ距離の和が変わる。
（9/27追記）昨夜、全方位木DPでやってみて、ライブラリは作ってあったからコードは数行書くだけだったが、サンプルが通らず悩んだまま寝た。布団の中で考えて見当は付いた。足すときに結合法則を満たしていなかった。距離の和にサイズを足すのは、部分木を足してそこに根を付けて新しい木ができるときだ。このライブラリの作りだと、親側に付いているものとそうでないものの非対称性があってはいけない。
G - Isosceles Trapezium
2乗が余裕を持って許されるけど、傾き毎に考えたら3乗とかになりそう。しばらく悩んでいたが、2点の中点を傾き付きで列挙して同値類に分けることを終了5分前くらいに思いついた。終了後これを実装。中点の座標を整数にするため入力は2倍する。2点の選び方全てについて中点とその線分の向きと重みの和を記録する。向きはGCDで割ってx方向が負にならないようにして正規化しておく（ここでx方向が0のときy方向の符号を揃えるのが抜けていてWA、ちょうどここ（ブログ）を書いていてWAの原因に気づいた）。適当な基準でソートして、向きが同じものをまとめて処理。その中で線分の向きとの内積でさらにソート。軸が合うものでまとめて処理。その中でさらに外積でソート（ここは単に中点の位置が一致するか見るだけでもよかった）。面積が正にならないものを除外。位置が同じものの中で重みの最大値を求めそれを代表値とし、その中から大きいものトップ2を求める。ちゃんと2つ正の重みがあればその和で最大値を更新。その最大値が答え。ソートしてfor文で境界を見つけ区間を処理というのが三重くらいになって地獄だった。サンプルが通るまでに、コピーして添え字を直してないみたいのが2箇所もあった。
