競プロを頑張るブログ

問題を解いてる時の思考なりをまとめていきます

yukicoder1011を解いた

c++ yukicoder 競プロ 競技プログラミング 解法

はじめに (ネタバレ無し)

こんにちは
ひぽたふです。

解きながらの考察、実際の解法をまとめておこうかなと思います。

今回解いた問題はこれです。

No.1011 Infinite Stairs - yukicoder

星2.5の問題です。 いい感じの、おすすめできる問題でした。

以下はネタバレがあるので見る際は注意してください。

解きながらの考察 (ネタバレ　方針まで)

ここからはネタバレがあります。 問題を解いている際に考えていたことをまとめておこうかなと思います。











問題概要

最初は0段目にいて、次の行動をN回繰り返す。
i段目にいる時、i + 1段目、i + 2段目 ... i + d段目のいずれかに移動。
つまり、後戻りを考えずに進むことだけ考えるということだね。

N回移動した後、K段目にいる移動方法は何パターンか。

考察

dはKより小さい時があるから、基本d歩で歩いて余剰でうまいこと歩き方を変えれば良さそうかな？
それで、どこをd歩部分にするかを後で考える・・・いやこれだとダメか。
Nに余裕がある時はd歩取っていく必要ないしなあ。。。

逆に、Nが小さい時は歩き方にバリエーションは少ないかな？

例えば、N=3, K=15, d=5の時はd歩ずつ歩く1通りしか考えられないね。
N=1の時はKがdよりも小さいか確認したら1通りしか考えられなさそうだね。
N=2の時は、1~d歩を適当に歩いてみてからN=1の確認をすれば良さそう！

残り移動回数(n)と、目的地までの距離(k)を引数にして、パターンを計算するDPを考えれば解けそう！

分岐は、1~d歩を適当に歩かせればいいね。

オーダーはO(n * k * d)で、3004 > 108
あああ・・・ちょっとはみ出る・・・

DP内のループを高速化できるかもしれないし、とりあえず実装してみようかな！

今回は中身の高速化が見えやすくて、そのままAC！

あとがき + 解法(ネタバレ全開)











DP内のループは累積和で解決しました。
残り移動回数に関するnについて、nからはn - 1にしか遷移しないので、とても累積和が見やすい形だったんじゃないかなと思います。

私は余りを計算するのを忘れたので、ご注意を！

ソースコード

ll MOD = 1'000'000'000 + 7;
ll mod(ll v) {
  if (v >= MOD) return v % MOD;
  return v % MOD;
}

int main() {
  ll input(N, d, K);

  vector<ll> dp(K + 1);
  REP(k, K + 1) { // n == 1 の時
    if (k <= 0) dp[k] = 0;
    else dp[k] = (int) k <= d;
  }

  vector<ll> cumsum(K + 1);
  REP(n, N - 1) { // [0, N - 1)
    partial_sum(dp.begin(), dp.end(), cumsum.begin());
    FORD(k, K, 1) { // [K, 1]
      dp[k] = mod(cumsum[k - 1] - cumsum[max(1ll, k - d) - 1]);
      // cumsum[a] - cumsum[b - 1] = sum(dp[b] ~ dp[a])
    }
  }

  print(dp[K]);
}

マクロに関しては別の記事でまとめてあります。

テンプレート - 競プロを頑張るブログ

REPと入出力のみ使用しています。
REPは半開区間、FORは閉区間となっています。

nに関する遷移が単純だったので、DPテーブルがKに関する1次元で収まってますね。

DP内での処理は、DPテーブル内の特定区間で合計を取るというものでした。

その処理を累積和で求めている形ですね。

計算量は、Nに関するループ * (累積和の準備 + Kに関するループ)
なので、O(N * K)ですね！

https://yukicoder.me/submissions/493276

いきなりテーブルを1次元で持とうとするのは大変だったので、最初は2次元から実装し始めるのがオススメです！

それでは、またっ！

今回の便利

  • #include <numeric>
    • partial_sum
    • accumulate

シーケンスに対する計算処理が定義されているみたいです。

今回はpartial_sumで累積和を求めています。
accumulateだと全体の合計値だけ返してくれますね。

gcdとかlcmもnumericに入ってるみたいです。