けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

ダブルカウントを防ぐ場合分けのテクニック

AtCoder AGC 049 D - Convex Sequence (橙色, 1000 点)

最初は二次元 FFT が必要な気分になっていて右往左往していた。個数制限なしナップサック問題になるのは面白かった! 問題へのリンク 問題概要 正の整数 が与えられる。長さ の非負整数列 であって という条件を満たすものの個数を、1000000007 で割ったあま…

AtCoder AGC 045 C - Range Set (橙色, 800 点)

面白かった!! 問題へのリンク 問題概要 すぬけくんは長さ の文字列 を持っている。最初、 のすべての文字は 0 である。 すぬけくんは,以下の 2 種類の操作を好きな順序で好きな回数行うことができます. の連続する 文字を選んで,それらをすべて 0 にす…

AtCoder ABC 163 D - Sum of Large Numbers (緑色, 400 点)

「作れる数が連続する整数になる」というの、実は結構よくある!! 問題へのリンク 問題概要 個の整数 がある。 これらから 個以上の整数を選んで合計して得られる整数としてありうるものの個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこと まず…

AtCoder ABC 042 D - いろはちゃんとマス目 (ARC 058 D) (青色, 400 点)

これが青パフォ!!!!! 時代の進化を感じるところ!!! 問題へのリンク 問題概要 のマス目が与えられる。左上から右下へ進む最短経路のうち、 下から マス以内、かつ 左から マス以内 の範囲内には来ないようなものの個数を、1000000007 で割ったあまり…

フォルシアゆるふわ競プロオンサイト #3 F - Yet Another Cake Division locked

面白かった 問題へのリンク 問題概要 の盤面の各マスを T, M, N, P の四色に塗る方法のうち、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 どの T マスと M マスについても、M マスは T マスから見て strict に右にあるか、s…

キーエンス プログラミング コンテスト 2020 F - Monochromization (銅色, 1100 点)

「操作によって出来上がるものが何通りあるか?」という問題では、まず判定問題を考える!(素振り) 問題へのリンク 問題概要 のグリッドがあって、各マスは白または黒に塗られている。以下の操作を好きな順序で好きな回数だけ行った結果得られる盤面が何通り…

AtCoder ABC 130 E - Common Subsequence (青色, 500 点)

共通部分列に関する問題!!!!! 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…

AtCoder ARC 062 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer (橙色, 900 点)

大変だった ^^; 問題へのリンク 問題概要 全部で 色の色がある。 下図のような 枚の正方形があって、それぞれ のラベルがついていて、各正方形の四隅にはいずれかの色が塗られている。 枚の中から 6 枚を選んで立方体を作る。ただしどの頂点についても、そこ…

AtCoder AGC 001 E - BBQ Hard (1400 点)

当時は解けなかったけど、二項係数を扱うスキルを格段に高めた今なら解ける!!! というのは罠で、「経路数に帰着する」という考え方をこの問題で学んだ ^^; 問題へのリンク 問題概要 個の正の整数値のペア が与えられる。 の値を 109 + 7 で割ったあまりを…

AtCoder AGC 002 F - Leftmost Ball (銅色, 1600 点)

すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…

Tenka1 2019 F - Banned X (赤色, 800 点)

かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…

Tenka1 2019 D - Three Colors (黄色, 600 点)

お 見た目とても面白そう 問題へのリンク 問題概要 要素からなる数列 があたえられる。各要素を「赤」「緑」「青」の三色のいずれかに塗る方法のうち、各色の合計値を として三辺の長さが となるような三角形が存在するようなものを数え上げよ。998244353 で…

AtCoder AGC 031 B - Reversi (水色, 700 点)

これは安定感のある思考過程を経て解けた気がするので共有したい気持ち!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。各 は 以上 以下の整数値である。今、以下のような操作を何回でも行うことができる: となるような < を選んで、 と との間の…

全国統一プログラミング王決定戦 本選 E - Erasure (700 点)

700 点は絶対落とさないのん!!! 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間がある。 これ…

AOJ 2895 回文部分列 (AUPC 2018 day3 G)

すごく大好きな問題! 部分列を走査する考え方をちゃんとわかっていれば自然に解くことができる。 問題へのリンク 問題概要 文字列 が与えられる。 の部分文字列のうち回文となっているものが何通りあるか、1000000007 で割ったあまりで求めよ。 制約 は英小…

AtCoder AGC 027 E - ABBreviate (銀色, 1300 点)

2 日目:AGC 027 E - ABBreviate (1300 点)https://t.co/mvWcvtxfRz3 で割った余りについて不変量であることは既出。重複を除くために「文字列の部分文字列の数え上げ」的な考え方をするのも恐らく典型。自力で詰め切るのはまだ辛いけど「赤くならないうちは…