takumi152の競プロ日記

競プロとかその他諸々とかの記録

MM118 参加記

何も分からん、になった回でした。

問題

問題文(原文)はこちら

要約すると、

  • N*Nのグリッドと、D人のダンサーの位置が与えられる。
  • ダンサーは1ステップごとに上下左右に隣り合うマスに移動することができる（移動せずにそのマスに留まってもよい）。また、ダンサー1人ごとに、あるステップ数目の終了時点で居なければならない位置が入力として与えられる。
  • グリッドの各マスにはC色のうちどれかの色がついており、ダンサーが別のマスに移動すると、移動先のマスの色が別の色に変化する（移動しなかった場合は変化しない。また、複数人が同時に同じマスに移動した場合は、移動した人数と同じ回数だけ変化する）。どの色からどの色に変わるかはマスごとに入力として与えられる。
  • Sステップ終了後、(ある1色の連結成分の数)2の、全色についての総和が小さいほど良いスコアとなる。

という感じです。

やったこと

最後に提出したコードはこちら

各ダンサーの行動について、焼きなましをしました。

近傍の取り方

近傍は、あるダンサーの、あるステップ数目に居なければならない位置から次に居なければならない位置までの行動について、

  • あるステップ数目の行動と、その次のステップ数目の行動を入れ替え
  • （残りステップ数に余裕がある場合）ある一方向に移動して、直後に逆方向に移動する行動の挿入
  • ある一方向への移動と、それとは逆方向への移動を選択し、削除

の3通りとしました。

ただし、開始から1秒までは入れ替えのみを行って、それ以降は全ての近傍を使う、というようにしています。

評価関数

評価関数は、真のスコア*1000を共通の点数として（低いほど良い）、さらにNとCの値によって場合分けをしました。

  • N <= 25 の場合、各連結成分の大きさの2乗を点数から減算
    • Nが奇数かつC==2の場合、最初に偶数個ある色の連結成分についてのみ減算する（終わってから気づきましたが、これはあまり意味がなかったようです）
  • N > 25 の場合、↑を減算ではなく加算とする

という感じです。

連結成分の大きさの2乗を加減算する部分は、真のスコアのみで評価した場合にスコアが小さくなるまでどの程度近いか分からないため、その近さを表すような感じの部分です（伝われ）

実行例

seed = 7の場合の結果の例はこんな感じ（各マスの数字は色が変化した回数と、次に変化する色を表しています。考察の過程でビジュアライザに追加したやつです）。

f:id:takumi152:20200529155324p:plain

結果

結果（provisionalの時点）ですが、40位/68人でした。

普段は20位前後になることが多いですが、今回はかなり下振れしてしまったと感じています。

敗因

今回のMMでここまで下の順位になった点について、考えたことを以下に挙げてみます。

問題の特徴を考察しきれなかった

真のスコアの計算には連結成分の数を調べる必要があるため、愚直にやった場合O(N2)～O(N2 logN)程度の時間がかかります。そして自分はこの計算を（Union-Findを使って）愚直にやりました（差分計算をやろうとしたら逆に遅くなってしまった）。

一方で、上位勢の解法を見ていると、差分計算を高速化に成功していた方や、そもそも別の評価関数（隣接する色が異なるマスの数など）をメインとして使っている方が多かったようです。

差分計算の高速化ができなかった点はともかくとして、自分の場合、真のスコアを利用すること（と、それをできるだけ高速化すること）しか考えていなかったので、その部分に集中してしまって、より高速に計算できる評価関数、もしくは、言われてみればそれはそうってなるような点に気づけなかったことが失敗だったと考えています。

アルゴ系のコンテストでもそうですが、問題の特徴を考察する部分は割と苦手なので精進したいなーと思っています（こういうのはどう精進するのがいいんだろう）

始まってからしばらく手を付けなかった

今回は終了3日前ぐらいから手を付けました。

考察に掛ける時間が少ない分不利になったのはもちろんですが、今回を振り返ってみて、取り組む日数が多ければ、その分冷静に問題を考察できるんじゃないか？と思いました（ただ、今回の場合は1週間全部使ったとしても、良い評価関数には気が付けなかったかもしれない？）

ちゃんとやりましょう。

最後に

今回はかなり冷えた回になったので、次回以降でリベンジしていきたい。