Skip to content

第12回Asprovaプログラミングコンテスト(AHC053)

問題概要

  • N(=500)枚の何も書かれていないカードと、L以上U以下の一様ランダムかつ独立に整数値を生成する乱数生成器がある
    • L = 10^15 - 2 * 10^12
    • U = 10^15 + 2 * 10^12
  • 最初、1以上U以下のN個の整数A_iを自由に選んでカードに書き込む
  • 次に、乱数生成器によってM(=50)個の整数B_jを生成する
  • 最後に、生成された各整数B_jについて、カードの和がその整数値に近づくようにカードを割り当てる
    • このとき、割り当てないカードが存在しても良い
  • できるだけ誤差が小さくなるように、整数A_iとカードの割当を求めよ
    • スコアは、誤差の和をEとしたとき、「round( (20 - log_10 (1+E) * 5 * 10^7 ) )」

時間

  • 4 時間

個人的メモ

アプローチ

LからUの一様乱数を1枚割り当てる

  • もし、1枚ずつしか割り当てないとすると、LからUまでの一様乱数をN枚用意しておくことで、おおよそ近い値がある可能性がある
    • B_j はLからUが50個に分割されているのに対し、A_i は500個用意されるので、おおよそ、10^10 ぐらいのオーダーの誤差にできる

A_i を2進数的に用意する

  • 自然な発想として、目標の B_j を2進数的に考えて、A_i を組み合わせで表現する方針が考えられる
  • 各B_jについて考えると、1枚をLぐらいとすると、残りの9枚で4 * 10^12 ぐらいの範囲を調整したい、ということになる
  • この範囲を冪的( 40^x とか )に調整すると、大きいところでの誤差が大きくなってしまうので、2^x * 10^9 とか、2^33 〜 2^42 とかで A_i を用意する
  • このアプローチだと、誤差は 10^9 とかが限界のため、150ケースで80G点ぐらいが限界の模様

A_i を等比数列的に用意して、貪欲法で割当を決める

  • 「A_i が大きい方から順番に、B_j (を超えず)に一番近づくやつに割り当てる貪欲」が強かった模様
  • 貪欲法で、最初の方は大きく埋めたいが、最後の方では細かい調整をしたい、などを考えると指数的か等比数列的に用意したくなる
    • ただ、B_j はばらばらなので、同じ値を複数用意するより、すべて別の値で用意したほうが微調整ができる可能性がある
  • この方向で個数や大きさなど調整するとかなり小さくできる模様
  • (解説放送) シンプルそうでかなり強いアプローチ
    • Aの最初のM個を、Bを多めにシミュレーションして 各B_j の最小値にしておく
    • Aの残りは、4e12から0.96ぐらいの等比級数にしておく
    • 割当は上記の貪欲法で埋める

A_i をランダムに用意して、半分全列挙で割当を決める

  • 今回、最上位では、K個の整数和がXになるようなものを見つける問題を考えて、半分全列挙で求めていたらしい
    • 順番に決めていく、両側探索する、ある山を一旦崩して残ってるA_iと合わせて再度最適に作り直す、など
    • A_i がランダムなのも重要そうで、また、[L - α,U + α)のように少し大きめで考えると良い模様
  • Kは3、4枚ぐらいでもかなりよくなり、最上位は、うまく工夫して、6や8枚を使う場合でのアプローチができていた模様
  • かなり強くで、ほぼ誤差0に近い答えが得られる

単純な近傍の焼きなましだとあまりうまくいかないかも

  • 割当の部分は、雰囲気的には局所改善できそうに見える
  • が、おそらく、A_i の種類や、近傍の用意の仕方(1点変更、2点swapだけとか)を結構気をつけないとちゃんと改善できないかも
    • A_i が指数的に用意していると、局所解から変化させるのが難しい
    • 温度調整・スケール調整や、複数個同士のswap、複数山を再構築、キックなどの大きめの近傍じゃないと改善できない

10^15スケールの調整方法

各B_j に対して、 10^15 付近のカードを1枚用意しておく

  • 各B_j について、1枚 10^15 付近のカードを入れておけば、残りは 10^12 の調整にできる
  • 単純にL(やLよりちょっと小さいもの)を使うのもあるが、各 B_j よりちょっと小さいものが用意できると残りの誤差が小さくなるのでうれしい
  • 何サンプルか B を生成して、各jについて最小値を採用するとかすると、各 B_j について小さめのものを用意できる

K枚使うことを前提とする

  • 各B_jに割り当てるカードの枚数をK枚と決め打つと、「10^15 / K」ずつすべてのA_iに加算すればよいので、考えなくてよくなる
    • (指数的に用意する場合は枚数が固定だと厳しいかも)

B_jの分布

  • M個の整数B_jは、生成方法を見ると一様乱数をソートしたもので、一様分布の確率変数を順番に並べたk番目の値はベータ分布に従い、ベータ分布の期待値からk/(M+1)になる
  • なので、LからUの間で、おおよそ等間隔に近いB_jになる

誕生日攻撃

  • 誕生日のパラドックス
  • 「同じクラスに同じ誕生日の人がいる確率が50%を超えるには、クラスに何人いればよいか？」という問題で、366人いれば100%になるが、50%を超えるのにはわずか23人だけでよい
  • これを応用した「誕生日攻撃」というものがあり、ある乱数(ハッシュ値)が同じもの(衝突)を効率的に探す
  • 今回は、k個の和が目的の値B_jになるものを見つけたいが、それも研究されているらしい

解説