MC Digital プログラミングコンテスト2025（AtCoder Heuristic Contest 048）参加記
1. はじめに
AHC048お疲れさまでした。
プレテスト24位を達成することができました！
（システムテストは相対スコアがかなりブレそうなので怖いですが…）
ここまで高順位をとれたのは初めてなので、ウキウキで記事を残しておこうと思います。
なるべく考察手順とかも書いたので、参考になれば幸いです。
2. 問題
パレットの上で手持ちの絵の具を混ぜ混ぜして、画伯が欲しい色を1000個作ってね。
パレット上では指定ターン数まで絵の具の追加や仕切りの上げ下げができるよ。
絵の具を使った量と目標色の誤差を最小化しよう。
3. 考察
問題をぱっと見て、とりあえず色々貪欲を試してみたくなる衝動に駆られましたが、闇雲に発進すると危ないです（N敗）。
焦らずに問題を深く理解して、得点の理論値や入力データの分布などを徹底的に理解しておくのがAHCで勝つコツだと最近気づいたので、頑張って考察します。
3.1 得点計算からの考察
上記の計算方法を見てぱっと考えたこととしては、以下の通りでした。
- 作る絵の具の量1000gに対してパレットの大きさは十分広いので、絵の具を破棄したり余したりすることなく混ぜればコストDはかなり低くできそう。
- 目標色との誤差に1e4の係数が掛かっているので、ここが非常に大きい。何とかして誤差を小さくする混ぜ方を考えるのが効率が良さそう。
結果的に、誤差0を目指す方針は正しかったようです（最良ケースでE<=100程度は達成できる）。
最上位陣はDも0に近づけていましたが、自分は絵の具を廃棄する操作を入れてしまい、数回分のDのコストが発生する解法になりました。
3.2 入力生成方法からの考察
誤差Eを最小化する方針を立てたところで、始めに考えたこととしては、最適な混合をしたとして本当に目標色が作れるのか？ということでした。
例えば手持ちの絵の具が、CMY= (0,0,1), (0,1,0),(1,0,0)のような基底ベクトルをいくつか持っていればどんな色でも作れそうですが、
手持ち絵の具がランダム生成なので、目標色もランダム生成であれば作れない色もありそうです。
上記の入力生成方法をじっくり観察すると、数式が長いですが結局のところ、
「手持ち絵の具をランダム比率で混ぜて目標色を作ってる」という結論を導くことができます。
そこで次に考えたのは、以下の2つです。
- 目標色が手持ち絵の具のどのような混合比率であるかを、逆算することはできないか？
- 逆算できたとして、本当にその比率で混ぜるような操作が可能か？
後者が達成できないと、どうしようもないので、任意比率で混合するパズルを考えることにしました。
3.3 絵の具を任意比率で混ぜる方法はないか？
山場その1。
このパズルをどう解くかは始め中々思いつかず、一日中考えていました。
なんやかんや考えて思いついた方法は、手持ち絵の具専用エリアと混合用エリアを分ける方法でした。
具体的には以下の手順で絵の具を混合します。
手順1. K本の通路と混合専用エリアを作る
K=20のときの初期盤面
K=4のときの初期盤面
上図のように、K本の通路を19x20マスで作り、一番下の行を混合専用エリアとしました。
各通路は1個の仕切りで任意の比に分割できるよう、一筆書きできる形である必要があります。
なお、N=20をKで割り切れない場合、例えばK=6の場合は、[3,3,3,3,4,4]のようにN=20を分割しました。 （本当はKで均等に分割すべきですが、良いパズルが思いつかなかった&誤差への影響は少なそうなので妥協しました）
手順2. 仕切りを上げ下げして任意の分割で絵の具を混合エリアに送り込む。
例として、初期盤面からある絵の具を2/5の比率で送り込みたい場合は、以下のような操作をします。
また、この2/5の比率で送り込んだ後の盤面は、絵の具が3ブロック余るので、次の色を調合するときは以下の選択肢をとることができます。
- 操作a：1/3, 2/3, 3/3の比率で混ぜる（必要ターン数2）
- 操作b：ブロックを下側に拡張して、1/4～3/4、1/5～4/5、1/P～(P-1)/Pの比率で混ぜる。※Pは通路の最大ブロック数。（必要ターン数4）
基本的には空間の広い操作bをとることになるので、1個の絵の具を混合エリアに送り込む操作は、4ターン掛かると見込んでよいでしょう。
また、操作bを繰り返せば、X/Pを作った後、更にY/Pを掛け合わせることで、より精度を高めることができます。
手順3. 混合エリアから1.0gの目標色を配達し、余った絵の具は捨てる。
上図は、2つの絵の具を2/5+3/5で作り、混合して回収する例です。
上図の例ではピッタリ1.0gの絵の具を作れますが、自分の解法では分母を揃えてピッタリ1.0g作るようなことはせず、目標色に近ければ1.0gを超えることも許可しました。
そのため、絵の具が余った状態で操作bを行おうとすると、手持ち絵の具エリアに混合後の絵の具が混ざってしまうので、廃棄するようにしました。
3.4 目標色が手持ち絵の具のどのような混合比率であるかを、逆算することはできないか？
山場その2。
先ほどの考察で、任意の比率で絵の具を混ぜ合わせることができることは分かったので、次は混合比率の解を求めることを考えます。
定式化をすると、以下の問題に落とし込むことができます。
- 3次元ベクトルK本をまとめた行列A (3 x K)と、目標ベクトルy (3 x 1)がある。
- 任意の重みベクトルをx (K x 1）として、Ax = yとなるxを求めたい。
- （できれば絵の具の廃棄量を少なくするため、重みxの合計を1.0にしたい）
もう少し数学っぽく書くと、以下になります。
これは一般的に、 非負制約最小二乗問題（NNLS, Non-negative least squares）と呼ばれる問題に近いようです。（Chat GPTに教えてもらいました）。
制約に不等式制約があり、目的関数も2次関数なので、行列計算などで簡単に解くことはできません。
この問題を解くアルゴリズムはいくつかあるようなので、Wikiを見てもらうのが早いと思います。（というより、自分も正確に理解してないので説明できません…）
AtCoder環境で使えるアルゴリズムとしては、C++の行列計算ライブラリEigenに、NNLS実装が公開されていたのでそれを使うことにしました。
なお、注意点として、NNLSは非負実数の制約だけを扱いますが、今回はなるべく絵の具の量の合計を1にしたいので、係数の総和=1の制約も追加されます。
その場合は、以下のような拡大行列を考えると、係数の総和が1からずれた場合の二乗誤差も0に近づけるように問題を書き直すことができます。
自分は上記のような数理最適化でゴリ押しで目標比率を割り出しましたが、正直あまり筋の良い方法ではないとは思います。
ヒューリスティックらしく操作列の近傍を探索をするか、前計算で必要な色の組み合わせと目的の分数の組み合わせを全探索する方が良さげではあります。
個人的な直観としては、誤差が滑らかになるような近傍操作になるか不安だったため、近傍探索系のアルゴリズムは採用しませんでした。
（追記）コンテスト後に他の方の解法を見ていて気付きましたが、実は幾何的に目標色を作る比率は計算できるようです。 おそらく4点の凸包を求めて、適当な頂点から目標色となる凸包内部の点に向かって線を引き、平面との交差点とかを求めていけば良さそう？？
4. 実装 & 工夫点
ここからは、実装上の課題や工夫点などを話します。
4.1 NNLSで求めた係数に近い分数を二分探索する
考察フェーズでも述べたように、目標色を任意の分数で混合エリアに流し込むことができますが、この分数のパターンは実は結構多いです。
通路の大きさがP、現在の仕切り位置がQとすると、1回目の操作でできる分数パターンは、
[1/Q, 2/Q, ..., Q-1/Q], [1/Q+1, 2/Q+2, ... Q+1/Q+2] ... [1/P, 2/P, ..., P-1/P]
となり、K=4の場合は通路の大きさが 20 x 20 / 4 = 100程度になるので、O(1002)の全探索をする羽目になります。
更に、分数操作を1回するだけならまだしも、分数操作を2回行うと O(1004）個程度の分数パターンがあります。
そのため、この分数パターンをあらかじめ列挙してソートしておくことで、NNLSで求めた係数に近い分数が何かを二分探索できるように工夫しました。
4.2 ターン数が微妙なとき（11000<=T<=19000）はDPで何色混ぜるかを決めておく。
前提として、3次元の色は適切な3+1=4色があれば作ることができます。（カラテオドリの定理より）
manabitimes.jp
実際にNNLSで混合比率を求めると、非ゼロな係数が4つ現れ、その時の誤差は0になることが確認できました。
逆に、2色や3色で目標色を目指そうとすると、ほとんどのケースでそれなりの誤差が生じます。（たまたま2～3色で表せることもある）
そのため、基本は4色混合をしたいのですが、4色を任意比率で混ぜようとすると、
- 分数分割操作：4ターン x 4色
- 追加・配達・廃棄： 3ターン
の計19ターン程度かかることになるので、H=1000 x 19 = 19000ターンは確保できないと誤差0を目指すことはできません。
よって、19000ターン以下のときは以下の戦略をとることにします。
- 2色混合と3色混合の全組み合わせで、全てのH=1000個の目標色に対して、最適な係数をNNLSで求めておく。
- DP[h][t] = h色をtターンで画伯に渡したときの誤差の最小値として、DPを解く（T<=19000, H=1000なのでギリギリO(108)程度に収まります）
ある目標色がたまたま2～3色の混合で誤差が小さくできる場合、その目標色だけは2～3色で混合するようになるので、ターン数が節約できます。
4.3 ターン数が更に小さいとき（T<=11000）は貪欲
2色混合でも1回あたり11ターン掛かるので、H=1000 x 11 = 11000ターン必要です。
こうなると完全に別戦略をとる必要がありますが、実装時間もなかったので適当な貪欲でごまかしました。
（正直大した実装はしていないので、詳細は省略します。適当に4個のマスを作って、絵の具の追加と隣のウェルとの混合を全探索しました。）
4.4 ターン数は十分確保できるが、Dが大きい場合の改善
ターン数が大きい場合（T>=35000ぐらい）、目標色との誤差の総和は2～3ケタ程度に収まるようになってきますが、 そうなるとコストDの方が重要度が増すパターンがあります。
よって、後半はNNLSを更に改良して、今パレットに存在している絵の具の量を上限の制約とする最適化問題を解くことで、 なるべく絵の具の量の追加を少なくなるようにしました。（なお、手法としては勾配降下法的な方法でこの問題を解きましたが、ChatGPTに書かせて何も理解していません）
5. 感想
今回、24位を達成することができて非常にうれしいです。
瞬間最高順位は4位までいったので、かなり夢を見ることができました。
ただ、当たり方針と思える基本的なアイディアは1週目の土日の時点で思いついており、実装&改善に1週間ほど掛けて練ったつもりでした。
それでもトップ10には入れなかったので、最上位陣は当たり方針を引いて更に洗練された改善をしているだろうことを考えると、まだまだ先は長そうです。
これからも精進していきます。
統計検定2級 合格体験記
統計検定2級に合格したので、これから合格を目指す方の参考になるように、勉強法などをメモしておきます。
目安
勉強時間：〜50時間程度（高校数学は理解している前提）
費用：1万円（CBT方式受験料7000円、公式問題集2000円、電卓なければ1000円）
おすすめ勉強方法
Youtubeの動画で統計知識をざっくり掴む
大学の数学・物理などをわかりやすく教えてくれる、通称「ヨビノリ」さんの授業動画。
「推定」や「検定」といった概念をざっくり掴むのにとても良い。たまに出てくるボケはスルーで（笑）
目安勉強時間：3時間程度
「統計WEB」で試験範囲を一通りインプットする
解説はわかりやすい上に、練習問題もついている。
全部の章を読み切り、練習問題を1〜2周するだけで、合格できるだけの知識は身につく。
少しもったいないのは、公式が突然出てきて、厳密な数学的説明が省かれているところ。
ただし、数学的背景は重要ではない場合が多いので、
割り切って、公式を道具として使えるようにする練習をまずは優先しよう。
目安勉強時間：20時間程度
「高校数学の美しい物語」で数学的理解を深める
「統計WEB」で拾いきれなかった数学的理解を深める。 期待値・分散に関する公式や、さまざまな分布に関する数学的背景について、よくまとまっている。 特に、この辺りの記事が非常に参考になる。
- 不偏標本分散の意味とn-1で割ることの証明 | 高校数学の美しい物語
- 二項分布の平均と分散の二通りの証明 | 高校数学の美しい物語
- 期待値と分散に関する公式一覧 | 高校数学の美しい物語
- 歪度，尖度の定義と意味 | 高校数学の美しい物語
期待値・分散に関しては、定義から理解して、
典型的な性質を理解しておかないと解けない問題も出題されるので、
よく勉強しておこう。
目安勉強時間：数時間
過去問を解く
年度別に数冊出版されているが、最新の過去問だけでOK。公式解説はあまり評判がよくないので、
【統計検定2級 解説記事一覧】 | ブログ | 統計WEB
こちらの解説も併用すると良い。
目安勉強時間：20時間程度
