AHC047振り返り

はじめに

トヨタ自動車プログラミングコンテスト(AtCoder Heuristic Contest 047)に参加した。順位としては400番台で大したことなかったが、反省も含めて振り返る。

問題

問題には Lovely Language ModelというLLMをもじったタイトルがつけられている。内容としては、Lovelyな文字列を生成するマルコフ遷移モデルを作成するという問題。各文字列$S_i$には点数$P_i$が定義されており、$L = 10^6$以内に1度でもLovelyな文字列を生成できればその点数を得ることができる。実際のスコア計算は、確率から求められる期待値となる。

解いてみる

焼きなましで解けるのは予想がついたが、スコアの近似値の求め方がわからなかった。これは、コンテスト後に他の人のコードを読んで理解したので後述する。コンテスト内で考えた解放について記述する。

まず、状態としては$M = 12$個で固定されている。それぞれの状態が出力する文字1つに対応する。出力する文字はaからfの6個なので、1文字につき2状態が割り当てられる。そこで以下のようにした。
aを表示する状態$a_0$, $a_1$について、$a_0$の次はa,b,cのどれか、$a_1$の次はそれ以外の状態に遷移することした。つまり、次の文字がaa,ab,acのどれかなら$a_0$へ、ad,ae,afのどれかなら$a_1$に遷移することとした。

実際の動作としては、aからfを0から5の数字だとみなして、例えば$S_i$の文字列において、eを出力する状態が$x, x+1$の2つ、次の文字がabの場合、$A_{x,0}$と$A_{x + 1,0}に点数$P_i$を加算して、確率に正規化して出力するようにした。この場合、文字列最後の文字が「次」や「次の次」の文字列が見つからないという問題があるので、全部の文字列を繋げて1つの文字列だとすることで解決した。イメージ的は、lovelyな文字列を順番に全部出力できれば満点がとれるだろうという考えから。

「順番に全部出力」と言っているわりには、出力される文字列に偏りがある。これは、スコアが高い文字列の生成確率を上げた方がトータルのスコアが高くなったためで、上記で点数$P_i$を加算している部分を、最終的にはその二乗$P_i^2$を加算するようにした。

スコアの推定

時間内ではスコアの推定ができなかったので、焼きなましはできなかった。コンテスト終了後、他の人のコードを読んでいると、定常状態を使ってスコアを求めていたので、それを実装してみる。Heuristic ContestはPythonを使っているので、行列演算ライブラリとしてはnumpyを使う。

import numpy as np

まず、時刻$t$において状態$i$にいる確率を$p_i(t)$, 状態$i$から状態$j$に遷移する確率を$a_{i,j}$とすると、 時刻$t+1$に各状態にいる確率は以下のように示せる。

$$\begin{pmatrix} p_0^{(t + 1)}\\ p_1^{(t + 1)}\\ \vdots\\ p_{M-1}^{(t + 1)}\\ \end{pmatrix} = \begin{pmatrix} a_{0,0} & a_{1, 0} & \dots & a_{M-1,0} \\ a_{0,1} & a_{1, 1} & \dots & a_{M-1,1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{0,M-1} & a_{1, M-1} & \dots & a_{M-1,0} \\ \end{pmatrix} \begin{pmatrix} p_0^{t}\\ p_1^{t}\\ \vdots\\ p_{M-1}^{t}\\ \end{pmatrix}$$

これを以下のように記述するとする

$$\varphi^{(t + 1)} = A \varphi^t$$

この時、定常状態（$t\rightarrow\infty$）を考えると

$$\varphi^\infty = A \varphi^\infty$$

なので、

$$\tag{1} \left( A - I_M \right) \varphi^\infty = \mathit{O}$$

ここまでをpythonで書いてみると以下のような感じ。

    a = (np.array(original_a) / 100.0).T
    ai = a - np.identity(M)
    b = np.zeros(M, dtype=float)

あとはこれを多項式だと考えて

$$\tag{2} \sum_M p^\infty_i = 1$$

の条件下で解くのだが、linalg.solveは正方形の行列にしか対応していないので、1行足すわけにはいかない。ただ、式(1)は以下が成り立っているので、すべての多項式が完全に独立ではなく、1つ無くても問題はない...というかこれでは解がでない。

$$\sum_{j = 0..M-1} a_{i, j} = 1$$

そこで、一番上の行を式(2)に置き換えて解く。

    ai[0, :] = 1.
    b[0] = 1.
    phi = np.linalg.solve(ai, b)

これで、各状態の定常状態での発生確率がでてくる。
ここから各文字列が生成される確率を求める。ここで、各文字が生成される文字列だけをフィルタリングする行列$F(c)$を用意する。例えば状態0と1でaを出力する時、

$$F(\textrm{'a'}) = (1, 1, 0, 0, \dots, 0)$$

とする。こうしておくと、各要素の積（アマダール積と呼ぶらしい）を求めることで、特定の文字列を出力する状態をフィルタリングできる。 あとは、$L$文字の中で最低1回発生する確率を求める、つまり、$L$文字の中で1回も発生しない確率を1から引く。

    for text, score in lovely_text:
        p:np.array = phi * char_filter[text[0]]
        for i in range(1, len(text)):
            p = np.matmul(a, p) * char_filter[text[i]]
        prob:float = min(1., max(0., p.sum().item()))
        prob = min(1., max(0., 1 - (1 - prob) ** (L - len(text))))
        result += prob * score

これでスコアの近似値を求めることができるが、実際にこのままだと発生確率が低い文字列が改善してもスコアに反映されないなどの問題があるので、確率 prob を $r (< 0)$乗したものを使うなどといった処理が必要となる。

おわりに

スコアの近似式を使うと22位ぐらいのスコアをだすことはできた。

結局知識が不足していただけかなぁという気はする。ただ、解説記事を読んでいると「AHC044でもマルコフ遷移を扱ったので」と書いてあった。学びの機会を逃していたという反省と、あれってマルコフで解けるんだという発見が同時にあった。今度044をマルコフ遷移の定常状態で解いてみたいと思う。