【今日の精進】ABC279G - At Most 2 Colors

毎日格上の問題を倒すやつの51日目です。*1

問題リンク

atcoder.jp

問題概要

マス横に並んだものを、「隣り合う マスにはたかだか2色しか表れない」という条件を満たして マスで塗る方法を数え上げてね。

解法

• 番目と 番目の色が異なる塗り方

ってだけでDPはできるのでこれで終わりですが、あえてFPSにこじつけたいです。

うまく式変形して実装例のようにすると正しいDPになるのですが、これの一般項はBostan-Moriで求められます。

しかし、NTTなどの定数倍がきつかったりそもそも制約が大きかったりで応用できるかは怪しいところです。

例えば という制約なら解けます。

というわけでBostan-Moriが万能じゃないというお話でした。

提出コード

from collections import defaultdict

MOD=998244353
N,K,C=map(int,input().split())
dp=defaultdict(int)
dp[1]=(C*(C-1))%MOD
for i in range(1,N):
    dp[i]+=dp[i-1]*3-dp[i-2]*2+dp[i-(K-1)]*(C-2)-dp[i-K]*(C-2)
    dp[i]%=MOD
print((dp[N-1]+C)%MOD)

Submission #47418092 - TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279)

感想

締めに相応しくなさすぎないか？

宣伝

https://kenkoooo.com/atcoder/#/contest/show/172ff02f-aef7-48c8-8f65-0de9b8643797kenkoooo.com

春合宿バチャするからきてね*2

*1:FPSウィークの最終日ですが、締めにふさわしいことはできません

*2:コドフォは流石におやすみかなぁ