fc2ブログ

Entries

Beta Round #93 DIV1 D問題 - Fibonacci Sums (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV1 D問題 (2000pt)
Problem description

問題概要

フィボナッチ数とは
 1, 2, 3, 5, 8, 13, ...
である.
正整数n (10^18以下) が与えられた時,それを異なるフィボナッチ数の和で書く方法は何通りあるかを求める問題.
テストケースの数は10^5以下.

解法

DP.
とりあえず,与えられた整数をフィボナッチ進数みたいなので適当に書いた表記を計算する.
 19 = 1*13 + 0*8 + 1*5 + 0*3 + 0*2 + 1*1 = 101001(fib)
みたいなの.とりあえず,自分以下の最も大きいフィボナッチ数で引いていくことで得られる.
 連続する2つの1を消し,その一つ上の桁に1を加える.
 1を消し,1つ下と2つ下の桁に1ずつ加える.
という操作ができるので,適当に,上の桁から確定するとして,今何桁目かと,次の桁と次の次の桁の値を状態にしてDPする.
ある桁の値が3以上になる,-2以下になるなどしたら,それより下の桁で調整できないので,そういう状態遷移は行わない.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int n;
ll fib[100];
ll dp[98][4][4];
char g[98];

ll solve(int depth, int now, int next){
  int i,j,k;
  ll res = 0;
  int a, b, c;

  if(depth==1 && now==1 && next==1) return 1;
  if(depth==1) return 0;
  
  if(dp[depth][now][next] >= 0) return dp[depth][now][next];

  a = g[depth] + (now-1);
  b = g[depth-1] + (next-1);
  c = g[depth-2];
  
  if(a==0 || a==1){
    res += solve(depth-1, next, 1);
  }
  if(a==0 && b!=-1){
    res += solve(depth-1, next-1, 0);
  }
  if( (a==1 || a==2) && b!=2 ){
    res += solve(depth-1, next+1, 2);
  }

  return dp[depth][now][next] = res;
}

int main(){
  int i,j,k,l,m,n;
  ll in, res;
  int size;

  fib[0]=1;
  fib[1]=2;
  REP(i,2,100){
    fib[i]=fib[i-1]+fib[i-2];
    if(fib[i]>1000000000000000000LL){
      n = i;
      break;
    }
  }

  scanf("%d",&size);
  while(size--){
    scanf("%I64d",&in);
    rep(i,n+2) rep(j,4) rep(k,4) dp[i][j][k] = -1;
    for(i=n-1;i>=0;i--){
      g[i+2] = 0;
      if(in >= fib[i]) in -= fib[i], g[i+2]++;
    }
    g[0] = g[1] = 0;
    
    res = solve(n+1, 1, 1);

    printf("%I64d\n",res);
  }
  
  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2152-c1fadf1a
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)