- 0.はじめに
- 1.問題文の概要
- 2.最初の提出
- 3.2回目の提出
- 4.長方形を乱択山登りする
- 5.長方形から長方形を引いてコの字の多角形にする
- 6.長方形からたくさん長方形を引いた多角形にする
- 7.長方形の角をけずる
- 8.WAが続く
- 9.最後の提出
- 10.最終結果
- 11.終わりに
- 12.おまけ（WAの原因）
0.はじめに
はじめまして、もしくはお久しぶりです。競プロ歴4年11か月のかえでです。
今回は、 THIRD プログラミングコンテスト2024（AtCoder Heuristic Contest 039）に参加しました。開催期間は2024年11月11日(日)15:00から19:00までの4時間の短期コンテストでした。
この参加記はコンテスト後に書いています。今回は、4時間集中が切れることなく、参加記を書く時間も惜しんで、最後まで取り組んでいました。
何もメモしていなかったので簡単なものになりますが、少しでも記録に残しておきたいと思いこれを書いています。これを読んだ方の参考になる点が少しでもあると良いのですが。そして、ヒューリスティック・コンテストに興味を持つ人がもっと増えることを願っています。
1.問題文の概要
二次元平面上にいるサバとイワシそれぞれ5000匹ずつ（計10,000匹）の座標が与えられるので、条件を満たす多角形を構築し、その多角形の内側に含まれるサバの数からイワシの数を引いた差を最大化します。
条件:
- 多角形の頂点数は4以上1000以下。
- 辺の総和の長さは400000以下。
- 各頂点の座標は整数で、0 ≤ x, y ≤ 100000を満たす。
- 辺はx軸またはy軸に平行。
- 多角形は自己交差しない。
出力形式:
- 最初に頂点数 m(4 ≤ m≤ 1000) を出力。
- 次に、各頂点の座標をm行で出力。
得点:
- 多角形の内側に含まれるサバの総数を a、イワシの総数を bとすると、得点は となる。
2.最初の提出
最初の提出は開始20分後、(0, 0), (0, 100000), (100000, 100000), (100000, 0)の4点をつなぐ多角形を書きました。スコアは150点になりました。
3.2回目の提出
四角形の大きさを四分の一にしました。(50000, 50000), (50000, 100000), (100000, 100000), (100000, 50000)の4点をつなぐ多角形を書きました。
提出をすると42763点になりました。
25分が経過していました。
4.長方形を乱択山登りする
対角線上の2点をランダムで選択すると長方形が決定します。長方形の長さが400000以下のときにスコアを計算して、山登りをします。提出すると282385点になりました。
30分が経過していました。
あまり良く覚えていないのですが、思った以上に順位がよかったです。
5.長方形から長方形を引いてコの字の多角形にする
長方形から長方形を削除します。方法としては、長方形の内部から辺に平行な2点を選び、辺に向かって垂線を引きます。
48分が経過していました。
提出をすると301169点になりました。順位が良くて、おおっと驚きました。一桁順位だったと思います。
6.長方形からたくさん長方形を引いた多角形にする
長方形を追加するコードも書きますが、うまくいきません。長方形を追加したり削除したりすることを思い描いていましたが、複数の長方形を削除する方向に絞ることにしました。
それでも、とにかくバグらせます。長方形にならない！
何とかデバッグを書き終えたときには2時間31分が経過していました。提出をすると319679点でした。がんばった割に点数が上がらず、残念に思います。
7.長方形の角をけずる
ここからどうしようと悩みます。一番大きな長方形の選択方法をスコアではなくサバの数で山登りしてみることにしました。しかし、あまり良くなりません。
その後、下図のような、角をけずるような方法を取り入れました。外周の長さが変わらないのが良い点です。
提出をすると395864点になりました。
上がったー！
しかし、すでに3時間12分が経過していました。残りは48分です。何とか40万点までがんばりたい。
8.WAが続く
しかし、なかなか改善できません。最初の長方形の選択時のスコアの計算方法を2乗の差にすることにします。100テストケースの結果、ついに40万を超えました。提出をします。
しかし、結果は1ケースでWAが出て0点でした。
100テストケースでは問題ないため、どうしてWAが出るのがわかりません。もう1度提出してみたらどうだろうか、とか、少し変えたりして提出してみますが、6連続WAが出ます。ついに残された時間は最後の提出を残すのみとなってしまいました。
9.最後の提出
最後の提出はこれまでACしていたもののパラメータを変えたものにしました。これが今日の最高得点となる396572が出たものの、40万には届きませんでした。
試行中でいちばんよかったseed84のビジュアライザではスコア4259が出ていました。
10.最終結果
そしてあっという間に4時間のコンテストが終了しました。結果は751人中81位。初の黄パフォ、2桁順位を達成しました。
もうちょっとがんばれなかっただろうかと思いはするものの、良い結果が出てうれしく思います。
ヒューリスティックのRatingは58上がり、1759になりました。
明後日2024年11月13日水曜日にはAHCラジオがあります。しっかり復習したいと思います。
11.終わりに
思っていた以上に良い結果が出て、長く続けているとこんな風にごほうびをもらえることもあるのだなあと思いました。今回は実装する際にChatGPTを使ったのも時間短縮に役立ったと思います。具体的な実装を日本語で指示してコードを書いてもらいました。
もっと上を目指したいという気持ちはまだまだ尽きることはありません。これからもがんばっていきたいと思います。
12.おまけ（WAの原因）
今朝起きて（コンテストの2日後）はっと気がつきました。頂点数mが1000以下という制約をつけていませんでした（そんなに頂点数が多くなるケースは無いと思っていました）。WAが出ていたソースコードに出力のmが1000以下という条件をつけて再提出します。
無事ACしました。しかし40万を超えていません。
あれ？
「これがACすれば40万を超えていたはず」という思いは崩れ去ったのでした。今思うと、もっと複数のテストケースを試すとか方法はいろいろとあったはずです。短期コンテストで残り時間が少なくなると、焦ってしまうのだなあと思いました。
