Hatena::Grouptopcoder

yowa の TopCoder 日記

TopCoder yowa / twitter: @yowa

2015-01-13

SEAND2 (January Challenge 2015)

| 13:51 |  SEAND2 (January Challenge 2015) - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク -  SEAND2 (January Challenge 2015) - yowa の TopCoder 日記

マラソン問題。

問題

巨大な整数 A (~1000桁、十進表記で各桁は0でない)と、100個の整数B[i](~10^6)が与えられる。A の数字を並べ替えたものを A' としたとき、

score(A') = Σ(A mod B[i])

ができるだけ小さくなるよう、A' を求めよ。

やったこと

何か整数の性質を利用した賢い方法があるのかなーとか思いつつ、わからないので、ランダムに数撃ちゃ当たる作戦を取った。

スコア計算

A は文字列のまま持っておく。各桁の数字を操作したいので多倍長整数よりもそのままの方がいいんじゃないかな。多倍長を用意するのがめんどかったわけじゃないよ。

スコア計算をベタにやると、1000桁 x 100個分の mod(除算)をやることになって遅いので、

  • 初期解のスコアを(ベタに)求める
  • 前の解の2つの数字を入れ替えて差分だけ求める

という方針にした。

予め 1, 10, 100, ..., 10^1000, の mod B[i] を計算しておく。A mod B[i] が既知のとき、n 桁目と m 桁目を入れ替えたものを A' とするとそのスコアは、(A の n, m桁目の数字をそれぞれ D[n], D[m] とすると)

 A' mod B[i] = ((A mod B[i]) - D[n] * 10^n + D[m] * 10^n - D[m] * 10^m + D[n] * 10^m) mod B[i]
             = ((A mod B[i]) + (D[n] - D[m])*(10^m - 10^n)) mod B[i]

なので、除算1回 x 100個分の modスコアが計算できる。

探索方針

「既知の解をちょっと変更してスコア計算」という流れなので、山登りや焼なまし的な問題設定なんだけど、なんせ変更前後でスコアが違いすぎる(abs(10^m - 10^n) が B[i]よりすんごく大きい)ので、近傍を探索してるというよりはランダムサンプリングしてる感じなのだった。

ただ abs(10^m - 10^n) が min(B[i]) より小さい場合、ようは下の方のケタ同士の入れ替えの場合は、入れ替え前後でスコアが近い可能性がそれなりにある。たとえば末尾2桁を入れ替えて A = xxxxxx21 を A' = xxxxxx12 にしたら、高い確率で A mod B[i] より A' mod B[i] の方が 9 小さい、みたいな。

ということで、処理を2段階に分けて、

  • (第一段階)ランダムな2桁を入れ替えて、第一段階のベストスコアより良かったら第二段階へ。
    • 全体のベストスコアとは別に、第一段階でのベストスコアを記憶しておく
  • (第二段階)末尾6桁の permutation を全探索。

ということをやったのでした。

あとで思ったこと

第一段階で選抜するのは、「スコアのいいもの」より「値が揃ってる(max(A' mod B[i]) - min(A' mod B[i]) が小さい)もの」の方が、第二段階でごっそり減らせるチャンスが大きかったのかなあ、みたいな。