naoya_t@hatenablog

いわゆるチラシノウラであります

SRM585

寝倒した…

ので過去問としてチャレンジ

Easy ("TrafficCongestion", 250)

  • treeHeight <= 1 のとき:1
  • treeHeight >= 2 のとき:
    • 葉にあたる町が 2^(treeHeight) 箇所ある
    • 葉を左から入って最初の町で右折してすぐに葉へ。これで 2^(treeHeight-1) 台消費
    • で下2段が消えるので、(treeHeight-2) の時の結果にこれを加えれば良いのでは
  • 218.45 (11'7'')
  • passed system test; 出てたら黄色に戻れてた風(寝倒さないのも実力のうち><)
#include <vector>
using namespace std;

typedef long long ll;

#define MOD 1000000007LL

class TrafficCongestion {
 private:
 public:
  int theMinCars(int treeHeight) {
    vector<ll> ma(1000001, 1LL);
    ll w = 2LL;
    for (int i=2; i<=1000000; ++i) {
      ma[i] = (ma[i-2] + w) % MOD;
      w = (w * 2) % MOD;
    }
    return (int)ma[treeHeight];
  }
};

Medium ("LISNumber", 500)

  • (一番左に持ってくる数)と(残りの中の最小)の組み合わせで K-1 の時との関係が描ける?

枚数が増えると時間がかかりすぎる駄目コード

#define MOD 1000000007LL

class LISNumber {
  int n, m;
  vector<int> cn;

 private:
  ll pos(int currmin) {
    for (int i=currmin; i<n; ++i) {
      if (cn[i] >= 2) return 0;
    }
    return 1;
  }

  ll solve(int before, int currmin, int k) {
    if (k == 1) return pos(currmin);

    if (currmin == n) return 1;
    if (cn[currmin] == 0) return solve(before, currmin+1, k);


    ll sum = 0LL;

    if (cn[currmin] >= 2) {
      --cn[currmin];
      sum = (sum + solve(currmin, currmin, k-1)) % MOD;
      ++cn[currmin];
    } else {
      sum = (sum + solve(currmin, currmin+1, k)) % MOD;
    }

    for (int i=currmin+1; i<n; ++i) {
      if (cn[i]==0) continue;
      --cn[i];
      sum = (sum + solve(i, currmin, k-1)) % MOD;
      ++cn[i];
    }

    return sum;
  }
 public:
  int count(vector<int> cardsnum, int K) {
    cn=cardsnum;
    n=sz(cn);
    m=0; rep(i,n)m+=cardsnum[i];
    return (int)solve(-1, 0, K);
  }
};