DPの問題 atcoder.jp これは状態を列挙することと, どのように状態が遷移するかを見ることが必要となる. 今回の場合は文字の長さを i 番目まで見た時に状態がいくつあるか. ABCどれも使わない Aを使う場合 ABまで使う場合 ABCまで使い完成している場合 以上…

多次元DPの問題 dp[len][i][j][k] := 長さがlenのlen−２文字目が i len-1 文字目が j len 文字目が k である. 問題文に適する文字列の種類数 と定義する. import java.util.Scanner; class Main { static final long mod = 1000000007; public static void m…

2分岐探索 atcoder.jp 問題概要 N日満腹度が0より大きい状態でいる.毎日以下の3つの行動のいずれかをする 代金a円払いbの栄養をえる 代金c円払いdの栄養をえる 栄養を e 失う この状況下で生き残るために払う最初の値段を求める 考え方 最初に栄養をとり残り…

単純グラフ DFS atcoder.jp 問題概要 N頂点M辺の無向グラフが与えられる. 全ての頂点を丁度一回づつ通る経路は何通りあるかを求めよ. 始点は頂点1とする. 解答 今回の問題はDFSを用いて解くことができる. しっかり書いたコードは下に置いておき擬似コードを…

atcoder.jp 問題概要 'a','b','c'の３種類の文字のみを含むN文字の単語を辞書順で出力せよ 考察(TLE) abcの3つの文字なので3進数を使って0ならa,1ならb,2ならcを出力すればいいのかと思い実装したらコードが長くなりTLEしてしまった 解答 この問題は再帰関数…

DP(1次元)と全探索の複合問題 abc099.contest.atcoder.jp この問題はこちらにも書いてある通りC問題にしては難しいです.しっかり理解したい方はこの記事読んだ方が100倍わかりやすいです。 提出コード 問題 1 , 6p , 9q のうちから好きな数を選び取り合計をn…