Branched Evolution

Competitive Programming in Python

Introduction to Heuristics Contest

問題

26種類のコンテストを365日間にわたって1日1種類ずつ開催する。$i$ 日目にコンテスト $j$ を開催したとき $S _ {ij}$ の満足度を得て、コンテスト $j$ を開催しなければ $C _ {j} \times (i - L _ {ij})$ の満足度を失う。ただし、$L _ {ij}$ は $i$ 日目までに $j$ を最後に開催した日とする。このとき、最終的な満足度をできるだけ大きくするような開催スケジュールを求めたい。($C _ {j} \leq 100, S _ {ij} \leq 20000$)

atcoder.jp

日ごとの評価関数

状態 $X \in \{ 0, \ldots , 25 \} ^ {365}$ に対して $L _ {ij} (X)$ を $i ' \leq i$ かつ $X _ {i '} = j$ なる最大の $i '$ (存在しない場合は $-1$) とすると、$i$ ごとに評価関数は $$ S _ {i X _ {i}} - \sum _{j = 0} ^ {25} C _ {j} (i - L _ {ij}(X)) $$ すつ増えることがわかる。これが正しいことはB問題に提出することで確認できる。

atcoder.jp

実装例

d = int(input())
*C, = map(int, input().split())
S = [list(map(int, input().split())) for i in range(d)]
X = [int(input()) - 1 for i in range(d)]
L = [-1 for j in range(26)]
score = 0
for i in range(d):
    L[X[i]] = i
    score += S[i][X[i]]
    score -= sum([C[j] * (i - L[j]) for j in range(26)])
    print(score)

貪欲法

各 $i$ ごとに、評価関数の増加が一番大きい $j$ を $X _ i$ として採用する。

実装例 (62634806点)

d = int(input())
*C, = map(int, input().split())
S = [list(map(int, input().split())) for i in range(d)]
X = []
L = [-1 for j in range(26)]
for i in range(d):
    max_diff = -10**10
    best_j = 0
    for j in range(26):
        memo = L[j]
        L[j] = i
        diff = S[i][j] - sum([C[jj] * (i - L[jj]) for jj in range(26)])
        if diff > max_diff:
            max_diff = diff
            best_j = j
        L[j] = memo
    L[best_j] = i
    X.append(best_j)
for x in X:
    print(x + 1)

評価関数の高速化

評価関数をこのまま実装すると $365 \times 26$ 回の計算が必要だが

$$ \begin{aligned} f(X) & = \sum _ {i = 0} ^ {364} \left( S _ {i X _ {i}} - \sum _ {j = 0} ^ {25} C _ {j} (i - L _ {ij}(X) ) \right) \\ & = \sum _ {i = 0} ^ {364} S _ {i X _ {i}} - \sum _ {j = 0} ^ {25} C _ {j} A _ {j}(X) \end{aligned} $$

と変形することで $365 + 26$ 回の計算でできる。
ただし、$A _ {j}(X) = \displaystyle\sum _{i=0} ^ {364} (i - L _ {ij}(X))$ であり、$ \displaystyle\sum _ {i = 0} ^ {364} S _ {i X _ {i}} $ の部分と同時に計算できる。これが正しいことはC問題に提出することで確認できる。

atcoder.jp

実装例

d = int(input())
*C, = map(int, input().split())
S = [list(map(int, input().split())) for i in range(d)]

def f(X):
    score = 0
    L = [-1 for j in range(26)]
    A = [0 for j in range(26)]
    for i in range(d):
        score += S[i][X[i]]
        A[X[i]] += (i - L[X[i]]) * (i - L[X[i]] - 1) // 2
        L[X[i]] = i
    for j in range(26):
        A[j] += (d - L[j]) * (d - L[j] - 1) // 2
        score -= C[j] * A[j]
    return score

X = [int(input()) - 1 for i in range(d)]
m = int(input())
for k in range(m):
    i, j = map(lambda x: int(x) - 1, input().split())
    X[i] = j
    print(f(X))

局所探索

貪欲法による解を初期解として、そこからランダムに少しだけ動かしてスコアが上がっていればそれを次の解とする、という操作を制限時間いっぱいまで繰り返す。

ここでは「1点更新」と「2点交換」の2通りの動かし方を考え、交互に使っている。 「1点更新」では $i$ と $j$ をランダムに選び、$X _ i$ を $j$ に更新する。 「2点交換」では $i$ と $a$ をランダムに選び、$X _ {i}$ と $X _ {i + a}$ を交換する。

実装例 (114960563点)

from random import choice
from time import time
start_time = time()

# ~中略~

max_score = f(X)
while time() - start_time < 1.8:
    i = choice(range(d))
    j = choice(range(26))
    memo = X[i]
    X[i] = j
    score = f(X)
    if score > max_score:
        max_score = score
    else:
        X[i] = memo
    a = choice(range(7))
    i0 = choice(range(d - a))
    i1 = i0 + a
    memo = X[i0], X[i1]
    X[i0], X[i1] = X[i1], X[i0]
    score = f(X)
    if score > max_score:
        max_score = score
    else:
        X[i0], X[i1] = memo
for x in X:
    print(x + 1)

焼きなまし法

焼きなまし法についてはこちらの記事がわかりやすい。

gasin.hatenadiary.jp

ここでは 時刻 $t \in [0,1]$ における温度を $T(t) = 2000 ^ {1 - t}$ とし、時刻 $t$ における$X$ から $X'$ への遷移確率を $$ \min \left\{1, \exp{\left(\frac{f(X') - f(X)}{T(t)} \right) } \right\} $$ とした。

実装例 (116357321点)

from random import choice
from random import random
from time import time
start_time = time()

# ~中略~

max_score = f(X)
while time() - start_time < 1.8:
    t = (time() - start_time) / 2
    i = choice(range(d))
    j = choice(range(26))
    memo = X[i]
    X[i] = j
    score = f(X)
    if score > max_score:
        max_score = score
    elif random() < pow(2.7, (score - max_score) / pow(2000, 1 - t)):
        max_score = score
    else:
        X[i] = memo
    a = choice(range(7))
    i0 = choice(range(d - a))
    i1 = i0 + a
    memo = X[i0], X[i1]
    X[i0], X[i1] = X[i1], X[i0]
    score = f(X)
    if score > max_score:
        max_score = score
    elif random() < pow(2.7, (score - max_score) / pow(2000, 1 - t)):
        max_score = score
    else:
        X[i0], X[i1] = memo
for x in X:
    print(x + 1)