AHC001 hotpepsi

最終的な方針

最初の3.5秒

• 再配置
  • スコアが悪いセルをランダムに選び、近傍のセルを合計3-5個選び、1x1にリセットして、ランダムに成長させる
  • xとyの1ターンの成長量を決め、まずそちらに伸ばす。伸びきったら反対方向にも伸ばす
• 変形
  • 上にあるセルを迂回して変形したほうがスコアが良くなるなら、変形させる(下図)

後半の1.5秒

• 1px改善
  • 1px伸ばしてスコアが良くなるなら伸ばす
  • 幅を1px削り、代わりに高くしてみて、スコアが良くなるなら採用する
  • 高さを1px削り、代わりに幅を大きくしてみて、スコアが良くなるなら採用する
  • セルが接しているとき、境界線を1pxずらしてみて、スコアが良くなるなら採用する
• 押す
  • スコアが悪い場合、隣のセルを押す
  • スコアが良いセルが押されていて、空き地に移動できるなら移動する
  • スコアが良いセルが上か下から押されているなら、幅を大きくして高さを減らしてみる
  • スコアが良いセルが左か右から押されているなら、高くして幅を減らしてみる

スコア

• 提出時48,881,928,918、124位
• 入力サンプルの最初の10個は984757640,979692669,969269062,971213145,980883715,981599644,955689689,990451836,977322994,992553047

便利関数など

• マージンを含めて衝突するセルの集合を持っておき、変化が近傍だけで起きるときはそれだけを使って衝突判定した
• 上下と左右の関係で同じ関数を書きたくなかったので、一部の処理は全体を回転して4回実行するようにした。
• バッチで10個実行し、結果をCSV経由でGoogle Sheetに書き出して良くなっているか見た

考えたこと

• 最初、盤面全体を何回か再生成していたが、Nごとに違うパラメータを使っていた(生成する四角形の比とか)。そのようなアプローチだとアルゴリズムを変えるごとにパラメータを調整する必要があり、なるべくそのようなパラメータがいらないアルゴリズムのほうがよいだろうと思った。
• 四角形の領域をランダムに選んで改善しようと思ったが、面積当たりの点の個数がNによって違うし、点によって幅が広かったり面積が広かったりするので微妙だった。最終的なアプローチでは、全体から点をランダムに選び、その近傍だけ再配置するようにした。このアプローチではNにあまり依存しないようにできた。
• 隣から押されていたら(あるいは隣の隣から押されていたら)移動する、みたいなのを適切に実装するのは難しそうだったが、10px空いてたら移動する、みたいに適当な仮実装したらスコアが改善したので、そのまま最後まで使った。正式実装が大変そうでもとりあえず簡略版を書いて試すのは大事そう。
• とにかく面積を大きくするようにしていたが、スコア関数的に、スコアが良いセルから悪いセルに1pxあげたほうが良いことに最後に気づいて入れた。

やればよかったこと

• 時間はRDTSCを使った。おそらく1秒は3Gカウント。ただC++の標準関数(chrono)を使った方が良かった。
• 定番の方法(焼きなまし、山登り、ビームサーチなど)をやらなかった
• データ分析してない
• 自前のビジュアライザ書いてない
• プロファイリングしなかった
• メモを取っておけばよかった(これは終わってから書いている)

ログ

3/7 (日)

• 45.1G
  • 素朴解。ぶつからずに伸ばせたら伸ばす。

3/8 (月)

• 46.4G
  • 縦横を入れ替えてみる
  • 移動してぶつかる方向があるなら、反対方向に移動してみる
• 47.0G
  • 迂回して変形する(上の図)
  • スコアが悪い場合、隣のセルを押して移動させる

3/9 (火)

• 47.1G
  • スコアが良いセルが押されていて、細長くできるなら採用する
• 47.4G
  • ざっと実行してみてスコアが悪いものを覚えておき、先に埋める (実装したが不採用)
  • 回転関数を導入
  • 隣接したセルが細長くて邪魔しているとき、変形するようにした

3/10 (水)

• 進捗なし

3/11 (木)

• 47.3G
  • 4.5秒まで実行するようにした
  • フェーズを二つに分け、最初のフェーズは何回か盤面全体を再配置して一番良いものを採用するようにした
  • 配置可能な(別の点を含まない)四角形を、複数の縦横比でいくつか生成しておき、ランダムな順番で重ならなければ置く
• 47.9G
  • パラメータ調整

3/12 (金)

• 47.9G
  • バグ修正、Nの大きさ別のパラメータ変更
  • 結果を読み込んでそこからデバッグできるようにした

3/13 (土)

• 48.0G
  • 便利関数をいくつか追加
  • 乱数をxorshiftに変更
  • 回転を効率化
  • 押されているときに変形する量を抑えめにした
  • 最初のフェーズで、領域を何分割かして、そこだけ更新するようにした (不採用)

3/14 (日)

• 48.6G
  • 最初のフェーズで、スコアが悪いセルとその近傍のセルだけ再配置するようにした
  • セルの平均距離を閾値に使うようにした
• 48.8G
  • 隣接するセルの境界線を調整するようにした