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

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

2023-05-03

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

AtCoder AtCoder600点 ABC-Ex 橙色diff DP状態:フェーズ(耳DP) 始点と終点がともに動く経路を走査する解空間:O(N^2)通りの選択肢平方分割場合分け二次元グリッド多項式・FPS(形式的冪級数) DP グリッド上のDP

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

2020-03-22

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

AtCoder AtCoder600点 ABC-F 部分和 DP ナップサックDP 区間解空間:O(N^2)通りの選択肢主客転倒数え上げ問題 DP状態:フェーズ(耳DP) 青色diff DP状態:ナップサック始点と終点がともに動く経路を走査する

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

2019-02-10

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

区間 DP ナップサックDP パリティ AtCoder AtCoder600点条件の言い換え操作最小回数・最小個数を求める最小コスト DP状態:フェーズ(耳DP) 操作の流れを単純化する ARC-like 青色diff 最適化問題

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

2018-08-05

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

DP 数え上げ問題ナップサックDP 3つのものの真ん中に着目する ABC-D AtCoder400点 AtCoder DP状態:フェーズ(耳DP) ワイルドカード問題文字列青色diff 0と1と2の問題解空間:O(N^2)通りの選択肢 DP状態:照合文字列の何文字目まで到達したか典型要素を詰め合わせた教育的問題 3つ組(i<j<k)の問題

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

2018-05-30

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

累積和 AtCoder300点 AtCoder ABC-C 茶色diff 最適化テク:最適解の形を考える前処理累積和テク:左右両端からの累積和や累積結果を前処理 N個のものうち1個を変更・削除したものを解く ARC-C そのまま覚えたい典型問題累積和テク:累積和や累積結果を前処理しておく DP DP状態:フェーズ(耳DP) ナップサックDP DP状態:on/off 0と1の問題累積和テク:条件を満たすものの個数を累積和で表す典型要素を詰め合わせた教育的問題【問題集】累積和

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