しゃくとり法
問題 atcoder.jp 解法 いわゆる「しゃくとり法」で解ける問題。 数列cの中からK個の連続した数値を選び、その種類が最大になる範囲を総当たりで調べる。 わけだけど、ベタに作ると計算量が多すぎる。 範囲の左端と右端を決定し、色数を計算。 色数が最大か?…
問題 atcoder.jp 解法 数列A, Bを、それぞれ先頭から何個目まで使用することができるか?という問題。 数列A, Bを、しゃくとり法で走査する。 数列Aはゼロから。 数列Bは最後尾から条件を満たす位置を走査して、最大値を調べる。 実装
問題 atcoder.jp 解法 しゃくとり法という単語をAtCoderの解法でよく聞くが、やったことなかったので、やってみる。 ある条件を満たす数列の範囲を、しゃくとり虫のように長さを変えながら探索するアルゴリズムで 条件〇〇を満たす区間 (連続する部分列) の…