ABC183 感想
ABC183 で成功したのでイキります
54分で全完 230th/7199
体感難易度は A < F < C = D < E <= B
正直このセットならパフォ2200以上を出せないとな〜って感じ
Eでバグらせなければ30分台で全完できるはずなんだよな
A.ReLu
cout << max(0, x) << endl;
B.Billiards
いやむずすぎる x座標について二分探索して入射角<=反射角になる最も左の位置を見つけます
考察時間はBが一番長かったと思う
C.Travel
制約に答えが書いてあって、O(N!)が通る 訪問順全探索でOK
始点が1固定なの見落としててサンプル合わなかったのにびっくりした
D.Water Heater
どの時刻に対してもどれだけ湯量が必要かわかれば良い 区間可算ができればおわりです
今回は更新が無いのでimosでOK
E.Queen on Grid
5分くらい考えてわからなかったのでF行った 戻ってきたらすぐにわかりました
DPの遷移を考える -> 縦、横、斜めに対して壁に当たるまでの和が欲しい -> dp[i][j]を計算する時点でこれらの和は1つ手前まで求まっている
縦横斜めの和を1で初期化しておくのを忘れてるのに気付かなくてデバッグで時間だいぶ食っちゃった
F.Confluence
クエリ1を見て UnionFind ですねってなる
クエリ2を見てマージをうまくやりたいよねってなる
区間可算になる? -> 可算する値が一様だったり一次関数で表せたりする？
みたいにして自分の知識に対してアキネイターするとデータ構造をマージする一般的なテクが出て、解ける