AtCoder AGC 031 参戦記

今回コンテスト中に700点問題が初めて解けて、AB2完でした。が、何と水色パフォーマンスでレートが落ちました。厳しい。

解説書く時間が無いので提出コードとコメントだけ。

A問題 (Colorful Subsequence)

N = int(input())
S = input()
mod = 7 + 10 ** 9
 
word = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m"\
    ,"n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y","z"]
count = [1] * 26
for i in range(N):
    count[word.index(S[i])] += 1
Total = 1
for c in count:
    Total *= c
    Total %= mod
print(Total - 1)

誤読に気を付けましょう。同じ文字でも場所で区別するので、各文字の数を数えて文字数+1を答えにかけていきます。

B問題 (Reversi)

N = int(input())
C = [int(input())]
cindex = {C[0]: 0}
mod = 7 + 10 ** 9
counter = 0
for _ in range(N-1):
    c = int(input())
    if c != C[-1]:
        C.append(c)
        counter += 1
        if c not in cindex:
            cindex[c] = counter
 
DP = [[0, 1] for i in range(len(C))]
for i in range(1, len(C)):
    if cindex[C[i]] == i:
        DP[i][1] = DP[i-1][1]
    else:
        DP[i][0] = DP[cindex[C[i]]][1] 
        DP[i][1] = DP[i][0] + DP[i-1][1]
        DP[i][1] %= mod
        cindex[C[i]] = i
print(DP[-1][1])

いろいろ実験すると同じ色が連続する場所は圧縮できることがわかります。圧縮した後は挟める区間を独立に見てDPします。10^9+7で割るのを忘れないようにしましょう。

これ1000人近く解けてるのきつい。