AHC048参加記 (プレテスト 211 位)

概要

方針

左19列を使って1行ずつ絵の具を配置し、右1列を使って壁を移動させながら混ぜることを考えました。そして、各目標色を作る前に、それぞれの行から何列ずつ絵の具を供給するかを最適化しようとしました。

しかし、これだと以下の例のように途中で絵の具が足りなくなることがあり、それをうまく調整することができずに困りました。

• 例: 19列ある状態から、8列供給する → 8列供給する → 8列供給したいが足りない

これを回避するために、目標色を0-19番目・20-39番目・…・980-999番目というように20色ずつに分け、目標色20色を、最初に配置した20色で作り切るように制約を付けました。コンテスト中、この制約を外したいとずっと思っていましたが、うまく外すことができませんでした…。

1つ工夫できたのは、途中で右側に絵の具が余っても良いことにした点です (順位表を見ていた感じ、これの有無で順位が100-150位くらい変わった気がしました)。

詳しい解き方

以下の2段階を最適化しています。

1. 目標色20色に、どの20色を割り当てるか

   • 目標色20色の平均を取り、それとの誤差が小さくなるように20色の選び方を最適化しました。

2. 各目標色を作る前に、それぞれの行から何列ずつ供給するか

   • 初期状態を「目標色1色に対して、供給行1行ずつその全てを割り当てる」状態とし、手数 T が制約をはみ出さない範囲で誤差を小さくする山登りを行いました。
   • 遷移は、以下の2種類です。
     • ある1マス分の供給を、別の目標色の前に付け替える
     • 1マス分の供給を2つ選び、供給のタイミングを交換する。

また、T <= 6500 のときは、目標色を40色ずつ分け、左右9列ずつに絵の具を配置するほうがスコアが良くなることを発見し、場合分けを追加しました。

感想・反省

盤面の自由度を上げていくと、それに応じてスコアも良くなっていくことが実感できて面白かったです。とはいえ、手数をうまく見積りながら最適化を進めていくのがとても難しく感じました。

以下を思いつけなかったのが心残りでした。

• 20色ずつ作るという制約を撤廃する。
• 途中で絵の具を捨てる操作 (操作3) を行う。