TERRYのブログ

最近は競技プログラミングにお熱。

トップ > AtCoder > トヨタ自動車プログラミングコンテスト2025#2 (AHC047) 解説

トヨタ自動車プログラミングコンテスト2025#2 (AHC047) 解説

AtCoder 競プロ マラソン

AtCoder Heuristic Contest 047お疲れ様でした。6,924,133点で5位です。1桁順位が取れて満足です。

あまり自分と同じ解法の人がいなさそうだったので、今回も軽めに解説記事を書いていきます。

ビジュアライザ (seed=0, score=48,728点)

問題概要

ロボてりーを調教してね。

欲しい単語が出てくるようなマルコフ連鎖モデルを作ってね。

atcoder.jp

解法

概要

C は aabbccddeeff で固定で、 A を求めました。

大まかな解法の流れはこんな感じです。

  1. 貪欲で初期解作成
  2. 貪欲で P_i の大きい順に S_i を追加し、追加した単語が全て50%以上生き残るような A を都度焼きなましで求める
  3. 近似スコアで焼きなまし

お気持ち

焼きなましをしたいのですが、一度ある文字列の出現確率がほぼ0になってしまうと、そこから復活させるのは至難の業です。

下の表は縦を S_{i,j} から S_{i,j+1} への遷移確率、横を S_i の長さとしたときの「1回以上出現する確率（左）」と「出現数の期待値（右）」なのですが、出現確率はかなり狭い範囲で立ち上がっていて、ほとんどの場所で確率が平坦になっていることが分かります。これだと焼きなましで解を変更しても評価値がほとんど変わらず、良い解に持って行きづらいです。

これを解消するためには、「初期解を頑張る」「近傍を頑張る」「評価関数を頑張る」あたりのアプローチがあると思いますが、今回は初期解を頑張ることにしました。

文字列生存確率

初期解作成

A の初期解を作ります。強い文字が残るようにしたいので、 P_i^2 で重み付けして遷移確率を決めます。

具体的にはこんな感じで作ります。

  1. 6\times 6 の行列 E を用意する
  2. 各 (S_{i, j}, S_{i, j+1}) の組について、 E_{S_{i, j}, S_{i,j+1}} に P_i^2 を足していく*1
  3. 出来上がった行列 E を 12\times 12 に拡張して、いい感じに百分率で丸めて A とする

貪欲

この解の肝になる部分です。

先ほど書いたとおり、文字列の出現確率が0%になると復活が絶望的なので、採用したい文字列番号の集合 X を考え、 P_i の大きい順に文字列番号を X に追加しつつ、X に含まれる各 i について S_i がそれぞれ50%以上の確率で出現するような A を求めていきます。

まず、 A が決まったときの文字列 S_i の出現確率を近似します。十分長い文字列を生成するとマルコフ連鎖が定常分布となるので、文字列のある場所をS_i の1文字目としてそこから S_i の生成に成功する確率を p_i とすると、長さ L の文字列に S_i が1個以上含まれる確率 P_i は、 P_i\approx 1-(1-p_i)^L と近似できます。*2 *3

この出現確率 P_i が閾値 T 以上になってほしいです。つまり i 番目の文字列について、 1-(1-p_i)^L\ge T を要求したいです。ここで P_i は指数関数的に小さくなって焼きなましで扱いづらいので、両辺の対数を取って \log(1-(1-p_i)^L))\ge \log T を要求することにしましょう。*4

この要求に対する違反量 e(A) は、 e(A) = \max(\log T-\log(1-(1-p_i)^L),0) となります。これを現在対象としている文字列番号の集合 X に対して足し合わせて、焼きなましの評価関数 f(A) をf(A)=\sum_{i\in X}\max(\log T-\log(1-(1-p_i)^L),0) としましょう。 A をこの評価関数のもとで焼きなましで最小化し、その結果 f(A)=0 となれば X に含まれる全ての i について文字列 S_i の出現確率が T 以上となることが達成されることになります。

近傍はあまり工夫していないですが、以下の2つを使っています。

A[i][j] -= 1
A[i][k] += 1

A[i][k] -= 1
A[i][l] += 1
A[j][k] += 1
A[j][l] -= 1

この焼きなましを使って、以下の貪欲を行います。

  1. S_i を P_i の降順に並べる
  2. 遷移行列 A を上記の初期解で、文字列番号の集合 X を空集合で初期化する
  3. X に i を追加したものを X' とする
  4. 焼きなましを行った結果得られた遷移行列を A' として、 f(A')=0 となっているか確認する
  5. f(A')=0 なら成功で、 A を A' で、 X を X' で置き換える。そうでなければ置き換えない
  6. 3.～5. を繰り返す

この貪欲を行うと、 P_i の大きい文字列がいくつか50%ずつくらい残ります。ビジュアライザはこんな感じです。

貪欲完了時の状態

焼きなまし

普通に焼きなまします。上記の焼きなましにおいて、評価関数を実スコア \sum_{i=0} ^{N-1} P_i\cdot Q_i\approx \sum_{i=0}^{N-1} (1-(1-p_i)^L)\cdot Q_i にしただけです。

スコアがかなりブレるので、2回実行して良い方を出力しました。

本番中に提出したコードはこちらです。ちょっと細かい工夫を入れていたり、なぜか貪欲パートの焼きなましで確率ではなく期待値を使ってたりします（なんで？）。

atcoder.jp

ビジュアライザアニメーション

余談

これは完全に余談なのですが、ロボてりーも原理としては同じ仕組みで動いています。

今回の問題設定との違いは以下の2点だけです。

  • 各状態を文字ではなく、直近2トークンまたは3トークンの組にしている
  • 始点ノードと終点ノードがあり、始点ノードから遷移を始めて、終点ノードに達したら生成完了とする

感想

自然な問題設定にもかかわらず、評価関数の近似・焼きなましの工夫など考えるべき点が多く面白い問題でした。問題の特性を考えて自分なりの工夫ができたのは良い立ち回りだったかなと思います。

個人成績としては昨年11月のAHC039から8回連続で1ページ目に入れていて、安定感が出ていてかなりいい感じです。GP30も現在5位に入れており、今後もこの調子を維持していきたいですね。

*1:aを0, bを1, ..., fを5と読み替えます。

*2:余事象を2回使っています。

*3:p_i は、定常分布を求めた上でDPをすると求めることができます。詳細はAHCラジオをご覧ください。

*4:解説はこう書いてますが、本番中はなぜか期待値で考えていました。まあそんなに大きく外しはしないのですが、なぜ……。