自分の解法

大きく3種類の解法を作りました。まだ「効く」方法というのがよく分かっていないので結構遠回りをしてると思います。

初提出

とりあえず動くプログラムを作ろうと思い書きました。

ターゲット色を一つずつ処理していく
- 簡単なビームサーチを用いて、持っている数色の組み合わせ方を探索
- ターゲットに一番近くなるようなものをパレットに追加して抽出
- 残った絵の具は全て取り除く

<aside> 🔍

回数を気にしなければターゲットをほぼ同じの色を作れることが分かりました。この提出のパフォは🟢900くらいでした

</aside>

クラスタリングによるルールベース

長期コンテストだったので最初からヒューリスティック手法を使うよりは良いルールベースの解法を模索しながな問題理解を深めようと思いました。

点数の式は以下

$$ 1 + D \cdot (V - H) + \text{round}(10^4 \times E) $$

色の追加回数 (V) の重要度はDの大きさによって決まり、Dが大きければ色の正確性よりも操作回数を減らすことが重要だと考えました。初提出のコードからどうやって操作回数を減らそうかと考えた時に、色が近いターゲットをまとめて処理すればいいのでは？と思いました。具体的には、

パレットをいくつかのwellにあらかじめ分けておく。グループにはそれぞれ空いているwellを割り当てていきそこで処理する

この時、
1. wellが大きい → より多くの色を一度に処理する → 操作回数は減少するが色の正確性は落ちる
2. wellが小さい → 細かくターゲットを区切って処理する → 操作回数は増加するが色の正確性は上がる
ので、TとDの値を元にwellのサイズを 1 ~ 33 ($\sqrt{H} = \sqrt{1000}$くらいなのでなんかいいかなと思った) の間で決定し、KMeansクラスタリングを用いてグループ分け。

<aside> 🔍

一番最初と一番最後のターゲットが同じグループに入ってたりするとそのwellが最初から最後まで占領されていることになるので良くないと思い、絵の具の色の3次元座標に「何番目のターゲットか」というインデックスを加えて正規化した4次元座標を用いてクラスタリングしました。そうすることで処理する順番が近いターゲットは同じグループに入りやすくなります。

</aside>
処理する絵の具を順番に見ていき以下のように処理
1. もしその絵の具のグループの処理がまだ始まっていない場合
  
  空いているwellをそのグループに割り当て、前処理で計算しておいたそのグループの平均色を初期回のビームサーチを用いて作る
  
  もし空いているwellがなかった場合は、既存のwellのうち最もグループの平均色に近い色を含んでいるものを選んでそのwellを割り当てる
  
  作られた色を抽出する
2. すでにそのグループのwellの処理が始まっている場合
  
  割り当てられたwellから色を抽出する。もし絵の具が残っていなかったらもう一度ターゲットを作り直してから抽出する。

この方法で、色の正確性もある程度保ちながら初期回と比べて処理回数が格段に減らすことができました。その後少し調整を加えたりして、最終的に🩵1500パフォくらいまで持ってこれました。ただ、グループの平均の色を全く同じ色で処理してしまっているのでEがまだ高かったです。 Vももう少し減らせそうでした。