【今日の精進】ABC227E - Swap

毎日格上の問題を倒すやつの7日目です。

無事一週間続いたことに驚いております。

問題リンク

atcoder.jp

問題概要

K,E,Yのみからなる文字列が与えられるよ。

「隣り合う文字を入れ替える」ことを 回まですることで作れる文字列の個数を答えてね。

解法

まあ、明らかに という制約を使いたいですね。

作れる文字列を考察してみると、転倒数的なものが 以下なら作れることがわかります。¹

なので、以下のようなDPを考えます。

これを適切に累積和をとるなどして丁寧に実装すればACできます。²

計算量はたぶん5乗オーダーくらいで、定数倍も軽そうなので間に合います。³

提出コード

S=input()
N=len(S)
K=int(input())
cnt=[[0 for i in range(N+1)] for i in range(3)]
pos=[[] for i in range(3)]
for i in range(N):
    if S[i]=="K":
        pos[0].append(i)
    if S[i]=="E":
        pos[1].append(i)
    if S[i]=="Y":
        pos[2].append(i)
    cnt[0][i+1]=cnt[0][i]+(S[i]=="K")
    cnt[1][i+1]=cnt[1][i]+(S[i]=="E")
    cnt[2][i+1]=cnt[2][i]+(S[i]=="Y")
DP=[[[[0 for i in range(N*N)] for i in range(cnt[1][-1]+1)] for i in range(cnt[0][-1]+1)] for i in range(N+1)]
DP[0][0][0][0]=1
for i in range(N):
    for j in range(cnt[0][-1]+1):
        for k in range(cnt[1][-1]+1):
            for l in range(N*N):
                if DP[i][j][k][l]==0:
                    continue
                m=i-j-k
                if j<cnt[0][-1]:
                    DP[i+1][j+1][k][l+max(0,k-cnt[1][pos[0][j]])+max(0,m-cnt[2][pos[0][j]])]+=DP[i][j][k][l]
                if k<cnt[1][-1]:
                    DP[i+1][j][k+1][l+max(0,j-cnt[0][pos[1][k]])+max(0,m-cnt[2][pos[1][k]])]+=DP[i][j][k][l]
                if m<cnt[2][-1]:
                    DP[i+1][j][k][l+max(0,j-cnt[0][pos[2][m]])+max(0,k-cnt[1][pos[2][m]])]+=DP[i][j][k][l]
ans=0
for i in range(min(K+1,N*N)):
    ans+=DP[-1][-1][-1][i]
print(ans)

Submission #45976696 - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)

感想

一歩踏み間違えれば橙Diffになる問題の難易度ではないでしょこれ⁴

---

1. バブルソート的な↩
2. 丁寧に(説明は雑)↩
3. 未証明です(え？)↩
4. どっちの意味なんでしょう？↩