2024/11/10(日) は THIRD プログラミングコンテスト2024（AtCoder Heuristic Contest 039）が開催されていました。 そのコンテストに参加した様子をお届けします。*1
今回は大変な実装をクリアしたものの、一部制約を考えていなかった結果ほとんど価値を発揮できずに終わってしまいました。 悔しさを記事として昇華し、上位陣の実装から学ばせていただきたいところです。
どんな問題か？
上のような分布に対して「赤い点」をなるべく含み、「青い点」をなるべく含まないような1つの多角形領域を作りたい。
ただし、多角形の辺はタテヨコに真っ直ぐしか引けないし、頂点は 1,000 まで。また、多角形の外周長にも強めの制約があります。
考えたこと
やりたいことは実にシンプルに見えましたが、全体は 105 * 105 の正方形なのでめちゃくちゃ広いです。 1px単位でコントロールするのはまず無理なので、大きなブロックに分けて扱うのが楽そう。
大きなブロック単位で「赤点の数 - 青点の数」を数えて、これが大きいやつを繋げて多角形を作れば良い。ヨシ！
ブロックが離れてしまうことはあるので、じゃあそこは細いブリッジを作ってあげると良さそう・・ 実装はかなりダルそうだけどなんとかなるか？
多角形の辺をどうやっていい感じに出力するか、それが大変だ
「ブロック同士を繋げて多角形を作る」言葉にすると楽そうですが、これがかなり大変です。コンテスト中の3時間はここに費やされています。 最終的に出力するのは「多角形の辺のリスト」であり、一筆書きの要領で正しい順番で座標を出力しなければなりません。 頂点集合と、頂点同士のつながりをグラフ形式で出力・・ とかだったらだいぶ楽なんですが！！
考察の結果、「左上を起点として」「右に行って左に戻ってくる」「1ブロック下に移動する」「右に行って左に戻ってくる」... 「一番上まで戻る」という順番で DFS をやる形式とすれば自分の実力でも形にできそう。 2時間ちょっとのデバッグ地獄を終えてなんとかビジュアライザに描かれる出力ができました。
描かれたのですが、なんと多角形の外周がクソ長くなっていました。これを5%程度の長さにしないと valid な出力になりません。 長さの制約、目には入っていたと思うのですが完全に甘く見ていてスルーしていました・・・！
ちなみに左右が繋がっていない部分があるのは実装の都合です。多角形をマージする実装が無理すぎてこうなりました・・
無理やり提出まで持っていく
残りの時間で新たな実装をやるのも現実的ではなかったので、なんとかします。 ブロックを大きくしたり、最終的な長さが制約を超えないようにブロックの数を制限したりして一応提出できる状態になりました。
長さが無限の時に比べて全然サバを獲れておらず悲しみです。
参加した感想
なかなか大変な実装を完遂したので、満足度は高かったです・・！
日頃のギョームでも大事な前提や制約を見逃したり甘く見たりして痛い目を見ているので、そこは大いに学習すべき点だと思いました。 そんなにスコアが良くない提出だと思ったのですが、水色パフォーマンスは取れていて意外でした。
この問題は「多角形の辺を出力する」のが一番大変だと思っていますが、こういうのはライブラリとかで解決できたりしないのかな？というのも興味が湧きました。 図形描画ツールでは任意の図形をベクタ化できたりしますが、そういうアルゴリズムを知っておいたり道具として使える状態にしておくと楽しそうです。 年末に開催されている Xmas Contest では A 問題でお絵描きみたいな問題がよく出ており、結構参考になりそうな気がしました。
