はじめに
はじめまして。一般通過競プロerのSaki1103です。$2025/8/1 \ 19:00$ ~ $2025/8/11 \ 19:00$の間に開催された「THIRD プログラミングコンテスト 2025 夏（AtCoder Heuristic Contest 051）」で$140$位（当社比でそこそこいい順位）を取ったので、記念に解法を記しておこうと思います。
なお、私はこのような記事を書くのが初めてなので拙い部分が多々あると思いますが、最後まで見てくれるとうれしいです。（深夜テンションで書いてるので、変なところがあったらごめんなさい ＞＜ ）
↑の顔文字、chokudaiさんが使ってるのを見かけてから結構お気に入りです。二文字で的確に感情を表現できるのがいいですよね（？）
問題概要
二次元平面上に$N$個のごみ処理装置と$M$個の分別器があるよ！
分別器は$K$種類あって、それぞれ、ごみをその種類ごとに一定の確率で分別するよ！
どの分別器をどの種類にするかは自由に決めていいよ！
今から$N$種類のごみが、搬入口から流れてくるから、分別器とごみ処理装置をベルトコンベアでいい感じに繋げて、きれいに分別できるようにしてね！
ちなみに、ベ ル ト コ ン ベ ア は 交 差 し た ら だ め だ よ ! !
問題概要はこんな感じです（かなりざっくりしてますが）。
やはり、ベルトコンベアを交差させてはならないところが一番の難題だったと思います（ここで詰まって、サンプルを投げるだけで終わってしまった人も少なくないのではないでしょうか）。
解法概要
私の解法は大きく、3つの段階に分けることができます。
第一段階
先ほども述べたように、やはり、ベルトコンベアを交差させないのがとても難しいため、ベルトコンベアの構築を乱択系のアルゴリズムに任せます。具体的には、山登り法を用いました。
初期解はかなり適当で、ごみの搬入口からできるだけ横に一直線となるように$N$個の分別器を選び、それぞれに適当にごみ処理装置を割り当てます。
近傍は
- 解に使われている、ある1つの分別器を選び、その近くの分別器に変更する
- 使うごみ処理装置の割り当てをswapする
以上の二つのみです。
評価関数は、交差している辺の組の数で、愚直にすべての辺の組に対して交差しているかどうかを判定しました。
これだけでほんとにうまく構築できるのかよって疑問に思うかもしれませんが、うまくいきます。うまくいってしまうのです。
ローカルで$5000$ケース回してみたところ、遅くても$150$ms程度あれば構築できました。
ちなみに、このような制約を満たすような解を、山登りでがんばって構築する、みたいな方法は、AHC043で見たような気がします。（気がするだけです。）
第二段階
第一段階の状態だと、1つのごみ処理装置につき、1個だけしか分別器が割り当てられておらず、うまく分別できているとは言えません。そこで、第二段階では、分別器を複数使えるように、分別器のグループをつくります。
具体的には、以下の図のように（以下の図の形でベルトコンベアをつなげても制約を満たすように）なるよう、山登り法をしました。
初期解は、第一段階で構築したものをそのまま使いました。
近傍は
- 解に使われていない分別器一つをどこかのグループに挿入
- 解に使われている分別器一つを削除
- 解に使われている分別器をswap
- 解に使われている、ある1つの分別器を選び、その近くの分別器に変更する
以上の4つのみです。
評価関数は、各処理装置について、「割り当てられている分別器の数と、理想の分別器の数との差」の総和としました。ここで、「理想の分別器の数」は１グループあたりの分別器の２倍としました。（色々試してみたのですが、これが、一番スコアがよかったです。まあ、色々っていっても１時間も試せてないんですけどね）
また、辺が交差してしまうような近傍は無効としました。（これも時間によって、ペナルティを変えながら～、とかやりたかったんですけれども、時間がありませんでした。terryさんの記事みたいな感じにできたらめっちゃかっこいいですよね（？））
ここで、少し実装の話をします。
実装上の問題 (時間がなかったんですよ...) で、各処理装置に割り当てる分別器の集まりを、解として持ちました。そして、ベルトコンベアが交差しているかどうか判定するときに、分別器を3 ~ 4つに分けて上図のように辺をはりました。ここで、上のような解の持ち方をしているため、上図のように「綺麗」にグループ分けされているかどうかは、各処理装置に割り当てられている分別器の数を見ればよいことがわかります。
また、たまにイジワルなケース（1000ケースに1個程度）があり、構築がうまくいかないことがありますが、この後の気合の実装によりなんとかなりました（？）
第三段階
最後に、分別器の種類を決めます。第二段階で構築した解の性質から、各ごみの種類について、3～４つの分別器を組み合させて、その種類のごみを集めたくなります。また、その種類以外のごみは、極力減らしたいです。そこで、よさげな分別器の種類の組み合わせを山登り法によって探索しました。
初期解は、単体で一番評価関数が高い種類の分別器を3~4つ使ったものにしました。
近傍は
- 一つだけ、分別器の種類を変更する
以上の一つだけです。 （お手軽ですね）
評価関数は、種類$t$のごみを集めたいときに、ある分別器の組み合わせによって、$i$種類目のごみを抽出する確率を$p_{i}$としたときの、以下の数式の値としました。
$$
\sum_{i = 0} ^ N
\begin{cases}
(1 - p_{i})^\frac{1}{2} & (i \neq t) \\
p_{i} & (i = t)
\end{cases}
$$
お気持ちとしては、他の種類をできるだけ削らないようにしたい！という感じです。
このようにすると、種類$t$を$40$~$60 \%$ほど、他の種類を$1 \%$~$10 \%$ほどにすることができました。
Kiri8128さんがX上でより具体的な議論をなさってました。
解法を振り返って
この解法で、プレテストが約$8.8G$で$137$位、システムテストが約$356G$で$140$位でした。（システムテストが想像以上に早く終わっていてびっくりです。）
パフォーマンスは$1916$で、瓦が一枚増えました。（やったね！）
以下がseed0とseed1のビジュアライザです。
seed = 0
score = 561891807
seed = 1
score = 361062754
X上で、自分と同じような解法をしている人が散見されました。
解法の筋自体は、そこまで悪くはなかったのだと思います。一方で、やはり、似たような解法でも、上位陣の人達と比べて全然煮詰まりきっておらず、スコアも大きく差が生まれています。
ビジュアライザを改めて見ていても、全体的に確率が高いとは言えない感じでした。自分の詰めの甘さを強く感じました。
しかし、とても難易度が高い平面グラフの構築でつっかからなかったのが、かなり命運を分けたっぽく、その部分をメタヒューリスティックに託したのは英断だったと思っています。
また、最上位勢の解法を見てみると、とにかく焼きなましをしている人が多いように思われました。
参加記...?
うろ覚えです。
- 8/1
問題文を読みました。ﾑｽﾞｶｼｲ
現実逃避のためにpahcerのバージョンアップをし、ついでにエイリアスを設定しておきました。結構たのしかったです。
（これで本当にいいのかどうかよくわかってないですが一応動きます）
pahcerを入れていない画面の前の君！今すぐ入れよう！
（めちゃめちゃ便利です。terryさんに感謝しながら入れましょう。）
-
8/2 全人類、積分サークルを見ましょう
-
8/3 全人類、積分サークルを見ましょう
ここら辺でドロネー三角形分割を思い出し、色々試してみるも、あんまりうまくいきませんでした。 -
8/4 全人類、積分サークルを見ましょう
-
8/5 全人類、積分サークルを見ましょう
-
8/6 全人類、積分サークルを見ましょう
-
8/7 全人類、積分サークルを見ましょう
-
8/8 全人類、積分サークルを見ましょう
-
8/9
第一段階の部分を実装しました。 -
8/10
がんばって実装を進めました。 -
8/11
超がんばって実装を進めました。
なんとかなって一安心。割といい順位が出たので、勢いで記事を書きます。← 今ココ
最後の3日間くらいでパフォーマンスを500くらい盛りました。
まじで実装が終わってよかったです( ；∀；)
最後に
元気だったのは最後の2~3日間くらいだけでしたが、とても楽しめました！
今回も面白く難しすぎる問題を、ありがとうございました！Writerのwataさん、THIRD株式会社の皆さん、並びに関係者の皆さんに心より感謝を申し上げます。本当にありがとうございました！
こんな記事を最後まで読んでくれてありがとね！(*‘∀‘)
現在時刻、2:48
おやすみなさい