Codeforces Beta Round #9

Codeforces 凡ミス

凡ミスタグを付けなくてすむその日まで頑張る.

A Die Roll

(^p^)

B Running Student

sqrtの中身にintの範囲を超えるものを渡してて,それに気付かなかった(^p^)前にもsqrtの中身が負でバグってたことがあった。はぁ…

引数がおかしくなるケースがあるか考えよう

あとintの範囲は2^31^1 == 2147483647 だいたい 2 * 10^9.今回は(10^5)^2でint超えてた

C Hexadecimal's Numbers

10進数で0と1だけで構成できる,ある数を超えない数はいくつ？

1から*10 + 1、*10 を再帰的に数えた.

D How many trees?

ノード数N,高さがH以上の2分木は何通り構成できる？

  • 木の性質かなぁ…ググル
  • 大した情報ないので考える.
  • あるノードの左,右につけるものを考えるとき,自分より大きい数字がいくつ,小さい数字がいくつって情報だけでいいよな
  • じゃあこれに今の高さの情報を付け加えて再帰かな
  • 高さがH以上になるには,あるノードの左の木が高さH以上じゃなくても右の木がH以上ならいいから…
  • 返り値に最大の高さと構成数が必要？pair？？
  • って考えててこんがらかって終了
  • 無条件の構成方法から,高さがH未満の構成方法を引くって方針に切り替えたらすんなり書けた
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <complex>
#include <set>
#include <vector>
#include <bitset>

#define REP(i,N)for(int i=0;i<(int)N;i++)
#define MP(a,b) make_pair(a,b)
using namespace std;

int nextInt(){
  int ret=0,sign=1;
  char c=' ';
  while (!isdigit(c=getchar())){
    if (c==EOF) return -1;
    if (c=='-') sign=-1;
  }
  do{
    ret=ret*10+(c-'0');
  }while (isdigit(c=getchar()));
  return ret*sign;
}
void printlineInt(int num){
  char str[101];
  if (num<0) num=-num,putchar('-');
  else if (num==0) {puts("0");return;}
  str[100]='\0';
  int i=99;
  for (;num;i--){
    str[i]=num%10+'0';
    num/=10;
  }
  puts(&str[i+1]);
  return;
}
//template end
int N,H;
long long dp[36][36][36];
long long dp2[36][36][36]; 

long long rec(int l,int u,int h){
  if (dp[l][u][h] != -1LL) return dp[l][u][h];
  //cout << h << " " << H << endl;
  if (h >= H) return dp[l][u][h] = 0;
  if (l == 0 && u == 0){
    return dp[l][u][h] = 1LL;
  }
  long long r1=0,r2=0;
  REP(i,l){
    r1 += rec(i,l-i-1,h+1);
  }
  if (!l) r1 = 1;
  REP(i,u){
    r2 += rec(i,u-i-1,h+1);
  }
  if (!u) r2 = 1;
  //cout << l << " " << u << " " << h << " " << r1 * r2 << endl;
  return dp[l][u][h] = r1 * r2;
}
long long rec2(int l,int u,int h){
  if (dp2[l][u][h] != -1LL) return dp2[l][u][h];
  if (l == 0 && u == 0){
    return dp2[l][u][h] = 1LL;
  }
  long long r1=0,r2=0;
  REP(i,l){
    r1 += rec2(i,l-i-1,h+1);
  }
  if (!l) r1 = 1;
  REP(i,u){
    r2 += rec2(i,u-i-1,h+1);
  }
  if (!u) r2 = 1;
  //cout << l << " " << u << " " << h << " " << r1 * r2 << endl;
  return dp2[l][u][h] = r1 * r2;
}

int main(){
  N=nextInt(),H=nextInt();
  REP(i,36) REP(j,36) REP(k,36) dp[i][j][k] = -1LL;
  REP(i,36) REP(j,36) REP(k,36) dp2[i][j][k] = -1LL;
  long long ans=0;
  REP(i,N){
    ans += rec2(i,N-i-1,1) - rec(i,N-i-1,1);
  }
  cout << ans << endl;
}

(^p^)