https://atcoder.jp/contests/typical90/tasks/typical90_ah ベーシックなしゃくとり法【問題】 数列の区間のうち、含まれる値の種類がK種類以下である最長の連続部分列を求めよ。 【典型ポイント】 しゃくとり法 【方針】 見たまんま、しゃくとり法の典型問…

問題https://atcoder.jp/contests/typical90/tasks/typical90_aq 解説 https://twitter.com/e869120/status/1394787605099601923/photo/1 【問題】 二次元迷路のスタートからゴールへの経路のうち、最も曲がる回数が少ない経路の回数を求めよ 【典型ポイント…

atcoder.jp 桁DPの典型的な問題 【題意】 自然数の区間[A, B]において、4または9を含む整数はいくつあるか？ 【典型ポイント】 1~Nの数え上げは桁DP 区間和 【方針】 dp[i][smaller][j]:=1~Nの整数のうち、前方i桁まで見て、4または9が含まれている(j==1)か…

atcoder.jp 桁DPの典型的な問題【題意】 自然数の区間[A, B]において、4または9を含む整数はいくつあるか？ 【典型ポイント】 1~Nの数え上げは桁DP 区間和 【方針】 dp[i][smaller][j]:=1~Nの整数のうち、前方i桁まで見て、4または9が含まれている(j==1)か含…

atcoder.jp ゲーム系。 勝負が確定している後ろからDPする(バックトラックというらしい) この方針は正しかったが、7の倍数判定を無駄に考えすぎて解けず。【問題】 数列が与えられる。 文字列の手番に従って、高橋君と青木君は新しい数列の末尾にS[i]か0を加…