解法概要

パレットの初期状態は，幅1マスの蛇腹状の399マスとターン数が足りなくなった場合用の避難所の1マスとしました．

絵の具の混ぜ方について，ウェル \(i\) 個での残りとチューブの絵の具 \(j\) 本とを混ぜ合わせる操作を \(W_iP_j\) と表記します．
各作成すべき色（以下ターゲット）について，すべてのウェルに対して \(W_0P_1\)～\(W_0P_4\)，\(W_1P_0\)～\(W_1P_3\)，\(W_2P_1\)，\(W_nP_0\) を試し，評価値が最も高いものを貪欲に採用しました．

評価値は通常のスコアに加え，パレット上の絵の具の増減量・廃棄した絵の具の量・パレット上のウェル数・ターゲットの進行状況を元に計算しました．

消費ターン数はシード0～99では2500～5500ターンに収まっていました．
恐らくほぼターン数の制限が厳しいシードでのみ相対得点を得られた形となっています．
（プログラムのミスにより，それまでの消費ターン数を実際より大きくカウントし操作を選択してしまっていたことがコンテスト終了後に判明しました．（既に仕切りのある位置へ仕切りを配置しようとした時の「なにもしない」をカウントしてしまっていたために，例えばシード3では3782ターンしか使用しておらず，修正後は上限の4349ターン使用するようになりました（スコアは147670→65412）．）とはいえ修正後も同じく2500～5500ターンに収まっていました．）

解法詳細

パレットの管理

幅1マスの蛇腹状399マスと避難所の1マスとします．
これにより各ウェルは1次元の区間となり，ウェルを表す構造体 Well を用いて map<int,Well>：map[ウェルの開始位置] = Well として管理できます．

評価関数

評価値は，ターゲットとの誤差を \(e\)，絵の具のコストを \(c\)，加えた絵の具の量を \(p_a\)，廃棄した絵の具の量を \(p_d\)，パレット上のウェル数を \(w\)，ウェル数の目標値を \(w_0\)，ターゲットの進行割合を \(t\) として，

\[ 10^4e+(p_a-1)c+(1-t)(-(p_a-p_d-1)+(1+10^{-3}c)p_d+10^{-1}(w-w_0)^2)c \]

により計算し，この値が小さい方が良いとします．

補正部分について，

• \(1-t\)：終盤に近づくほど通常のスコアに近づけています．
• \(-(p_a-p_d-1)\)：パレット上の絵の具の増減量にあたり，他の色を作成する際に使用することを想定しペナルティを減らしています．
• \((1+10^{-3}c)p_d\)：絵の具のコストに応じて廃棄した際のペナルティを増やしています．
• \(w_0\)：パレットの幅 \(N\) に対して \(N^2/2.5\) としました．
  （スコアを見ながら調整したのですが，各ウェル2.5マスと想定よりも小さくなりました．）

となっています．

操作

\(W_0P_0\)～\(W_0P_4\) では操作前にウェルに残っている絵の具はすべて廃棄します．
\(W_1P_0\)～\(W_1P_3\) ではウェル内の残りが無くならない範囲で廃棄を許可します．
また，これらの操作では使用して良いターン数を，残りのターゲットに2ターンずつ残るよう定めました．
\(W_nP_0\) ではウェル5つの連結を上限とし，使用して良いターン数を（残りのターン数）/（残りのターゲット数）までとしました．

\(W_0P_1\)

避難所の1マスを使用します．
ターゲットの色 \(\boldsymbol{p_t}\) に対してチューブの絵の具の色 \(\boldsymbol{p_a}\) を全探索し， \(\lVert \boldsymbol{p_a}-\boldsymbol{p_t} \rVert\) を用いて評価値を計算していきます．

\(W_1P_0\)

ウェルを全探索し，各ウェルの色 \(\boldsymbol{p_w}\) について \(\lVert \boldsymbol{p_w}-\boldsymbol{p_t} \rVert\) を見ていきます．

\(W_0P_2\)

絵の具の色 \(\boldsymbol{p_a},\boldsymbol{p_b}\)を全探索します．

それぞれの混合割合を \(w_a, w_b\) \((w_a+w_b=1)\)とすると，誤差は \(\lVert w_a\boldsymbol{p_a}+w_b\boldsymbol{p_b}-\boldsymbol{p_t} \rVert\) となります．
ここで，\(w_a\boldsymbol{p_a}+w_b\boldsymbol{p_b}\) は2点 \(\boldsymbol{p_a},\boldsymbol{p_b}\) を結ぶ直線であるため，最適な割合で混合したものはこの直線への \(\boldsymbol{p_t}\) の投影点となります．
これは（幾何的な直交条件，あるいは誤差の2乗の式を展開したものの\(w_b\)微分を考え），

\[ \begin{aligned} w_b &= \frac{(\boldsymbol{p_t}-\boldsymbol{p_a})\cdot(\boldsymbol{p_b}-\boldsymbol{p_a})}{\lVert \boldsymbol{p_b}-\boldsymbol{p_a} \rVert^2} \\ w_a &= 1-w_b \end{aligned} \]

により計算できます．
また，実際に混合によって作成できるのは \(w_a,w_b>0\) となるものであり，投影点が線分 \(\boldsymbol{p_a}\boldsymbol{p_b}\) 上にあるものが対応します．

次に実際の操作を考えます．
絵の具を最適な割合の小さい順に \(p_1, p_2\) とします． マス数が \(n_0\) であるウェルに \(p_1\) を加え，仕切りの操作により \(n_1\) マスとした後 \(p_2\) を加えるとします．
このとき，最後のマス数 \(n_1\) のウェルには \(n_1/n_0 : 1\) の比で絵の具が混ざり，これが \(w_1 : w_2\) にあたるため，

\[ n_1=\frac{w_1}{w_2}n_0 \]

として計算できます．

各 \(p_a, p_b\) について \(w_a, w_b\) を求めたうえでウェルを全探索し，実際に生成される色を見ていきます．
このとき，実際に生成される色は \(n_0\) によって決まるため，既に見たマス数のウェルについては飛ばしました．

\(W_1P_1\)

最適な混合割合は \(W_0P_2\) と同様に計算できます．
マス数 \(n_0\) のウェルに絵の具 \(p_w\) が量 \(m\) 存在し，マス数 \(n_1\) とした後 \(p_1\) を加えるとすると，同様にして \(mn_1/n_0:1=w_w:w_1\) となり，\(n_1\)を計算できます．
削除する絵の具の量については全探索します．

\(W_0P_3, W_1P_2\)

絵の具の色 \(\boldsymbol{p_a},\boldsymbol{p_b},\boldsymbol{p_c}\) や 各ウェルの\(\boldsymbol{p_w}\) に対する \(\boldsymbol{p_a},\boldsymbol{p_b}\) を全探索します．

それぞれの混合割合を \(w_a, w_b, w_c\) \((w_a+w_b+w_c=1)\)とすると，誤差は \(\lVert w_a\boldsymbol{p_a}+w_b\boldsymbol{p_b}+w_c\boldsymbol{p_c}-\boldsymbol{p_t} \rVert\) となります．
ここで，\(w_a\boldsymbol{p_a}+w_b\boldsymbol{p_b}+w_c\boldsymbol{p_c}\) は3点 \(\boldsymbol{p_a},\boldsymbol{p_b},\boldsymbol{p_c}\) を通る平面であるため，最適な割合で混合したものはこの平面への \(\boldsymbol{p_t}\) の投影点となります．
\(\boldsymbol{v_a}:=\boldsymbol{p_a}-\boldsymbol{p_c},\boldsymbol{v_b}:=\boldsymbol{p_b}-\boldsymbol{p_c}, \boldsymbol{v_t}:=\boldsymbol{p_t}-\boldsymbol{p_c}\) とすると，この混合割合は（誤差の2乗の式を展開したものの \(w_a,w_b\) 偏微分を考え），

\[ \begin{pmatrix} \boldsymbol{v_a} \cdot \boldsymbol{v_a} & \boldsymbol{v_a} \cdot \boldsymbol{v_b} \\ \boldsymbol{v_b} \cdot \boldsymbol{v_a} & \boldsymbol{v_b} \cdot \boldsymbol{v_b} \end{pmatrix} \begin{pmatrix} \boldsymbol{w_a} \\ \boldsymbol{w_b} \end{pmatrix} = \begin{pmatrix} \boldsymbol{v_a} \cdot \boldsymbol{v_t} \\ \boldsymbol{v_b} \cdot \boldsymbol{v_t} \end{pmatrix} \]

によって計算できます．
\(\boldsymbol{p_a},\boldsymbol{p_b},\boldsymbol{p_c}\) が線形従属である場合は逆行列が存在しないため，確認が必要です．
（C++のEigenからNaNが帰ってきた場合に \(min(...) < eps\) では判定できていないという罠にしばらくはまっていました．）

実際の操作については \(W_0P_2\) と同様に，マス数 \(n_0\) へ \(p_1\) を加え，\(n_1\) とし \(p_2\) を加え，\(n_2\) へ \(p_3\) を加えるとし，\(n_2/n_0:n_2/n_1:1=w_1:w_2:w_3\)から，

\[ \begin{aligned} n_2 &= \frac{w_1}{w_3}n_0 \\ n_1 &= \frac{w_3}{w_2}n_2 \\ \end{aligned} \]

として計算できます．

ウェルについても同様に全探索します．

\(W_2P_1\)

隣接する2つのウェルについて，それぞれに仕切りを設置 → 間の仕切りを削除 → 絵の具の追加 を考えます．
マス数 \(n_{a0}\)，量 \(m_{a0}\) のウェルとマス数 \(n_{b0}\)，量 \(m_{b0}\) のウェルをそれぞれマス数 \(n_{a}\)，\(n_{b}\) に変えた後，絵の具 \(p_1\) を加えることを考え，\(m_an_a/n_{a_0}:1:m_bn_b/n_{b_0}=w_a:w_1:w_b\) から，同様にして \(n_a,n_b\) を計算できます．

\(n=0\) となる場合は \(W_1P_1\) に含まれると考え，候補から除外しました．

\(W_nP_0\)

連続する \(n\) 個のウェルについて，両端のウェル内へ仕切りを設置 → 間の仕切りの削除 を考えます．
\(m_i\boldsymbol{p_i}\) の累積和と \(m_i\) の累積和とを前計算しておくことにより高速化が可能です．

\(W_0P_4\)

絵の具の色 \(\boldsymbol{p_a},\boldsymbol{p_b},\boldsymbol{p_c},\boldsymbol{p_d}\) を全探索します．

色 \({p_i}\) を \((c_i,m_i,y_i)\) として，

\[ A:=\begin{pmatrix} c_a & c_b & c_c & c_d \\ m_a & m_b & m_c & m_d \\ y_a & y_b & y_c & y_d \\ 1 & 1 & 1 & 1 \end{pmatrix} \]

を使用して

\[ A\begin{pmatrix} w_a \\ w_b \\ w_c \\ w_d \end{pmatrix} = \begin{pmatrix} c_t \\ m_t \\ y_t \\ 1 \end{pmatrix} \]

を解くことによって，最適な混合割合 \(w_a,w_b,w_c,w_d\) を計算できます．
生成できるのは \(w_a,w_b,w_c,w_d>0\) となる場合であり，これは \(\boldsymbol{p_a},\boldsymbol{p_b},\boldsymbol{p_c},\boldsymbol{p_d}\) がつくる四面体内に \(\boldsymbol{p_t}\) が存在する場合に対応します．
この場合，実際のマスを考えなければ誤差0で生成できることになります．

与えられた絵の具から4色を選ぶ組み合わせについて \(A^{-1}\) を前計算しておくことにより，高速化が可能です．

\(W_1P_3\)

ウェルの色 \(\boldsymbol{p_w}\) に対して絵の具の色 \(\boldsymbol{p_a},\boldsymbol{p_b},\boldsymbol{p_c}\) を全探索し，\(W_0P_4\) と同様に計算します．

与えられた絵の具から3色を選ぶ組み合わせについて，あらかじめ

\[ A'^{-1}:=\begin{pmatrix} c_a & c_b & c_c & 0 \\ m_a & m_b & m_c & 0 \\ y_a & y_b & y_c & 0 \\ 1 & 1 & 1 & 1 \end{pmatrix}^{-1} \]

を計算しておくことにより，逆行列の補助定理を使用して，

\[ \begin{aligned} A^{-1}\begin{pmatrix} c_t \\ m_t \\ y_t \\ 1 \end{pmatrix} &= \begin{pmatrix} c_a & c_b & c_c & c_w \\ m_a & m_b & m_c & m_w \\ y_a & y_b & y_c & y_w \\ 1 & 1 & 1 & 1 \end{pmatrix}^{-1} \begin{pmatrix} c_t \\ m_t \\ y_t \\ 1 \end{pmatrix} \\ &= \left( A'+ \boldsymbol{v_w} \boldsymbol{e} \right)^{-1} \boldsymbol{v_t} \\ &= A'^{-1}\boldsymbol{v_t}-\frac{A'^{-1}\boldsymbol{v_w}\boldsymbol{e}A'^{-1}\boldsymbol{v_t}}{1+\boldsymbol{e}A'^{-1}\boldsymbol{v_w}} \\ &= \boldsymbol{t}-\frac{\boldsymbol{t}[3]}{1+\boldsymbol{w}[3]}\boldsymbol{w} \end{aligned} \]

\[ \left( \boldsymbol{v_w} := \begin{pmatrix} c_w & m_w & y_w & 0 \end{pmatrix}^{\rm{T}}, \\ \boldsymbol{e} := \begin{pmatrix} 0 & 0 & 0 & 1 \end{pmatrix}, \\ \boldsymbol{v_t} := \begin{pmatrix} c_t & m_t & y_t & 1 \end{pmatrix}^{\rm{T}} \right) \\ ( \boldsymbol{t}:=A'^{-1}\boldsymbol{v_t}, \boldsymbol{w}:=A'^{-1}\boldsymbol{v_w} ) \]

として高速化できます．