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

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

DP状態:フェーズ(耳DP)

AtCoder ABC 325 E - Our clients, please wait a moment (緑色, 450 点)

少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題! 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…

AtCoder ABC 259 Ex - Yet Another Path Counting (橙色, 600 点)

opt さんとのスペースで解いた! いくつか典型を見落としていたのでメモ!! 問題へのリンク 問題概要 のグリッドがあって、マス には値 が記されている。 いずれかのマスから始めて右または下に隣接するマスへの移動を 0 回以上繰り返すことで得られる経路…

AtCoder ABC 159 F - Knapsack for All Segments (青色, 600 点)

ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…

みんなのプロコン 2019 D - Ears (青色, 600 点)

郡山駅のベンチで寒さに震えながらやる問題ではなかった...必要以上に複雑にしてしまった。。。 問題へのリンク 問題概要 すぬけさんが、座標 0 と との間を行ったり来たりする。行って方向転換できる場所は整数座標のみである。 このとき、各区間 [ ] () に…

AtCoder ABC 104 D - We Love ABC (青色, 400 点)

これ好き!!! 問題へのリンク 問題概要 "BCABBACCBCCACA" のような A, B, C のみからなる文字列 S の「ABC 数」とは、 S[i] = 'A' S[j] = 'B' S[k] = 'C' i < j < k を満たすような (I, j, k) の組の個数のことである。今、 ????C?????B??????A??????? の…

AtCoder ABC 098 C - Attention (ARC 098 C) (茶色, 300 点)

累積和の典型問題 問題へのリンク 問題概要 WWEWEEWWEE のような文字列が与えられる。 文字列のうちの 1 つの文字を選んで、その左側をすべて E に、右側をすべて W にするのに必要な変更量の最小値を求めよ。 制約 解法 累積和を用いる。 #include <iostream> #includ</iostream>…

競プロ典型 90 問 008 - AtCounter(2Q, ★4)

これまたすごく典型的な DP!!! 「状態遷移」を意識して取り扱う DP。ごく一部の界隈では耳 DP と呼ばれていたりもするかもしれない。 問題へのリンク editorial この問題の前提知識 ナップサック問題を解く DP が自力で書けること 1000000007 で割ったあ…