日記

のみろぐ

主に競プロ日記です

観音堂

考察

  • 状態変数を考える
  • dp[i段目までの組み合わせの個数]で出来そう
  • 次に状態遷移を考える
  • 初期位置から1, 2, 3段目は1通りあるので、dp[1] = dp[2] = dp[3] = 1で初期化する。
  • 遷移はdp[i+1] += dp[i]とかで出来そう

解法

  1. dp[i段目までの組み合わせの個数]という状態を持つ
  2. dp[1] = dp[2] = dp[3] = 1で初期化する
  3. 遷移は以下の通り
dp[i] → dp[i+1]
            → dp[i+2]
            → dp[i+3]

コード

#include <bits/stdc++.h>
using namespace std;

#define int long long

int dp[50];
int n;

// 前計算
void init() {
  dp[0] = 1;
  for (int i = 0; i <= 30; i++) {
    for (int j = 1; j <= 3; j++) {
      dp[i+j] += dp[i];
    }
  }
}

signed main() {
  init();
  while (1) {
    cin >> n;
    if (n == 0) break;
    int mult = 3650;
    cout << (dp[n] + mult - 1) / mult << endl; // 切り上げ
  }

  return 0;
}

自分で書いたコード

  • 思いついたまままに書いたコード
  • min(1LL, hoge)は、一度提出してWAが出たから直した部分(ローカルでちゃんと確認しなかった)
  • 切り上げ、最近使わないのですっかり忘れてた

メモ化再帰で解いてみる

再帰のコード

  • これ、$O(3N)$だから通らないと思ったけど通っちゃったよ。えー、なんでー?
#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;

int rec(int stage) {
  // 終了条件
  if (stage == 0) {
    return 1;
  }

  int ans = 0;

  for (int i = 1; i <= 3; i++) {
    if (stage - i < 0) continue;
    ans += rec(stage - i);
  }

  return ans;
}

signed main() {
  while (1) {
    cin >> n;
    if (n == 0) break;
    int ans = (rec(n) + 3650 - 1) / 3650;
    cout << ans << endl;
  }

  return 0;
}

メモ化再帰のコード

  • 蟻本のナップサックのメモ化再帰みたいに書ける
#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;
int dp[55];

int rec(int stage) {
  // 終了条件
  if (stage == 0) {
    return dp[stage] = 1;
  }
  
  // 一度求めた値の場合、メモしたやつを返す
  if (dp[stage] != -1) {
    return dp[stage];
  }

  int ans = 0;

  for (int i = 1; i <= 3; i++) {
    if (stage - i < 0) continue;
    ans += rec(stage - i);
  }

  // 値を求めたらメモる
  return dp[stage] = ans;
}

signed main() {
  // 前処理
  fill(dp, dp+33, -1);
  rec(30);

  while (1) {
    cin >> n;
    if (n == 0) break;
    int ans = (dp[n] + 3650 - 1) / 3650;
    cout << ans << endl;
  }

  return 0;
}

感想

  • 状態変数考えて遷移書いたらなんか上手くいった。問題文に「値が大きくなる」と書いてあったので、この遷移で値大きくなるのか〜?みたいに思った(実際大きくなったけど)
  • なんでただの再帰で解けるんだ?計算量的に無理では?