UVa1228

UVa1228

メモ化する。
memo[ 使った 0 の数 ][ 使った 1 の数 ]

0 と 1 はそれぞれ先頭から使う。つまり、入れ替わりが発生するのは同じ数同士ではない。
与えられた遅延の値を見ていけば答えは出せる。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;
typedef unsigned long long int ulli;

using namespace std;


const int ONE = 64 + 1;
const int ZERO = 64 + 1;
ulli memo[ONE][ZERO];
bool vis[ONE][ZERO];

int size_o, size_z;
int D;
lli O[ONE], Z[ZERO];

ulli rec(int o, int z)
{
  if (vis[o][z]) return memo[o][z];
  vis[o][z] = true;
  if (o == size_o && z == size_z) return memo[o][z] = 1;

  ulli sum = 0;

  int curr = max(O[o - 1], Z[z - 1]);

  bool prev;
  bool next;

  prev = next = false;
  if (O[o] < curr && O[o] + D >= curr) {
    prev = true;
  }
  if (curr <= O[o]) {
    next = true;
  }
  if (o < size_o && (prev || next)) {
    sum += rec(o + 1, z);
  }


  prev = next = false;
  if (Z[z] < curr && Z[z] + D >= curr) {
    prev = true;
  }
  if (curr <= Z[z]) {
    next = true;
  }
  if (z < size_z && (prev || next)) {
    sum += rec(o, z + 1);
  }

  return memo[o][z] = sum;
}

ulli conv(string s)
{
  ulli n = 0;
  reverse(s.begin(), s.end());
  for (ulli i = 0; i < (ulli)s.size(); ++i) {
    if (s[i] == '1') {
      n |= (ulli)1 << i;
    }
  }
  return n;
}

string ulli2s(int len, ulli num)
{
  string s = "";
  for (int i = 0; i < len; ++i) {
    s += '0' + (num % 2LL);
    num /= (ulli)2;
  }
  reverse(s.begin(), s.end());
  return s;
}

ulli make_max(int len, ulli num)
{
  string s = ulli2s(len, num);
  vector< pair<int, int> > v;
  for (int i = 0; i < (int)s.size(); ++i) {
    if (s[i] == '1') v.push_back(make_pair(i, -1));
    else v.push_back(make_pair(i + D, 0));
  }
  sort(v.begin(), v.end());

  for (int i = 0; i < (int)s.size(); ++i) {
    if (v[i].second == 0) {
      s[i] = '0';
    } else {
      s[i] = '1';
    }
  }
  return conv(s);
}

ulli make_min(int len, ulli num)
{
  string s = ulli2s(len, num);
  vector< pair<int, int> > v;
  for (int i = 0; i < (int)s.size(); ++i) {
    if (s[i] == '1') v.push_back(make_pair(i + D, 1));
    else v.push_back(make_pair(i, 0));
  }
  sort(v.begin(), v.end());

  for (int i = 0; i < (int)s.size(); ++i) {
    if (v[i].second == 0) {
      s[i] = '0';
    } else {
      s[i] = '1';
    }
  }

  return conv(s);
}

int main(int argc, char *argv[])
{
  ulli n, k;
  while (cin >> n >> D >> k) {
    size_o = size_z = 0;
    O[size_o++] = 0;
    Z[size_z++] = 0;
    for (lli i = n - 1; 0 <= i; --i) {
      if (k & (1LL << i)) O[size_o++] = n - i - 1;
      else Z[size_z++] = n - i - 1;
    }

    fill(&vis[0][0], &vis[ONE - 1][ZERO], false);

    ulli mem = rec(1, 1);
    ulli mn = make_min(n, k);
    ulli mx = make_max(n, k);

    static int tc = 0;
    cout << "Case " << ++tc << ": " << mem << ' ' << mn << ' ' << mx << endl;
  }
  return 0;
}