EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)




Approach 最も多い色の連鎖をビームサーチして見つけるのを繰り返す貪欲を多スタートしました。
  • ビームサーチ
    • 今年の目標で禁止してたけど、chokudaiサーチより強かった。
      • chokudaiサーチは、貪欲を多スタートするんじゃなくて、1回で全体の最適化ができて強そうだったが。
  • 連鎖の探索:ビームサーチ中にわかる連鎖する前に必要なKnightの移動を、ビームサーチ後に連鎖の前に移動するの(文脈の入れ替え)をやった。
  • ビーム幅:64
  • 評価に使った特徴量1:連鎖する前に必要なKnightの移動数
    • 次の連鎖のためにKnightを残したいので。
  • 評価に使った特徴量2:スコア
  • 評価に使った特徴量3:2手前からの距離
    • 近い場所を探索してほしかったので入れたけど、あまり必要なかったらしい。
  • 評価に使った特徴量4:乱数



Example scores:
0) 142.0
1) 19797.0
2) 18371.0
3) 807.0
4) 182.0
5) 1355.0
6) 2438.0
7) 12067.0
8) 53667.0
9) 36781.0



...2015年のPegJumpingの復習が出来た気がした(同じようなApproachだったはず)。





Approach kickしました(パスを追加して、たまに強制的に削除する)。
  • パスの追加:パスのない点を選んで、4方向に適当に辺の数を割り振る。4カ所それぞれ深さ優先探索して有効なパスを見つける。
    • 3カ所以上に分岐させるのは追加する最初の1点のみ。深さ優先探索中の分岐はバグらせて間に合わなかった。
  • パスの削除:ランダムな正方形中に含まれるパスを削除する。
  • パスの探索:深さ優先探索。
    • 深さを深い方から10で制限して(今の探索中で見つかっている最も深いパスより10以上短いパスを探索しない)、どれだけでも長いパスを探索できるようにした。



Example scores:
0) 124.0
1) 9825.0
2) 1790.0
3) 3450.0
4) 1236.0
5) 424.0
6) 3698.0
7) 967.0
8) 4785.0
9) 874.0



... MMでは久しぶりにインタラクティブじゃなくて1回焼きなまして終わりの問題だったが、パスを見つけるのが結構めんどくさいかった。3カ所以上に分岐させるパスを見つけるのはもっとめんどくさかった。





Approach 貪欲です。
  • 各farmerそれぞれ別々に貪欲に動かす。farmer の wool が C 未満の場合、最も近い sheep の wool を刈に行く。そうでない場合、最も近い barn に向かう。
  • bfs で farmer を通過できるように探索して、自分より barn に近い farmer に wool を渡すようにする
    • 1%ほど良くなった。
  • farmer が barn の隣にいて、 1/4*C より多く wool を持っている場合は、barn に wool を渡すようにする
    • 2%ほど良くなった。
  • 各farmerが、今からどの sheep に向かうかの割当問題を解く
    • 最小費用流で、コスト = 定数 - 獲得できるwool数/turn数にして、コストパフォーマンスの和を最大化した
    • 5%ほど良くなった。
  • 終わりの処理をちゃんとやる。1000-N turn 以降、wool を持つ farmer を barn に向かわせる
    • 2%ほど良くなった。



Example scores:
0) 245.0
1) 5762.0
2) 3976.0
3) 380.0
4) 1090.0
5) 180.0
6) 1942.0
7) 629.0
8) 1212.0
9) 358.0



... 最近何かを捕まえてばっかり~。


↑このページのトップヘ