問題

http://codeforces.com/contest/1014/problem/A2

無限に続くマス目の列があり，0,1,2,..と番号がつけられている．それぞれのマスには'A','B',...,'J'の10種類の色のうち1つがつけられている．与えられた初期状態では，プレイヤーは10色の塗料のボトルを合計10本持っていて(1本づつとは限らない)いる．

初期状態ではマス0,1,...9に10匹のカメレオンがいて，これらを塗料のボトルを投げつける操作を10000回行うことでできるだけ番号の大きいマスへ動かしたい．

操作は以下のように行われる． * プレイヤーは手持ちのボトルのうち1本と対象のカメレオン1匹を指定する． * 対象となったカメレオンは，現在自分がいるマスの番号より大きく，投げられたボトルと同じ色を持ち，他のカメレオンに占有されていないようなマスのうち最も番号の小さいマスへ移動する． * ボトルを投げたプレイヤーは，バッグから1本のボトルを取りだし，手持ちのボトルを再び10本とする．バッグから取り出されるボトルの順序はあらかじめテストケースごとに指定されている．

各テストケースの得点は，10000回の操作終了後にカメレオンがいるマスの番号のうち最も小さい数である．

成績

??? 暫定8位

解法・参加記

7/25

全探索を最も愚直に行うと, 各操作で投げるボトルと対象のカメレオンが10種類ずつあるので $(10\times 10)^{10000}$ 通り．重複を取り除けても到底無理．

ここで手持ちの10本のボトルの組み合わせは $\frac{19!}{9!10!}=$ 92378 通りに限られるので，これらに0,1,...,92377と番号をつける． (カメレオンの位置，手持ちのボトル)を「状態」として，状態の良さを測る評価関数があると仮定した上で次のDPを考える．

$dp[i][j]= i$ 回の操作後に手持ちのボトルの組が $j$ の時の評価関数の最大値 $(0\leq i \leq 10000, ~~0\leq j \leq 92377)$

このDPは状態数が $92738\times10000 \simeq 10^{10}$ , 遷移の回数が $92738\times10000 \times 10\times 10\simeq 10^{12}$ となり，ちょっと可能そうに思えてくる．

しかしこのDPでも間に合わないので，i回目→i+1回目の遷移を92738通りの $j$ すべてから行うのではなく，評価関数の値の大きいwidth個(width~100)の $j$ からのみ遷移を行うというビームサーチ風の手法にした．

次に評価関数について考えてみる．もしDPで全遷移を計算できたとして，その時最適解が求まるためには，「i回目の操作後に手持ちのボトルの組が同じになるような投げ方 $A_i,B_i$ について，評価関数の値が $f(A_i)>f(B_i)$ ならば，(i+1)回目以降を最適に投げた時の最終的なスコアは $A_i$ を経る操作の方が大きい」という性質が成り立っていてほしい．これにできるだけ近そうな評価関数を作ることが目標となる．

とりあえず評価関数を

static int eval(vector<int> position){
    int ret = 0;
    sort(position.begin(), position.end());
    for (int i = 0; i < 10; ++i)  ret += position[i] * (10-i);
    return ret;
  }

として， 37795.24点(width = 60)．

7/26

若干の高速化．それと評価関数を

static int eval(vector<int> position){
    int ret = 0;
    sort(position.begin(), position.end());
    for (int i = 0; i < 10; ++i)  ret += position[i] * (19-i);
    return ret;
  }

に変更．39355.21点(width = 72)．

7/27

実は評価関数でpositionをソートしているのがボトルネックになっていた．だが単純にpositionの総和を評価とすると，カメレオン集団が前後に分断されて一部のみが前進してしまいうまくいかない．そこで，総和 - 標準偏差*0.2 を評価関数として分断を防いだ．この変更によりスコアは少し下がったが，高速化の効果が上回り，39754.64 点(width = 101).

7/28

最後の20回に限り，評価関数に(最も後ろのカメレオンの位置)×10を足して目的関数に近づけた．

ビームサーチの多様性が低そう(あるターンで評価の高かったものばかり次に引き継がれる)だったが改善方法が思いつかず．評価関数に0~9の乱数を加算してみたらスコアが上がったが，探索方法の改善にうまく繋がらない．

これらの変更によって40000点を突破した．40091.95 点(width=97)．

note

焼きなましできるのだろうか？どこかの操作を変えた時に更新がO(S)より速くなる気がしないので，10000回の操作を200*50などに分割して，前のブロックからブロックごとに焼きなまして行けばいいのか？

Hoi_koro memo

Editorialと異なる解法をしたら更新するblog

codeforces Marathon Match 2 Colored Path

問題

成績