ABC183

ノンペナ全完。いい感じに解けていたが結果はそれなり。自分にとって解ける問題ばかりだったが、たしかに瞬殺できないところは多くそこで力の差が出た。

A - ReLU

問題名からほんとに整数かと身構える。内容自体はとても簡単で31秒だった。

B - Billiards

x軸を鏡としてGをx軸に関して対称な位置に移動させSとGを直線で結びそれとx軸の交点のx座標を求めればよい。と思ったけどS_y:G_yに内分する方法が先に見えたのでそっち。交点の求め方とか内分点の求め方とか散々やったから簡単なのは知ってるけどパッと出てこないんだよね。特に数分で解く必要があるB問題だとそれが響く。結局6分かかった。実装内容はともかく反射はB問題にしてはかなり高度だ。

C - Travel

うってかわって安心の全探索。next_permutationさえ知っていればやるだけ。数えさせるというのが気持ちいい実装で好き。

D - Water Heater

びっくりのいもすやるだけ。しかし苦戦した。入力もわりと自然なのだが、いもす法を書くのはそこまで頻度高くないしT_iの上限が入力で与えられないこともあり境界を考えて頭がオーバーヒートになった。簡単だとわかっていることを短時間で確実に仕上げるのは難しい（簡単なことも定着してないのが悪いというのはそうだけどなかなか厳しい）。

E - Queen on Grid

1マスしか動けないいつものDPと何が違うか、実際にDPを頭の中でやって調べてみると、隣のマスだけでなく直線上にある全部の合計を得る必要があるのだった。これはDPで持つものを累積和にすればいいだろう（普通にfor文回せば自分の左や上は全部終わってる）。端っこをどう計算するかいつも迷うがとりあえず書いてみる。書き上がるあたりで、累積和は3方向ぶん3種類持つ必要があると気づく。実装が煩雑になりそうなので、端っこを考えなくて済むよう左と上に1列入れる。DPのタネをどうするか悩んだが、ループ内でスタート地点だけ分岐して3方向を1にした。通常のマスでは、まず累積和を使ってそのマスへ移動する方法が何通りあるか求め、次に隣の累積和を足してこのマスの累積和を求めるのを3方向ぶんやる。壁のマスはスキップするだけでよさそう（DPテーブルは0で初期化されている）。出力は累積和ではないので保存しておく（最後に計算するマスのを出力すればいいので楽？）。

F - Confluence

すっきりした問題なのでいい意味で典型っぽさを感じて解きたくなる。しかしとっかかりがない。UnionFindは使うとして、集団毎に各クラス何人いるか持つためにクラス数は人数以下だしmapとかで行けるのでは。と思ったけどマージの計算量がわからない。PAST4Mでどうも無理っぽいのでやめた方針と似ているということで捨てた。ここまで考えて来て平方分割は思いついていて、簡単な方法がないか少し考えて平方分割に行った。sqrt(20万)は447くらいなので1000にした（この問題の場合512などキリのいい数にする意味はなさそう）（人数を持つほうがメモリ食うのでそれを減らすほうへ少し寄せた（どうだろうなあ999人のクラスを延々数えさせられたら遅そう））。

さて、実装がかなり重い。平方分割自体はそれほどでもない（1000とかに固定するのを覚えたので）。1000人未満の小さなクラスについては、クラス名簿を作っておいてクエリが来たらクラスyを全員調べて生徒xと同じ集団か調べる。1000人以上のクラスは高々200個しかないので各集団に何人ずついるかの配列を持つことができる（深く考えてなかったけどけっこうメモリ食うな）。200に圧縮するためクラス番号を変換するためのテーブルを用意する。人数の配列も用意して大きいクラスに属している人は自分のクラスに1をセットする。一つ一つは簡単だけど、この量は相当きつい。クラス番号を変換せず人数にアクセスしてたりクエリ1でroot取り忘れて落ちたりしてた。