[Python] AHC048振り返り
[Python] AHC048 Mixing on the Palette
問題
最終結果
miso253oudonさんのMC Digital プログラミングコンテスト2025（AtCoder Heuristic Contest 048）での成績：556位
パフォーマンス：1293相当
レーティング：308→745 (+437) :)
Highestを更新し、7 級になりました！
#AtCoder #MCDigitalプログラミングコンテスト2025（AtCoderHeuristicContest048） https://atcoder.jp/users/miso253oudon/history/share/ahc048?lang=ja
最終提出ソース
ビジュアライザ
seed = 11
試したこと
初期
-
与えられた絵の具のうち、一番近い色を1色出して提出する
- ユークリッド距離の名前をしる
- 当初は普通に計算していたが、後々numpyでやった方が良いことを知り改善
- ユークリッド距離の名前をしる
-
2色以上を混ぜることを考える
- パレットの作り方を考える
- 当初は1×20で簡単に作っていた
- 1×2,2×4などを試して最終的には4×4に落ち着く
- 任意の2色を混合し、一番近い色をパレットに出して使う
- パレットの作り方を考える
中盤
-
空いているパレットの場所、色の管理を考える
- 色情報(tuple)をキーとしたdictでパレット上の場所、量を保持
- 空いている場所はsetで管理
- 絵の具を出す量が少ない方がいいので、できるだけ廃棄しないように空いている枠を優先して使うようにする
-
できるだけ絵の具を使う量を減らすことを考える
- 絵の具を混合した色の候補 or パレット上にある色で、誤差が少ない方を使うようにする
- 上下左右の枠の間の仕切りを開けたときにより誤差が小さくなるか検討する
-
コストの概念を考えようとするが、うまくいかなかったので一旦保留する
終盤
- 操作制限に掛からないように、少しずつ許容する誤差を縮めていく
- 操作可能回数が少ない場合にはパレット上の色と渡す色の誤差が大きくなることを許容する
- 時間いっぱい許容する誤差を広げて、スコア計算しつつ採用する
- 最後の数十色程度は絵の具を使い切ることを優先してみる
反省
-
スコア計算の勘違い
- 絵の具を出すコストについて、1000回までは無料であることをわかっていたのにソース上は全ての操作に対してコストを掛けてしまった
- (誤) コスト = 操作2の回数 * コスト + 誤差の合計
- (正) コスト = (操作2の回数 - 1000) * コスト + 誤差の合計
-
ローカル環境の整備不足
- 長期AHCは初参加。環境の準備不足が目立った。
- VSCode上で実装しているが、入出力が長いのでターミナル上では効率が悪すぎた
- 途中から
sys.stdin = io.StringIO(_INPUT)、with open("ans.txt", mode="a") as o:などを利用した - 複数の条件の出力を比べる方法がなかったので、ボトルネックが分かり辛い
- 途中から
- ローカルでは発生しないREが取れなかった
- 最終的にはtry-exceptで挟んで誤魔化してしまった
- 複数ケースを一気に試せるような環境が整っていれば、原因ケースの特定ができたかも
-
絶対スコアとか相対スコアとかで混乱していた
- 算数力の弱さが露呈した気がする
- 最終提出は絶対スコアが一番低く出たものにしたが、これが正しかったのか今でもよくわかっていない
感想
とりあえずわかるところから少しずつ問題を解いて行った。
途中で3次元上の一番近いところを使うといいんだろうなあという気持ちにはなれど、うまく処理する方法が思いつかず。
何パターンか処理方法を試す中で、それぞれの効果を定量的に比較することができなかったので、グラフにする、各処理の結果を表にする、何よりも複数パターンの(規模の大きい)入出力を気軽に試せる環境を事前に構築していく必要があることを痛感。
個人的にはアルゴリズムよりもスモールスタートしやすい、小さな改善でACを保ちつつ順位表に反映される…などヒューリスティックの方がモチベを保ちやすかった。
スコアの出易さもあるが、アルゴリズムよりも先に茶色になってしまったのでアルゴリズム側の勉強も続けていきたいと思います。
Discussion