AtCoder Heuristic Contest 004(AHC004) -Alien's Genome Assembly- 参加記

AtCoder AHC

問題

結果

6,406,046,257点で30位。限界を感じる。

seed=0, score=66981132

解法

  1. 別の文字列に含まれるものは削除する。残った文字列について、何個の別の文字列を含むかをその文字列の重要度とする。その文字列が現れれば、重要度分の文字列が現れたことになる。
  2. 任意の2つの文字列について重複数を計算する。例えば、ABCB とCBC なら 2、ABCBC とBCBCD なら 4。また、重複数が最大となる相手の文字列を記録しておく。複数ある場合は全て記録する。
  3. 任意の文字列からスタートして、長さが20になるまで連結するビームサーチを行う。連結は2.で記録した重複数最大の文字列でのみ行う。ソートの評価値は連結した文字列の重要度の和とする。
  4. 作成した長さ20の文字列の内、出現していない文字列の数が最大のものを選択し、答えの一行として採用する。
  5. 出現した文字列を削除して、3・4を繰り返し行う。

その他

  • 文字列はビット表現する。文字種はA〜Hの8種類なので、1文字3ビットで表現できる。一行20文字なので64ビット整数に収まる。
  • 横方向のみ考えて、縦方向の出現は考慮しなかった。seed=0だと縦に出現しているのもあるがたまたまで、長い文字列の場合は横方向のみしか出現しない。

反省点

  • ビームの幅調整と時間制御がなんだか上手くいっておらず、結局幅固定で提出結果で時間ギリギリになるように調整した。パラメータによって幅を変えた方が良いのは明らかで、ちゃんとやれば1、2コ順位上がってた気がする…。