今回はわりと真面目に頑張りました！ ざっくり20〜30時間はPCの前に張り付いて、
「考察 → 実装 → 測定 → 順位表チラ見…」の無限ループ。

結果としては、問題の本質である「任意の色を正確に作り出す」アプローチには迫れなかったものの、「手数が足りなくて理想の色に寄せきれないテストケース」でそこそこ点数を稼げたようです。

- 最終システムテスト：52位
- パフォーマンス：2319

を獲得！ 長期コンテストの自己ベストを+300ほど更新できたので、素直に嬉しいです。

> ※この記事は、“お気持ち”でAHCと戦う業務プログラマーの記録です。
> ガチで強くなりたい勢には物足りない内容かもしれませんが、緑〜青パフォーマンスあたりを目指す方には何か刺さるものがあると信じています。

最終提出のアニメーションはこちらです。

問題概要

高橋画伯のため、K種のチューブ絵の具とN×Nのパレットを使い、指定されたH色の絵の具を順番通りに1gずつ作成。パレットの仕切り操作や絵の具操作をTターン以内に行い、色の誤差と絵の具の無駄を最小化する競争問題。詳細は下記をご確認ください。

まずはベースラインを知る

サンプル出力1を投げてみる

実は、最初に提供されるサンプル出力1をそのまま提出するだけで 1007位、パフォーマンス707 が得られます。

AHCのレーティングはコンテスト直後に+150のボーナスが乗るので、理論上は「サンプル提出」を繰り返すだけでも緑コーダーになれそうです。（未検証）

シンプルな貪欲解

次に試したのが「目標色に一番近い色を、手持ちの絵具から単色で選んで返す」というシンプルな解法。ヒューリスティック要素はほぼない貪欲な実装で、ABCでいうとB問題かC問題くらいの難易度ですが、これだけで パフォーマンス874 が出ます。AHC、優しい！

最終提出に至るまでのアプローチ

ここからは、最終的に提出したコードの主要なアイデアです。

グリッド分割

盤面を細かい区画（ウェル）に分割して、それぞれで色を作る方針を取りました。

- 本当はウェルを動的に“ずらし”て接触領域を稼ぐアプローチが良さそうでしたが、実装のしやすさを優先して固定グリッド方式に。
- 最終的には「上下4分割 × 左右20分割 = 80ウェル」という構成にしました。
- 1ウェルのサイズは、縦 `20/10/5/4` を試行。
- ウェルが大きいと多くの色を混ぜられますが、作れる色の種類（ウェル数）が減るというトレードオフがあります。
- 試行錯誤の結果、「幅1 × 高さ5」の細長いウェルを80個並べる形に落ち着きました。

3色混合テーブルの事前計算

この問題では何度でも色を追加できるのですが、色を多く追加すると溢れが発生したり、絵具が無駄になるということで、最大3色の絵具を混ぜて色を作ることにしました。3色追加する組み合わせは意外と多く、効率的に扱えるように工夫しました。

- 3色を混ぜる組み合わせは、単純計算で `20(R) × 20(G) × 20(B) = 8000通り`。
- ただし、色の順序を問わない `i ≤ j ≤ k` という制約を考慮すると、1540通りまで削減できます。
- 1000ターンにわたって何度も色を評価するのは重い処理なので、この1540通りから生成される色を事前に計算して3次元配列にマッピング。これにより、ほぼO(1)で目的の色を取得できるようにしました。

絵具の使い切りを意識したコスト計算

終盤になると、絵具を余らせたときのペナルティがスコアに大きく響きます。そこで、評価値に「使い切り」の概念を導入しました。

- `コスト = (絵具消費量) × (0.981 ^ 残り手数)`
- このように設定することで、終盤ほど絵具を使い切るような選択が優先されるようになります。
- ちなみに `0.981` は、実験を繰り返して見つけたマジックナンバーです。

“狙えないなら組み合わせを増やす”方針

任意の色を精密に作るのが難しかったため、代わりに「作れそうな色の候補をたくさん用意して、その中からマシなものを選ぶ」という方針に切り替えました。

- 各ターン、「80個のウェル × それぞれに0〜3色を追加する」という操作を考えると、約1.3万通りの候補が生まれます。
- これだけだと探索の幅が狭いので、ランダムにウェルを結合して多様性をアップさせました。
- 横に2〜4マス、縦に最大2マスをランダムに結合。
- 「結合 → 色追加 → 分離」という操作と「結合 → 分離 → 色追加」という操作パターンを作ることで、候補の色の多様性を確保しました。
- 実装をシンプルにするため、1手ごとに必ず全ウェルを再分離する作りにしています。

貪欲＋乱択

ここまで作り込んだものの、時間切れが迫ってきました。
「1手ごとに最善を選ぶ」だけの純粋な貪欲解法ではスコアが頭打ちに。本当はビームサーチや焼きなまし法に発展させたかったのですが……時間がありません！ AIに何度か投げたのですがうまく行きませんでした。そこで、実装コストの低い「乱択」を加えることに。

- 評価値に微小なノイズを加えながら制限時間いっぱいまでシミュレーションし、その中で最も良かった結果を採用。
- 体感ですが、これだけでパフォーマンスが +100 ほど伸びます。その“+100”が順位を大きく左右するので、貪欲法で行き詰まったら試す価値アリです。

高速化・開発効率化TIPS

精度ダウングレードで高速化

計算速度を上げる定番テクニックとして、`double` を `float (Single)` に落とす方法があります。

- 試したところ、約1.3倍の高速化 を確認できました。
- しかし、今回は計算誤差によるスコア悪化が無視できなかったため、不採用に。
- ビームサーチや焼きなまし法（SA）のように、多少の評価値のブレが許容されるアルゴリズムでは有効な選択肢です。

おまじない`pragma`

Gemini 2.5 Proに「C++のコードを高速化して！」と雑に頼んだら、以下のコードを提案してくれました。これを追加したところ、実際に速度が向上！

#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC target("avx2")

GPT-o3 vs Gemini 2.5 Pro

今回はAIをかなり活用しました。

- 実は途中までPHPで書いていたのですが、性能的に厳しくなり、C++への変換をAIにお願いして乗り切りました。
- AHC046ではGPT-4oが優勢でしたが、今回はGemini 2.5 Pro（2025/6/5リリース版） のほうが良いコードを生成してくれました。この1か月で勢力図が変わったのかもしれません。

GitHub Copilotの恩恵

似たようなコードを量産するときは、Copilotが神でした。ハマると体感10倍速で開発が進みます。GitHub ColipotはGPT-4oになっていたのですが、いい感じで補完してくれました！

（本当はループなどで綺麗に書くべき場面でも、AHCでは「とにかく速く動くコードを書く」ことを優先して愚直なコードが増えがちなので、特に助かりました）

`pahcer`のちょっといい設定

ローカルテストツールの`pahcer`で、並列実行の設定を少し工夫しました。

- `threads=0`（自動設定）だと、手元のCore i9-13900K（P8+E16=24コア）環境でなぜか16並列に。
- 実行時間2.9秒のテストケースだと、「16並列で一斉にスタート → 残りケースを4並列で…」という動きになり、待ち時間が発生していてもったいない。
- `threads=20`や`threads=25`に設定したところ、端数が減ってスループットが向上。テスト全体の時間短縮につながりました。
- （Rustのコア数取得周りの挙動がPコア/Eコア混在環境だとズレる場合があるようです）

反省点と今後の目標

反省点

- 「4色混合で任意の色を作れる」「絵具を正確な有理数比で抽出する」 といった、上位勢が当然のようにやっていた王道アプローチを完全に見落としていました。
- いかにもビームサーチが効きそうな問題設定だったのに、時間と実装力が足りず、貪欲＋αで終わってしまったのが悔やまれます。
- 自分の実装力と体力のなさを痛感したコンテストでした。

今後の目標

- コンテスト時間外でもちゃんと勉強して、年内に橙パフォ を目指します！
- AHC強者の数ごりさんが提唱している「短期AHCの過去問をひたすらupsolveする」メソッドを真似して、地力を付けたいです。
- ……と数か月前から言っていますが、今度こそやります！

以上、雑多ですが今回の取り組みのまとめでした。

質問やツッコミなどあれば、ブログのコメントやX (旧Twitter) https://x.com/ynishi2015 でお気軽にどうぞ！