脳log[20220518]

2022年05月18日 (水) [AtCoder] 精進。パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）-G「Intersection of Polygons」(ギリギリ橙 diff)。答えをね、見ました。「アライグマ「G問題は、多角形の内側が「辺のこっち側」の積集合になることを知ってれば解けるのだ！」 フェネック「逆に、このことだけに気を取られてると嘘解法に引っかかる問題もあるよ。考えてみてねー」 https://t.co/9AbUhEnUZq」。といってもツイートがストレートに答えというわけではない。「辺の～積集合」に注目してちょっとは考えた。最大 50 角形の凸多角形が最大 20 万個あるわけなので辺の数は最大 1000 万本。これを一本一本チェックしていては最大 20 万個のクエリには答えられない。最大 20 万本の平行な辺から代表を１本だけ選ぶことにすれば、各クエリに対して最大 50 本の辺をチェックするだけで済む。提出 #31786740 (AC / 557 Byte / 1727 ms)。■自分の提出が 1727 ms のところ Ruby で先に AC していた hmmnrst さんの提出 #31756127 が 1551 ms。この差は明らかにメインループの照合部分が (a-x)*dy<=(b-y)*dx (遅い) か dx * px + dy * py >= threshold (速い) かに由来している。演算子の数が違うからね。だけど３つのペクトルをどう組み合わせれば引き算部分を事前に済ませておけるのかわからない。もうひとつ 10 行目の offsets.max_by もわからなかったよね。自分は辺と点の関係をあっち側こっち側の２値でしか扱わなかったから、値の大小を比較する max_by が選択肢になかった。外積が平行四辺形の面積なら値の大小は高さの大小であり符号と絶対値は辺のどちら側にどれだけ離れているかを表している。こちら側に一番離れている点が選ぶべき代表点であり、それを max_by で選べると事前準備の M 回の繰り返しがすごくシンプルになる。自分の提出は少なくとも２つの点で遅れをとっていた。■というのを踏まえて整理しました。提出 #31797336 (AC / 333 Byte / 1575 ms)。短く速くなった。速さは同じくらいに追いついたけどメモリ使用量がほぼ例外なく 1.5 倍くらいあるのがよくわからない。とくに富豪的な無駄遣いはしてないはずだけど……(多重代入？)。事前計算については意味を考えず単純に展開してクエリと無関係な定数部分を括りだして覚えておいた。