脳log[20220926]

2022年09月26日 (月) [AtCoder] 精進。第11回 PAST 過去問-O「面積クエリ」。最近 20220910 と 20220518 で書いたように外積や複素数が関係する問題 ABC268-F「Best Concatenation」と ABC266-C「Convex Quadrilateral」と ABC251-G「Intersection of Polygons」が続いていたので、することはまあまあわかる。求める面積は外積だし、外積の式を見れば X と Y の２つの累積和があれば点を足し引きすることで増減する面積をまとめて計算できることがわかる。■提出 #35186967 (AC / 933 Byte / 3695 ms)。だからってするすると書けるわけではないけど。点を一列に並べて計算した累積和を点と原点が成す直線のあちら側とこちら側で分けるために(あちらとこちらでは面積の符号が異なるので)、点と点の原点対称の点を使って３つの部分に分けた。■この回の PAST は HIKLMN がまだ解けていなくて受検していたらたぶん初級だった。これまではだいたい中の上にいて上級をうかがっていたつもりなんだけど……。■■■精進。「偏角ソート」で検索して見つけた問題。ABC139-F「Engines」(ぎりぎり黄 diff)。ソートして尺取りか累積和で半円分のベクトルを合成していくのだろうとはすぐわかったんだけど、ときどき微妙に答えが合わなかった。なぜか。半円の角度を入力されたエンジンの１つによって決めてはいけなかったのだと思う。つまり、あるエンジンを１つ選び、それの左右 90 度(あるいは左右どちらかに 180 度でも)に含まれる他のエンジンを合成するという方法では最適解を取りこぼす。合成した結果が右に傾いてるなら左にぎりぎりいっぱいのベクトルを足すのは損になり得る。ってことは半円じゃないのか。■提出 #35208506 (AC / 387 Byte / 61 ms)。N<=100 なので累積和で効率化とか考える必要がなかった。愚直に長さが長くなる限り合成し続けるので十分だった。