@morio_progの精進日記

解いた競プロの問題をつらつらと。(AtCoder: morio__)

DP

【ABC041】D - 徒競走

問題概要 匹のうさぎがいる. 人の観客から, うさぎがうさぎよりも先にゴールしたという情報を得た. これら全ての情報に合致する着順が何通りあるかを求めよ. 制約 考察 bitDPをする. dp[何匹見たか][状態]としたとき, 各うさぎがすでにゴールしたかをbitの状…

【Educational Codeforces】D - Bicolorings【Round 51】

問題概要 2列n行のマス目を白黒に塗り分ける。塗り分けた後、区画がk個できるような塗り分け方の数を求めよ。結果はかなり大きい数になるため、998244353で割ったあまりを出力せよ。 制約 1 <= n <= 1000 1 <= k <= 2n 考察 ぱっと見DPっぽいのでDPをする。 …