AHC025: 統計的推測によらない4位解法の解説

AtCoder Heuristic Contest 025 に参加し、4位を取ることができたので、その解法について解説します。各アイテムの重さを推定しない解法なので、統計的推測に自信がない方でも理解しやすい解法になっていると思います。

基本方針: 袋の重さをソートした状態を保ちつつ、一番重い袋と一番軽い袋の差を小さくする操作を繰り返す（60位解法）

まずは $${i}$$ 番目のアイテムを $${i \% D}$$ 番目の袋に割り当てることで、各袋のアイテムの個数ができるだけ均等になるように割り当てます。そして、マージソートを行うことで、以下のように袋の重さがソートされた状態を作ります。マージソートに必要な比較の回数は$${N \lceil \log_2 N \rceil  - 2^{\lceil \log_2 N \rceil} + 1}$$なので（英文参照:Stackoverflow）、今回の問題の制約では必ず実行できることがわかります。

その後、次のような操作をできる限り繰り返すことで、一番重い袋と一番軽い袋の差をできるだけ小さくすることを目指します。

• 次の操作のどれかを行う

  • (A) 一番重い袋から一番軽い袋にアイテムを一つ移す

  • (B) 一番重い袋の重いアイテムと一番軽い袋の軽いアイテムを交換する

• その結果二つの袋の重さの差が小さくなるならば、袋の中身を更新する。そうでない場合は、袋の中身は更新せず、他の操作を試す

• 袋の中身を更新した場合、再び袋の重さがソートされた状態になるように袋を並べ替える。

まず、操作 (A) について検討します。軽い方の袋を$${A}$$、重い方の袋を$${B}$$とし、移すアイテムを$${x}$$とします。ここで、操作によって二つの袋の重さの和は変わらないことから、「操作後の袋の重さの差が小さくなる」と「操作後の袋がどちらも操作前の$${B}$$より軽い」が同値であることがわかります。

$${B \setminus x}$$が$${B}$$より軽いことは自明なので、$${ A \cup x }$$が$${B}$$より軽いことを示せば良いです。ここで、$${ A \cup x }$$と$${B}$$は両方に$${x}$$が含まれていてそのままでは天秤で比較できませんが、両方から$${x}$$を除いた$${A}$$と$${B \setminus x}$$を比較すれば良いです。

次に、操作 (B) について検討します。軽い方の袋$${A}$$から選ぶアイテムを$${x}$$、重い方の袋$${B}$$から選ぶアイテムを$${y}$$とします。まず、$${x}$$が$${y}$$よりも重くなければならないことは明らかなので、これを天秤を使って確認します。成り立つ場合は、この操作によって$${B}$$の重さが減ることがわかるので、操作後の$${A}$$の重さが操作前の$${A}$$の重さより軽いことを示せば良いです。これも、両側に含まれているアイテムを除いて天秤で比較することによって可能です。

操作によって袋の中身を更新した場合は、更新後の一番重い袋と一番軽い袋がわかるように、袋の重さがソートされた状態になるように袋を並べ替えます。このとき、一からマージソートするのではなく、中身を更新した二つの袋以外はすでにソートされていることを利用し、二つの袋の挿入場所をそれぞれバイナリサーチによって求める方が効率が良いです。

袋を並び替えたあとは、再び操作 (A) または操作 (B) が行えるようなアイテム$${x}$$またはアイテムのペア$${\(x, y\)}$$をループによる列挙によって探します。これを実装すると、ケース5の場合以下のような挙動になります。この解法は本番で60位程度相当のスコアを出すことができます。

改善1: クエリをキャッシュする

特に操作 (B) で交換するアイテムの重さを比較する場合に多いですが、同じクエリを投げていることがあることに気付きます。これは明らかにムダなので、クエリ結果は map (C++) または同等のデータ構造に保存しておき、再利用できる場合は再利用しましょう。クエリ結果を保存するとき、左右を入れ替えた場合の結果も保存するようにしましょう。これによって、本番で50位程度相当のスコアに改善します。

改善2: Q が大きい場合、最初に全アイテムをソートする

$${Q}$$ が十分大きい場合、最初に全アイテムをソートすることを考えます。全アイテムの順序がわかっていると、様々な最適化が可能になります。

移動に失敗したアイテムより重いアイテムは、それ以降移動できない

操作 (A) でアイテム$${x}$$を移動することに失敗した、つまり、$${ A \cup x }$$が$${B}$$より重くなってしまったとします。この時点以降、アイテム$${x}$$より重いアイテムは操作 (A) によって移動できることはないことがわかります。一番重い袋と一番軽い袋の重さの差は増えることがないためです。

操作 (B) についても同様のことが言えます。アイテム$${x}$$とアイテム$${y}$$の交換に失敗した場合、この時点以降、これより重さの差が大きいアイテムのペアの交換は必ず失敗することがわかります。二つのアイテムの重さの差の大小関係は必ずわかるわけではありませんが、$${x}$$より軽いアイテムと$${y}$$より重いアイテムの交換が必ず失敗することはわかります。

このように失敗するとわかっている操作をスキップすることで、クエリ効率が上がります。

アイテムの交換をするとき、最も近い重さのペアを選ぶことができる

操作 (B) でアイテムを交換するとき、$${x}$$が$${y}$$より重いようなペア$${(x, y)}$$を選ぶことができる点はもちろんですが、片側を固定したときにできるだけ重さが近い交換相手を選ぶことができる点も重要です。ある程度最適化が進んだ段階では、ほとんどの交換は失敗するため、できるだけ重さの差が小さいペアを見つけることが必要だからです。

最も、最初の段階からこのようにすると、各ステップでの改善が小幅になってしまいます。まずは操作 (A) を各アイテムに対して試し、それがすべて失敗した段階で操作 (B) を試すようにすれば、この段階では小幅な改善の方が必要だと言えそうです。

ソート結果を利用した初期解

全アイテムの順序がわかっている場合、各アイテムの重さを以下の方法で推定できます。

• $${N}$$個のアイテムの重さを問題文の設定通りに生成し、ソートすることで、$${i}$$番目の重さのアイテムの重さの推定値とする

• これを100回程度繰り返し平均を取ることで、推定の精度を高める

この推定値に基づいて、基本方針通りの改善を繰り返す（実際にクエリを投げないので、収束するまで操作を試すことができる）と、以下のような良い初期解を得ることができます。

タイトルで「統計的推測によらない」と書きましたが、この部分は統計的推測を使っているので、厳密には正しくありませんでした、すみません。ただ、高度な手法は使っていないと考えています。

改善3: Largest Differencing Method

さて、数の集合が与えられたときに、それをできるだけ均等に分割するという問題は、非常にシンプルな設定なので、有名問題かもしれないと考えます。実際にその通りで、検索してみると、数分割問題 (Partition Problem) という有名問題であることがわかります。opt100 という最適化に関するサイトの数分割問題のページは日本語の良い資料です。英語版 Wikipedia の Partition Problem のページには複数の近似アルゴリズムが書かれていて、その中でも Largest Differencing Method が実験的に性能が良い方法として紹介されています。このアルゴリズムの日本語の解説は先ほどの opt100 の数分割問題のページに書かれているので、アルゴリズムそのものの解説はそちらを参照してください。

Largest Differencing Method は強力な近似アルゴリズムではあるのですが、これをそのまま適用しようとすると、比較回数が$${O(N (\log N  + D \log D))}$$になるため、$${D}$$が大きい場合は比較回数が多くなってしまって、問題の条件では実行できるケースはかなり少ないことがわかります。そこで、一番重い袋と一番軽い袋に含まれているアイテムのみに対して Largest Differencing Method を実行することを操作 (C) として基本方針に追加することを考えます。クエリ回数消費は大きいので、操作 (A) と操作 (B) がすべてのアイテム・アイテムのペアに対して失敗したときのみに実行すると有効でした。

その他の改善

単一アイテムの大小関係は Floyd-Warshall アルゴリズムで拡張する

最初に全アイテムのソートができない場合でも、操作 (B) で単一アイテム同士の重さの比較をすることで、単一アイテムの重さの大小関係の情報が蓄積していきます。これによって、改善2で書いた単一アイテムの大小関係を利用した最適化を一部行うことができます。

ここで、$${w(x) < w(y)}$$かつ$${w(y) < w(z)}$$ならば$${w(x) < w(z)}$$であるという推移律を利用することで、より多くの情報を抽出することができます。これには Floyd-Warshall のアルゴリズムを使うことができます。単純に Floyd-Warshall のアルゴリズムを使うと更新毎に$${O(N^3)}$$となり重いのですが、以下のように bitset を活用することで十分高速になります。

// matrix: vector<bitset<N_MAX>>
// matrix[i][j] is true: w(i) < w(j) is true

// Floyd-Warshall
for (int i = 0; i < n_; i++) {
  for (int j = 0; j < n_; j++) {
    if (matrix[i][j]) {
      matrix[i] |= matrix[j];
    }
  }
}

交換するアイテムのペアを探すときに、ソートしながら探す

最初に全アイテムのソートができない場合、操作 (B) で交換するアイテムのペアを探すとき、袋の中のアイテムの個数を$${N, M}$$として最悪$${NM}$$通り試すことになってしまいます。このとき、二つの袋から交互にアイテムを取り出しつつ、アイテムを重さ順にソートした列に二分探索で挿入していくと、ソート済みの列で隣り合う「重い袋の軽いアイテムと軽い袋の重いアイテム」のみを考慮すればいいことから$${O((M +N) \log (M+N))}$$回の比較でできることがわかります。これは特に袋当たりのアイテムの個数が多い場合に大きい改善になります。

これら様々な改善を実装することで、本番で4位を取ることができました。リンク:提出コード