penguin46 https://blog.hatena.ne.jp/penguin46/ penguin46の精進記録 https://penguin46.hatenablog.com/ 日記はこちらです↓ penguin46.hatenablog.com 結果 pretest 、システムテストともに9位 問題概要 atcoder.jp格子点上に頂点を1つ追加して軸に平行or45度傾いた長方形を作ることを沢山繰り返してください。既存の頂点を通ったり、辺を共有するような長方形は追加できません。 seed1, 1.48M点 解法 一部の長方形を削除して貪欲で再構築する焼きなましをしました。長方形を削除すると宙ぶらりんになる長方形が生まれるので、それらも削除します。*1 長方形の全列挙 各頂点から8方向に線形探索し、直角な2方向で別の頂点に到達したら、その3点を使う長方形が作成可能か… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpenguin46.hatenablog.com%2Fentry%2F2022%2F10%2F01%2F191428" title="AtCoder Heauristic Cotest 014 解説(9位) - penguin46の精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/p/penguin46/20220928/20220928051849.png Hatena Blog https://hatena.blog 2022-10-01 19:14:28 rich https://penguin46.hatenablog.com/entry/2022/10/01/191428 1.0 100%