結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
![]() |
提出日時 | 2025-04-19 18:56:01 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,642 bytes |
コンパイル時間 | 626 ms |
コンパイル使用メモリ | 82,968 KB |
実行使用メモリ | 107,568 KB |
最終ジャッジ日時 | 2025-04-19 18:56:14 |
合計ジャッジ時間 | 13,083 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 49 |
ソースコード
""" https://yukicoder.me/problems/no/3119 2増える or 1増える or 変化なし 増えるものはいくつあるか?を数え上げればいい? 2増える場合は A[i] < B[i+1] A[i+1] < B[i] A[i] >= B[i] A[i+1] >= B[i+1] これは存在しない 1増える場合 B[i] <= A[i] < B[i+1] <= A[i+1] OR B[i+1] <= A[i+1] < B[i] <= A[i] なら成立 dp[i][既にあるか?][ B[i-1]<A[i-1]か? ] でdpすれば行けそう? 2つ同時に決めないとダメかなぁ いや、増えないものを数え上げたほうがいい dp[i][次で違反の可能性があるか?] で良いのかなぁ 1 2 1 2,3,4 -> 違反できる """ mod = 998244353 N,M = map(int,input().split()) A = list(map(int,input().split())) # dp[0] = 次違反する可能性がない # dp[1] = 次違反する可能性がある i = 0 if A[i] < A[i+1]: dp = [ M-A[i] , A[i] ] elif A[i+1] < A[i]: dp = [ M-(A[i]-A[i+1]) , A[i]-A[i+1] ] else: dp = [ M , 0 ] print (dp) # 同じ値を置くことで、番兵とする A.append(A[-1]) for i in range(1,N): ndp = [0,0] # 違反の危険性がない場合、後ろだけを見て決められる if A[i] < A[i+1]: ndp[0] += (M-A[i]) * dp[0] ndp[1] += A[i] * dp[0] elif A[i+1] < A[i]: ndp[0] += (M-(A[i]-A[i+1])) * dp[0] ndp[1] += (A[i]-A[i+1]) * dp[0] else: ndp[0] += M * dp[0] # 違反の可能性がある場合は、大小関係で場合分け... if A[i-1] < A[i]: # A[i-1] < B[i] <= A[i] は設置禁止 if A[i] < A[i+1]: # A[i]より大きい位置に配置する場合 ndp[0] += ( M-A[i] ) * dp[1] # A[i-1]以下に設置する場合 ndp[1] += ( A[i-1] ) * dp[1] elif A[i] > A[i+1]: p1 = max(0, A[i-1]-A[i+1]) ndp[0] += ( M - (A[i]-A[i-1]) - p1 ) * dp[1] ndp[1] += p1 * dp[1] else: # A[i] == A[i+1] ndp[0] += ( M-(A[i]-A[i-1]) ) * dp[1] elif A[i-1] > A[i]: # B[i] <= A[i] が禁止 # A[i] < B[i] となるようにB[i]を決めることとなり # この時点ですでにB[i+1]をどう配置しても不等式条件を満たすことは無い ndp[0] += (M - A[i]) * dp[1] else: # dp[1] = 0のはずなので pass dp = [x % mod for x in ndp] print (dp) # 動かさない場合のスコア X = pow(M,N-1,mod) base = 0 for i in range(N): base += (M-A[i]) * X base %= mod print (base , pow(M,N,mod) ,- dp[0]) ans = (base + pow(M,N,mod) - dp[0]) % mod print (ans)