mod7占い (paizaランク S 相当)

自己紹介

大阪大学2回生で競技プログラミング部rainbou副部長、Atcoder緑
X:https://x.com/e4h99rhQ7I24670

問題文URL

解説

この問題はぱっとみ、かなり難しい問題のように見えます。
この問題ではDPという考え方を使うのですが、慣れていないとおそらく解けなかったと思います。
さすがはSランク問題といった感じです。（笑）
Atcoderで出題されればおそらくdiff800程度でしょう。

先ほども触れましたようにこの問題はDPを使います。
N<=10^5である点からもDPとぱっと思いつくことは難しくないと思います。（DP解きなれてくればなんとなく問題文から雰囲気を察すれるようになれます。）

今回はDP[i][j][k]<-i番目の数のみでj枚使ってKmod７を作れる個数でDPします。
遷移としては

DP[i+1][j][k] += dp[i][j][k]
DP[i+1][j+1][(k+a)%7] += dp[i][j][k](if j != 2)
ans += DP[i][j][k](if j == 2 and (k+a) % 7 == 0)

です

あとはこれを実装に落とし込むだけです。

N = int(input())
dp = [[[0]*7 for _ in range(3)] for _ in range(N+1)]
dp[0][0][0] = 1

ans = 0
for i in range(N):
    a = int(input()) % 7
    for j in range(3):
        for k in range(7):
            dp[i+1][j][k] += dp[i][j][k]
            if j != 2:
                dp[i+1][j+1][(k+a) % 7] += dp[i][j][k]
            elif j == 2 and (k+a)%7 == 0:
                ans += dp[i][j][k]

print(ans)

modをとらなくてもいいというのはどこか気持ち悪いですね。ｗ