AtCoder Heuristic Contest 048お疲れ様でした。相対スコア858,336,697,107点で2回連続の5位です！

今回も解説記事を書いていきます。

問題概要
解法
感想

問題概要

絵の具を混ぜて欲しい色を作ってね。

atcoder.jp

解法

概要

$T$ の値によって4通りの解法を使い分けました。

$T$ が中途半端な値の場合、途中まで上位解法を行った後、ターンが足りなくなったら下位解法に切り替えました。

$T\sim 4000$ : 固定パレット上で混ぜる
$T\sim 13000$ : 1色1レーン使って、4色を $b/a$ （ $a$ は定数）ずつ混ぜる
$T\sim 19000$ : 1色1レーン使って、4色を $p/q$ ずつ混ぜる
$T\sim 33000$ : 1色1レーン使って、4色を $(b+p/q)/a$ （ $a$ は定数）ずつ混ぜる

前提

指定された色 $(C, M, Y)$ を作っていく問題ですが、各色を3次元空間上の点だと思うと見通しが良くなります。

絵の具の色を表す点 $A, B, C, D$ を適切に4色選ぶと、四面体 $ABCD$ 内部の点は（任意の実数比で混ぜ合わせることができれば）自由に作ることができます。

作成したい色を表す点を $P$ とすると、点 $P$ が四面体 $ABCD$ の内部にあれば点 $P$ を作ることができます。これは四面体 $ABCD$ の体積と、4つの四面体 $PBCD, APCD, ABPD, ABCP$ の体積の和が一致しているかどうかを調べれば良いです。*1 *2

このときの四面体 $PBCD, APCD, ABPD, ABCP$ の体積比を $a:b:c:d$ とすると、絵の具 $A, B, C, D$ を $a:b:c:d$ の割合で混ぜることで所望の色 $P$ を得ることができます。*3 *4

ということで、 $T$ が大きいときはできるだけこれの達成を目指します。

① T~4000くらいのとき

$T$ が小さいときは上記の4色混ぜをするだけの手数を確保できないので、たくさん小部屋を作って適当に混ぜました。

レーンを $N$ 本用意して、レーンを縦に2分割したセルを作り、各レーンの中で絵の具を混ぜました。操作の候補として、

レーン $i$ に対して、仕切りを動かさず、0, 1, 2, 3, 4g の絵の具を足してから採取する
レーン $i$ に対して、仕切りを削除し、適当な場所に動かした上で、0, 1, 2, 3, 4g の絵の具を足してから採取する

を使い、ビームサーチしています。

絵の具をどのように足せば良いかについて考えます。セルに既に入っている絵の具の色ベクトルを $\boldsymbol{x}$ 、量を $w$ とし、目標とする色ベクトルを $\boldsymbol{y}$ とします。このとき、追加する絵の具の量を $\Delta w\ (=1, 2, 3, 4)$ とすると、追加したい絵の具の色ベクトル $\boldsymbol{z}$ は、

$\boldsymbol{y} = \dfrac{w \boldsymbol{x} + \Delta w \boldsymbol{z}}{w+ \Delta w}$

より、

$\boldsymbol{z} = \dfrac{(w + \Delta w)\boldsymbol{y} - w \boldsymbol{x}}{\Delta w}$

となります。あとは $\Delta w$ gの絵の具を混ぜてこれに近い色を作る方法を高速に探せばよく、予め $\Delta w$ gの絵の具の混ぜ方 ${}_K H_{\Delta w}$ 通りを前計算してkd-treeに格納しておくと、 $\boldsymbol{z}$ に近いいい感じの色を $O(\Delta w\log K)$ で検索することができます。*5

② T~13000くらいのとき

$T$ が大きくなると少しできることが増えてきます。ここから、前述の4色混ぜを行っていきます。

まず $K$ 本の絵の具のタンクを用意し、それぞれに1gずつ絵の具を入れておきます。各タンクから好きな量だけ絵の具を取り出すことができれば、所望の色を作り出すことができます。

これを実現するため、下図のようにタンクの内側に仕切りを追加してから外側の仕切りを開けるという操作をします。これにより、タンクの中の絵の具を $1/a$ 刻みで取り出すことができます。なお、絵の具が足りなくなったときは仕切りの位置を最大までリセットしてから1g足します。

これで各色を好きな量だけ取り出すことができるようになりました。これを4色について繰り返して混ぜます。欲しい量ピッタリ出すことは基本的にできないので、色ごとに欲しい量より小さい側と大きい側の2通りを考え、bit全探索で $2^4$ 通り全部調べることにします。

これを使って、各目的色に対して4色ずつ選んで混ぜることを繰り返すビームサーチをします。*6 なお、混ぜて採取した後の絵の具が微妙に残ってしまいますが、私の解法では毎回余った分は捨ててしまいました。*7

これにかかる手数を考えます。目的色1色あたりにかかる手数を考えると、

絵の具を足す: 平均 $1$ 手（合計で $H$ 回くらい追加するため）
絵の具を採取する: $1$ 手
絵の具を捨てる: $1$ 手
絵の具を出す量を調節する: $2\times 4 = 8$ 手（1色あたり $2$ 手を $4$ 色分）
絵の具を足すときに仕切り位置のリセットを行う: 平均 $2$ 手

となるため、 $T$ が $13H=13000$ くらいからこの解法が使えることになります。

③ T~19000くらいのとき

$T$ がさらに大きくなると、より精緻に取り出すことができるようになります。下図のように、一旦タンクの長さを伸ばしてから取り出すことを考えます。

タンクの長さを $L$ 、現在の絵の具が占めるマスの数を $a$ とすると、 $a\le p\le q\le L$ であるような有理数 $p/q$ を作ることができます。このようにすると、取り出す量を概ね $1/L^2$ 刻みくらいのオーダーで制御することができ、精度が向上します。

もう少し詳しく解析しましょう。簡単のため $a=1$ のケースを考えると、 $1\le p\le q\le L$ を満たす既約分数 $p/q$ の数は、オイラーのトーシェント関数を $\varphi(n)$ として、 $\Phi(L)=\sum_{k=1}^L\varphi(k)$ と表すことができます。これは $\Phi(L)\sim \frac{3}{\pi^2}L^2+O(L\log L)$ と近似できる*8 ので、ざっくり平均 $3/L^2$ 刻みくらいで量を調整することができることになります。*9

この解法にかかる手数を考えます。目的色1色あたりにかかる手数を考えると、

絵の具を足す: 平均 $1$ 手（合計で $H$ 回くらい追加するため）
絵の具を採取する: $1$ 手
絵の具を捨てる: $1$ 手
絵の具を出す量を調節する: $4\times 4 = 16$ 手（1色あたり $4$ 手を $4$ 色分）
~~絵の具を足すときに仕切り位置のリセットを行う: 平均 $2$ 手~~ ← これは不要

なので、 $T$ が $19000$ くらいからこの解法が使えることになります。

④ T~31000くらいのとき

$T$ がかなり大きいときはもう1段階ステップを増やしました。

下図のように、各タンクの片側だけでなく両側から出せるようにしておきます。左側から大雑把に出して、必要に応じて右側への「繰り下がり」を行った後、右側で分数方式を使って微調整をする帯分数的な制御をしました。*10

このように制御すると、 $(b+p/q)/a$ を作り出すことができます。かなり良い精度が出せて、色の誤差は $10^{-5}$ くらいまで小さくすることができます。

AHCは暫定6位でした。めちゃくちゃ自由度が高くて面白かった……！
4色使うと四面体の内部の色を自由に作れるので、Tが足りていれば目的の色ごとに4色選んで混ぜていきました。いい感じの帯分数x+p/qを作るのが強くて、ビムサを走らせた後に最後を焼きなまして余りが少なくなるようにしました #AHC048 pic.twitter.com/Y6DIIEfND9
— TERRY (@terry_u16) 2025年6月9日

その他の工夫

焼きなましによる無駄な絵の具の削減

$D$ が大きいケースはできるだけ最後に余る絵の具を少なくしたいので、ビームサーチを1000ターン行った後、最後の20ターンだけ焼きなましを行いました。

十分精度よく絵の具を制御できると仮定して、余った絵の具は毎回捨てることにすると各ターンが独立になるため、各ターンでどの絵の具をどのくらいの量使うかを焼きなましました。

最後の20ターンはビームサーチと焼きなましの両方を試し、良かった方を採用しています。

使用する絵の具数の削減

絵の具は $K$ 色与えられますが、パレットの大きさは固定なので、絵の具の種類数が多すぎると1色あたりに使えるマスの数が少なくなり、制御の精度が落ちてしまいます。そのため、解法①以外では不要な絵の具を予め削除しておきたい気持ちになります。*11

3次元空間上で $K$ 個の点を考えると、これらの点の凸包を構成する点だけあれば凸包内部の点を全て作ることができます。そのため、そのような絵の具だけを残して他の絵の具をなかったことにしました。*12

3次元凸包の実装は、Codeforcesブログの $O(n^2)$ のアルゴリズムを参考にしています。

感想

自由度がものすごく高くてとても面白い問題でした。個人的には Graphorean の次に好きな問題です。

4色を混ぜるところまでは割とすぐに思い付いたのですが、それだけだと順位がズルズル落ちていったので、どうやって精度を上げるべきか相当悩みました。しばらく $k$ 進数を考えていたのですがそこまで精度が上がらず、また手数もかなり消費してしまうので苦しかったです。分数解法は最後の土曜深夜に思い付いたのですが、それで精度が爆上がりしたのがかなり面白かったですね。