inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_o選んだボールの1、選ばれなかったボールを0と表すと、例えばN=5で1と4が選ばれたら、10010と表現できます。 出力例を見ると、下のほうは差が等差数列になっていて簡単そうですね。一方、kが小さいとDPが使えます。例えば、k=2なら、左から考えて、直前に1があった状態と次に1を置ける状態の2つがあって、という状態に、という行列を作用すれば答えが出るので、kが小さければ速いです。ただ、これだと個々の計算量がなのであまり大きいkには使えません。 もう少し詳しく見てみましょ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F2023%2F09%2F16%2F100849" title="アルゴリズムと数学 101 - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2023-09-16 10:08:49 rich https://inamori.hateblo.jp/entry/2023/09/16/100849 1.0 100%