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

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

EDPCとTDPC

AtCoder EDPC W - Intervals

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね!!! 一部の競プロ界隈では、俗に実家 DP などと呼ばれてたりしていたものです。 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列を 0-1 文字列と呼ぶことにしま…

AtCoder EDPC Q - Flowers

まさに重み付き LIS ともいうべき問題ですね。 問題へのリンク 問題概要 本の花が横一列に並んでいます。 左から 番目の花の高さは で、美しさは です。 太郎君は何本かの花を抜き去ることで、次の条件が成り立つようにしようとしています。 「残った花を左…

AtCoder TDPC G - 辞書順

いわゆる部分列を扱う DP ですね。経路復元も含んでいて少し難しい問題です。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられます。 の部分列 (連続でなくてもよい) として考えられる文字列をすべて考えたとき、その中で辞書順で 番…

AtCoder TDPC A - コンテスト

部分和問題とほとんど一緒なのだけど、意外と詰まるかもしれない。 問題へのリンク 問題概要 個の正の整数 の中からいくつか選んで総和をとる。作ることのできる整数が何通りあるか求めよ。 制約 考えたこと この問題とよく似た部分和問題とは次のような問題…

AtCoder EDPC Y - Grid 2

座圧に見えてしまった 問題へのリンク 問題概要 のグリッドがあります。グリッドのうち マスに壁があって壁の位置は で与えられます。壁のあるマスには行けません。 マス からマス へと至る最短経路が何通りあるか、 で割ったあまりを求めよ。 制約 考えたこ…