Yandex.Algorithm 2015 Round 1 C問題 - Solitaire Simplified

Source

Yandex.Algorithm 2015
Yandex.Algorithm 2015 Round 1
問題文

問題概要

$1$ から $N$ までの整数が書かれたカードが $N$ 枚からなる一山のデッキがあるとき,次のルールでゲームを行う.
一番上のカードが,残されているカードの中で最小値または最大値であれば,取り除く.
そうでなければ,一番上のカードを一番下に移動する.
この時,最後に取り除くカードが $K$ となるような,$1$ から $N$ のカードの初期配置が何パターンあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.

解法

実験してみると,答え $T(N,K)$ は $1$ から $N$ の置換の中で,隣り合う要素を見て,右のほうが大きい部分が $K-1$ 箇所あるような数と等しいことがわかる.
これは,Eulerian numbers A008292と呼ばれるもので,例えば以下の漸化式などを用いれば時間計算量 $O(TK)$ 程度で解ける(もっと高速な公式もある).
$\qquad T(i,j) = 0, \;\;(i \leq 0 $ または $j \leq 0$ または $j > i)$,
$\qquad T(1,1) = 1,$
$\qquad T(i,j) = j \times T(i-1,j) + (i-j+1) \times T(i-1,j-1).$

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

#define MD 1000000007

/*
int main(){
  int i, j, k;
  int N = 7;
  int ind[1000];
  int cnt[1000] = {};
  int now[100], sz;
  int mx, mn;

  // A008292
  rep(i,N) ind[i] = i;
  do{
    sz = N;
    rep(i,N) now[i] = ind[i];
    mx = N-1; mn = 0;
    while(sz != 1){
      if(now[0]==mx || now[0]==mn){
        if(now[0]==mx) mx--;
        if(now[0]==mn) mn++;
        sz--;
        rep(i,sz) now[i] = now[i+1];
      } else {
        now[sz] = now[0];
        rep(i,sz) now[i] = now[i+1];
      }
    }
    cnt[now[0]]++;
  }while(next_permutation(ind,ind+N));

  rep(i,N) writerLn(i,cnt[i]);
  rep(i,N){
    k = 0;
    rep(j,i+1) k += cnt[j];
    writerLn(i,k);
  }
  return 0;
}
*/

int N, K;
ll dp[555][555];

int main(){
  int i, j;

  dp[1][1] = 1;
  REP(i,2,515) REP(j,1,i+1){
    dp[i][j] = (j * dp[i-1][j] + (i-j+1) * dp[i-1][j-1]) % MD;
  }

  reader(&N,&K);
  writerLn(dp[N][K]);

  return 0;
}

Current time: 2024年03月19日16時36分34秒
Last modified: 2015年05月26日23時37分31秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2015 Yandex_Algorithm_2015_Round1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: