Skip to content

THIRDプログラミングコンテスト2025夏(AHC051)

問題概要

  • N(=5〜20)種類のゴミを分類して処理するゴミ処理場を建設する
    • ゴミ処理場全体は、2次元平面上の正方形で表される
  • ゴミ処理場の搬入口(図の左真ん中の赤点)からゴミが運び込まれる
  • ある1種類のゴミを処理する「処理装置」と、ゴミを確率的に分類する「分類器」を設置して、ゴミをできるだけ処理したい
    • 処理装置の候補地点は、N箇所あり、各ゴミの種類ごとに処理装置を1台設置する
    • 分類器の候補地点は、M(=10N〜50N)箇所あり、K種類(=N〜4N)の分類器のどれかを設置できる
    • 分類器は、分類器の出口が2つあり、他の分類器か処理装置にベルトコンベアで繋げる必要があり、このとき、他のベルトコンベアと重なってはいけない
      • 出口が同じ場合は、分類はされず、単にその先にゴミを運ぶような使い方ができる
  • できるだけ搬入口から入ってくるゴミが対応する処理装置に送られるような配置を求めよ

時間

  • 240 時間

個人的メモ

分類器の種類数

  • 分類器は、出口を入れ替えると、確率を逆にしたもの(1-pにしたもの)として考えられるので、実際は2*K種類あると考えられる

分類器の組み合わせ

  • 各処理装置ではどれか1種類しか処理できないので、どれか1種類だけ確率が高くなるように分類器を組み合わせる必要がある
  • 一旦、設置地点のことは忘れて、「分類器の組み合わせ」でどの程度分類できるのかを、小さいケースなどから考えるのがよい

直列つなぎ

  • 単純そうなのは、いくつかの分類器を直列につなぐ場合で、分類器の種類をうまく選ぶと、1種類だけ確率があってそれ以外がほとんど0に近いようなものが作れる
  • アプローチの方向性として、これを各処理装置にうまく複数繋げられるとよさそう、と考えられる
  • 分類器の種類は、全探索や局所探索などでもよさそうなものが見つけられる
  • また、これに頂点を追加してみてみると、より改善する場合もあることがわかる
分類器を3つつなげた場合

 ● --exit1--> ● --exit1--> ● --exit1--> X
 |            |            |
exit2       exit2         exit2
 |            |            |
 |            v            |
 -----------> ● <-----------
              |
              v
              Y

同じ分類器をメッシュ状・グリッド状・網目状につなぐ

二分木、DAGを探索

  • 単純に、入口から各処理装置までを二分木にすることを目標に、頂点の追加や辺の追加や張替えなどして木を作り、各頂点の分類器の割当を探索することも考えられる
    • 解説放送だと、サンプルの次の1手として想定されていたよう
    • これだけでは1つあたりの分類能力はそこまで高くないのでそこまでスコアはでない
  • きれいな二分木だけでなく、辺の途中に頂点を追加して別の頂点に繋いだりなどをしてより複雑なDAGにしていくと、よりスコアが改善する可能性がある
    • 焼きなましやビームサーチなどで大きなものも探索できる

辺の交差判定

  • 問題文の「ヒント」にある交差判定のコードは、問題文のベルトコンベアの条件とは異なっている
    • 線分の両端が同じ場合の処理の追加が必要
  • 基本は、現在使われている辺すべてとの交差判定が必要になるため、結構計算が重い

使う辺を制限する

  • 三角形分割(ドロネー三角形分割など)して、その辺のみを使うと、交差チェックを省略できる
    • ただ、使える辺をかなり制限してしまうため、微妙な可能性はある
    • 今回はドロネー三角形分割している人が多かったようで、それでも十分スコアは取れていた模様

辺の交差を高速に判定する

  • データ構造などを使う
    • 線分集合が動的に変化するので、それにも対応できる必要はある
  • (解説放送) 各辺について、交差する辺集合を事前計算しておき、各辺の交差数をカウントして判定
    • 辺が多い場合は適当に間引く、など
  • 幾何的に判定
    • 偏角ソート順に、交差辺情報を活用しながら判定する
    • 無向グラフとして見て、同じ面の辺とだけ交差判定をする

サイクル検出

  • 単純には、DFSなどで求められる
    • 辺の構造が変化した場合のみ判定すれば良いので、スコアが悪化する場合や分類器の種類を変化させるだけの場合、頂点追加の場合などでは不要
  • 頂点のトポロジカルソートを求めておく
    • あらかじめトポロジカルソート順が決まっていると、自分より後ろの頂点にしか繋がなければサイクルはできない
    • 現状のトポロジカルソート順は、辺の方向を変えなければ別のトポロジカルソートに変更できるので、あとからDFSなどで作り変えができる

スコア計算の高速化

  • テスターなどでは、トポロジカルソートしてからその順番で確率を求めていく感じでスコア計算を行っているが、そこそこ計算は重い

差分DP

  • DAGの場合、過去でも出てきている「前向き・後ろ向きで計算しておいて中間地点を差分計算するテク(差分DP)」が適用でき、ある頂点の分類器の種類を変えたり、辺を変えたりした場合のスコアの差分計算を高速に求めることができる
  • 入口側から「その頂点xまで種類iがたどり着く確率(前向き)」と、処理装置側から「その頂点xから対応する処理装置までたどり着く確率(後ろ向き)」を求めておく
  • すると、ある頂点や辺について、その前後での値から変更後の値を高速に求めることができる
  • 値を更新した場合は、その変更地点以降の値が変化しているので、更新しなおす必要はある
    • ただ、ここも、更新順を工夫すると、片方の更新し直しを省略できる(解説放送)

SIMD

  • AVX2/FMAを使って、float8要素をまとめて計算などで、配列の要素を並列計算できる

アプローチ

  • 上位はおおよそ「埋め込み解」か「局所探索解」が多かった模様

二分木を探索

  • あまり強いアプローチではないが、サンプルよりも強くなる解として、入口から各処理装置につなぐように二分木を作るアプローチが考えられる
    • 分類器を1つずつ増やしていく感じで作る
    • 分類器の種類は、一番良くなるものを選んだり、一緒に探索したり、など
    • 全部の処理装置につながる必要はないので、辺が交差せずにできるだけつながるものを探す
    • 結構これをやるだけでもいろいろ必要なので大変だったかも
  • 「二分木」で終わらず、これを初期解として、さらに頂点や辺を増やして複雑なDAGにすることができるので、結構重要な解法だった

組み合わせ分類器を埋め込み

  • 「分類器の組み合わせ」にあるように、分類器を組み合わせると、特定の種類を取り出せる分類器が作れるので、それを埋め込む
    • ただ、これがあまり単純ではなく、処理装置の位置もランダムで変な位置や他の処理装置と近かったりするとうまくいかない可能性がある
  • 上位だと、凸包や扇形の領域を用意して、その中の頂点で分類器の組み合わせを作り、それら同士をつなぐ、など
  • また、1種類ずつ分類してパスにする以外も、最上位は部分集合で考えていい感じのものを探索して木で分類していく、などもしてた模様

全体を局所探索

  • 素直にグラフの構造や分類器の種類の割当など全部を局所探索する
  • 単純にやろうとすると、変更した場合に「サイクル検出」「交差判定」「スコア計算」など遅い処理が多いため、高速化や近似計算を考える必要がある
  • 今回、TIME LIMITを100倍とかに伸ばして実行してみると、高速化によってどの程度改善しそうか？がわかるため、これを確認してから高速化を頑張る方針があり得た
  • 初期解の工夫や近傍設計、高速化などで取れるスコアの幅が大きいようだけど、かなり上位まで目指せた
初期解
  • 何もつながっていない状態からだと、他の辺が邪魔になって全部の処理装置に繋げられないなどあり得るので、処理装置につながる分類器を用意しておくとか(解説放送)、全部につながる二分木から始めるとかするとよかった模様
近傍
  • 頂点の追加
  • 出口の変更
  • 分類器の種類の変更
    • 同じ種類のものを組み合わせると良い傾向があるため、周りの種類に揃える近傍も有効
  • 部分破壊再構築
  • など

その他

ぐるぐるパス

AI

解説

(50位まで&発言を見つけられた方のみ)