drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ Codeforces EducationalCodeforces in-place DP DP 区間 区間ソート DP高速化 DP高速化:累積和 データ構造テク：前処理 各桁ごとに見る 考察：独立に考える 区間の交差 テク:区間の交差関係や包含関係を除去できる 0と1の問題 数え上げ問題 いもす法 DP状態:前回の最後の場所 単純化：操作の流れを単純化して考える CodeforcesR2500 DP高速化:セグメント木 DP高速化:セグメント木上のin-placeDP 場合分け：2点や2区間の配置関係を考える そのまま覚えたいシンプル設定の中堅以上の典型問題 グラフ・盤面・数列の個数の数え上げ N個の区間の問題 実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を満たすものの個数を 998244353 で割ったあまりを求めよ。 各条件は区間と値が指定される 数列の区間の AND をとった値が、指定された値に一致する 制約 考えたこと すっごく典型色強めで面白そう！！！ こういうのはとりあえず区間が交差しているところについて考えないといけなくて、ひとまず 区間が交差しているところの条件の値が異なっているものに… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F03%2F27%2F040200" title="Educational Codeforces Round 84 F. AND Segments (R2500) - けんちょんの競プロ精進記録" 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/1687765056723440 Hatena Blog https://hatena.blog 2020-03-27 04:02:00 rich https://drken1215.hatenablog.com/entry/2020/03/27/040200 1.0 100%