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

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

ダブルカウントを除く

AtCoder ABC 130 E - Common Subsequence (500 点)

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

AtCoder AGC 001 E - BBQ Hard (1400 点)

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