7K12 blog

猫でも分かるアルゴリズム解説

2020-07-31から1日間の記事一覧

AOJ DPL_1_D Longest Increasing Subsequence

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4726957 最長増加部分列の計算量は 小さい数字に貪欲に更新することで部分列の長さが増加する可能性を増やす。二分探索したときendであれば、その数字を追加することで長さが1増える。更新するべきか…

ABC135 D - Digits Parade

https://atcoder.jp/contests/abc135/submissions/15552119 桁DPで処理する 初期値は dp[0][0] = 1 繰り返しは rep(i, 1, Size(S)) 更新は if (S[i] == '?') rep(j, 0, 13) rep(k, 0, 10) dp[i][(j * 10 + k) % 13] += dp[i - 1][j] など 出力は dp.back()[5…