🐈

AtCoder Heuristic Contest 025 13位解法

2023/11/11に公開

Rust

競技プログラミング

AtCoder

tech

問題

$N$ 個のアイテムがある。各アイテム $i$ の重さ $w_i$ は未知であり、 2つのアイテム集合の重さの総和を比較することの出来る天秤を用いて、以下の操作を繰り返し行う。
天秤の左右の皿にアイテムを好きなだけ乗せる。乗せたアイテムの重さの総和が左と右どちらが大きいか、もしくは等しいかが判明する。
この操作を $Q$ 回繰り返すことにより、出来るだけ重さの総和の等しい $D$ 個の集合にアイテムを分割せよ。

解法

以下の山登りをしました。

$D$ 個のグループにアイテムをランダムに割り振る
$D$ 個のグループを重さでソートする
重いグループと軽いグループを一つずつ選び、以下の操作のいずれかを行う
a. 重いグループから軽いグループにアイテムを一つ移動する
b. 1:1でアイテムをスワップする
c. n:mでアイテムをスワップする
操作によって、スコアが改善されていれば採用、グループの重さ順を更新する
クエリ数・実行時間が尽きていなければ、3.に戻る

工夫した点

クエリ結果の活用

アイテム集合の大小関係を知りたい時に、実際に天秤に乗せることなく、今までの比較結果を利用することで推論できる場合があります。
例えば、アイテム集合 $A$ 、 $B$ 、 $C$ に対して、 $A<B$ かつ $B<C$ であることがわかっている場合、 $A<C$ であることがわかります。
そこで、今までの比較結果をグラフとして保持しておき、クエリを投げるときには、そのグラフ上で探索をすることで、大小関係が推論できる場合があります。

例えば、以下の図のようなグラフが構築できます。ここで、頂点はアイテム集合、有向辺は大小関係を表します。（ここでは $A \rightarrow B$ と辺が伸びていれば、 $A < B$ であるとします）

上図のグラフが構築されていた場合、例えば、以下の比較結果が推論できます。

{1} < {1, 2} < {1, 2, 3} < {4, 5}より{1} < {4, 5}
{3} < {4}より、{1, 2, 3} < {1, 2, 4}、よって{5} < {1, 2, 3} < {1, 2, 4}

このように、比較結果を保持しておき、そのグラフ上で推移律を利用すると、過去のクエリの結果だけを活用するだけよりも多くの大小関係を推論することができます。

グラフの構築

以下のいずれかの条件を満たすとき、辺を引きました。

クエリ結果が得られたとき
$A \subset B$ ならば、 $A \rightarrow B$ と辺を引く
- （例） A = {1, 2}、B = {1, 2, 3}なら、 $A \rightarrow B$ と辺を引く
$A$ と $B$ に含まれるアイテムの差分が2つで、かつその差分の大小関係がわかっているとき、 $A \rightarrow B$ と辺を引く
- （例） A = {1, 2, 3}、B = {1, 2, 4}、{3} < {4}なら、 $A \rightarrow B$ と辺を引く

実装

アイテム集合の大小関係を知る必要があるときに、都度構築したグラフ上で探索し、大小関係が推論できないか検証するため、グラフのサイズが大きすぎると実行時間に間に合わなくなります。
そこで、クエリに登場したアイテム集合のみを頂点として追加するようにすれば、頂点数は最大でも $2Q$ 、辺の数はおおよそ $4Q^2$ 程度で抑えられます（実際には同じアイテム集合を用いたクエリが多いので、最大でも頂点数は1,000、辺の数は20,000程度でした）。

考察

山登りの近傍操作では、アイテムを一つ移動させたり、スワップさせたりしました。このような操作を行った場合、似たような集合がクエリに登場することが多そうです。そのため、グラフの頂点にアイテムを一つ乗せるのではなく、アイテム集合をそのまま載せたことで、クエリの節約に大きく寄与したと考えられます。

操作を行うグループの選択

山登りでは、アイテムのスワップ等の操作を行う2つのグループを選びます。
このとき、一般には重さの差が大きいグループの組を選んだ方が、操作の採用率・改善幅が高いと考えられます。しかし、一番重いグループと一番軽いグループを選び続けていると、そのうち操作が進まなくなります（局所解にはまった状態）。そこで、最初は一番重いグループと一番軽いグループを選び、時間経過に応じて、たまに2, 3, ..., min(5, D / 3)番目に重い・軽いグループを選ぶようなスケジュール関数を作成しました。

fn select_g_idx_pair(input: &Input) -> (usize, usize) {
    const P: f64 = 0.3;
    let par = 1
        + (time::elapsed_seconds() * (input.d as f64 / 3.).min(5.) / (TIME_LIMIT - 0.1)).round()
            as usize;
    let mut lighter_g_idx = 0;
    let mut heavier_g_idx = input.d - 1;
    for i in 0..par.min(input.d / 2) {
        if rnd::nextf() < P {
            lighter_g_idx = i;
            break;
        }
    }
    for i in ((input.d - input.d.min(par)).max(input.d / 2)..input.d).rev() {
        if rnd::nextf() < P {
            heavier_g_idx = i;
            break;
        }
    }
    (lighter_g_idx, heavier_g_idx)
}

上記の実装で操作するグループの組を選ぶことで、以下の利点が得られます。

有効な操作の割合を保ちながら、局所解を抜けることができる
入力ケースによる $Q$ の大小を気にする必要がなくなる

最終提出

上位解法を踏まえた考察

以下は、個人的な考察です。

アイテムの重さの推論

最上位では、アイテムごとの重さを今までのクエリ結果から推論する、ということをやっていました。

コンテスト期間中は、比較結果が得られた時の各アイテムの重さの事後分布を解析的に出そうと考えていましたが、複雑になりすぎて実現できませんでした。また、クエリ結果を直接活用する方が正確な情報が得られるため、効果が薄いのではないか、と考えていました。

最上位の方の解法を聞くと、アイテムの重さの分布をサンプリングすることで、各操作の期待値を出していたそうです。各操作の期待値を求めることによって、より有効な操作の割合を増やすことができる点が、最上位と差がついた点になっていそうです。