drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AOJ HUPC 数え上げ問題 操作によって作れるものの集合を考える(判定関数を考える) 操作 操作後の結果の数え上げ 区間 区間ソート Greedy DP 移動可能区間を遷移していく シーケンシャルDP 座標圧縮 最適化の考察：探索候補を絞る 最適化の考察：端点のみを考える DP状態空間を絞る 比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 個の指示が与えられます。 個目の指示は、「時刻 には を満たす座標 にいなければならない」という指示です。 個の指示の空でない部分集合 が「適切」であるとは、umgくんが上手く動くことで、 に含まれるすべての指示に従うことができることをいいます。適切である指示の集合としてあり得るものの個数を 998244353 で割った余りを求めてく… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F09%2F17%2F031200" title="AOJ 3181 Proper Instructions (HUPC 2020 day3-J) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-09-17 03:12:00 rich https://drken1215.hatenablog.com/entry/2020/09/17/031200 1.0 100%