この記事は？
2025年4月19日に行われた「第二回マスターズ選手権 -決勝-」のupsolve記事です。
私のチームは決勝30位でしたが、本記事では決勝10位相当まで解説します。
概要
以下、問題を読み込んで、実際に数時間掛けて解いた読み手を想定しています。
A問題
両手でTSP（680-700M 本番45位）
まず初投の方針として「右手と左手を同時に動かして、巡回セールスマン問題（TSP）とみなして解く」を書いた人が多かったです。
両手を広げないので、資源ごみを巻き込まないvalidな解が得られます。
厳密には、燃えるごみを結ぶ経路上に資源ごみがあると誤って回収してしまうのですが、頂点数に対して二次元平面が十分に広く、経路上の整数座標の期待個数も十分少ないので、気にしなくてよいです。
最近傍法のみだと680Mくらいで、2-optの焼きなましをすると700M近くまで伸びますが、これは本番45位くらいです。
右手の移動距離を減らす（771M 本番17位）
「両手でTSP」で得た解を初期解として、
- 左手は、常に初期解通りに動かす
- 右手は、必要な場合だけ左手の位置まで動かす
をすると、割と簡単に右手の移動距離が節約できます。これで一気に本番17位相当です。
「必要な場合」というのは「右手を動かさなければ次の左手の移動で資源ごみを回収してしまう場合」です。
例えば上図において、「左手が4、右手が1」の状態から「左手を5に動かすと資源ごみを回収してしまう」ので、「右手を4に動かしてから、左手を5に動かす」とします。
三角形と頂点の内外は外積を使って判定でき、問題文中のヒントをそのまま使えばよいです。
参考：三角形と外積
さらにTSPベースを改良（800.2M 本番11位）
- 凸包を求める要領で、左手の移動回数を最低限にする（下図参照）
- 1つ解を求めた後は、生のスコアでTSP経路の改善をする
までやると、800Mに乗って本番11位相当になりました。
まだまだ
- 右手を左手まで重ねずに、資源ごみを避けられる最小限だけ動かすようにする
- 常に左手を動かさずに、右手を動かして回収を進めることも考える
- 焼きなましの差分計算や近傍の改良
など改善の余地はありそうです。
TSPベースを極めたものがwriter解で、860.2Mです。
上手い貪欲
TSPから発展させる方針以外に、強くてキレイなルールベースも複数あり、上位方針は様々でした。
本番1位解法（853.2M）
固定する方の頂点は乱択して、偏角ソートをして資源ごみをギリギリ避けつつ燃えるごみの凸包を辿っている感じでしょうか。
本番2位解法（849.9M）
B問題のスキャン解法の応用風ですが、実際のところ先にA問題の考察中にこの方針が思いついたそうです（ありえない話し‼️）
B問題
2人同時にTSP（700M程度。本番22-48位）
A問題からの自然な発展ですが、この方針は以下の単純なルールに300Mほど劣ります。
単純スキャン（933M 本番21位）
B問題には実は極めて強いシンプルな解法があります。方法はアニメーションを見れば一目瞭然で、これだけで本番22位以降に大差を付けることができます。
頂点数に対して座標空間が十分広いので、この方針で燃えるごみと燃えないごみを同時に回収してしまう確率は十分低いです（正確には横方向のスキャンのみだと数ケース発生しますが、横方向のスキャンと上方向のスキャンを両方試せば、本番の150テストケースでは上手くいきます）
改良版（1.069G 本番10位）
単純スキャンでは別々に移動させていましたが、できるだけ同時に同程度働くようにし、所要時間を縮めています。
また、左からのスキャンと下からのスキャンのうち、スコアが良い方を採用しています。
これで1Gに乗り、本番10位相当です。
本番1位解法
斜め！？
本番2位解法
両手を動かすより、片手で弧を描くように掃く方が動かす距離は少ないというのは言われてみれば納得ですね。
この方針を決勝本番でどう思いつくか？
コンテスト中、開始1時間で1.02Gが突如として順位表に現れ、開始3時間で10チーム程度が1G超を出していました。その下は700Mで巨大な崖ができていて、何か根本的にTSPベースとは発想が異なる上手い貪欲があるということが明らかになりました。
ここから再現性の高い閃き方はあるでしょうか？（最初に思いつくのは天才なので無視します）
思いついた方々と懇親会で話したところ、そんなものは無さそうなのですが（絶望）、semiexpさんの以下のポストモーテムが論理的でした。
順位表の1位の得点から見積るというのは定石ですが、今回のスコア計算の場合は単に合計得点をスコアケースで割っても平均所要時間になりません。
それでも分かることがあります。仮に全ケースで2人が左端から右端まで両手を移動した場合、所要時間は2e6で、スコアは997Mになります。したがって崖上の貪欲は「単に2人が左端から右端に両手を移動する」レベルの貪欲ということになりそれよりも悪い貪欲は検討から除外することができたはずということでした。
C問題
ランダムケースに対しては、とりあえず2人同時にTSPをすると安定してvalidな解は出ます。
動く距離を合わせるように途中の頂点で指示を区切るなどするとスコアが上がります。A問題と同様の改良やルールベースも有効だと思います。
こういう、ごみごとにクラスタが分かれていて2手で全回収できるテストケースは専用のソルバーを作るとハックできます。
こういう殺意の高いテストケースは、単にTSPをすると直線上の不要なごみを回収してしまいます。
今回はゴミ同士はユークリッド距離が1000以上離れているという制約があるため、「目的地の直線上に集めたくないゴミがある場合は、目的地から1だけずれた位置を経由する」と回避できます。
本番提出コードは638Mでした（本番15位）
D問題
自分は2手で回収できる（愚直なTSPに対して差を付けられる）テストケースを作ったのですが、結局どういうのが上手かったのか微妙です。
直線上の資源ごみ問題は回避できてしまうので、ライバルチームをinvalidな解にさせるのは難しいかなと思いました。
TERRYさんの発展で、「ルートを知っていれば上手くスキャンできるが、他チームがそれを見つけるのは大変」とかが強い気がしますが、それをするにはまず開始3時間でB問題のスキャン解法に気づく必要があり……。
自チームのテストケースはC問題の2%かつ、TSPでスキャン解の70%くらいは出るので、成功しても累計スコアの影響は0.2%程度で、まぁなんでもいいのかもしれません。
？？？？？？？？
