保存されている過去のバージョンの一覧

2015年01月21日00時53分44秒

AtCoder Beginner Contest #017 C問題 - ハイスコア

Source

AtCoder Beginner Contest #017
問題文

問題概要

$N$ 個のサプリメントがある．
サプリメントには $M$ 種類の味があり，サプリメント $k$ の味は $F_k$ である．
サプリメントは，番号の若い順に食べなければいけない．
サプリメントは，一日に何個食べても良いが，同じ味のサプリメントを一日に複数食べてはいけない．
サプリメントが残っているなら，サプリメントを $1$ つも食べない日があってはいけない．
というときに，サプリメントを $N$ 個食べきる方法は何通りあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題．

解法

尺取法をしながら動的計画法にて求める．
$\verb|dp[|k\verb|]|$ を入力が最初の $k$ 個のサプリメントしかない場合の答えとすると，
$\quad \verb|dp[|k\verb|]| = \verb|dp[|k-1\verb|]| + \verb|dp[|k-2\verb|]| + \cdots + \verb|dp[|i\verb|]|$
という風に計算できる．
ただし，$i$ は $F_{j+1}, F_{j+2}, \ldots, F_{k}$ が一度に食べれる（同じ味が複数ない）ような最小の $j$ である．
ここで，$k$ が増えると，このような $i$ も増えていく（厳密に言うと減らない）ので，この区間およびこの区間の $\verb|dp|$ 配列の値を尺取法で計算しながら，動的計画法をすれば良い．
時間計算量は $O(N+M)$ 程度．

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(int x, char c){int s=0,m=0;char f[10];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 N, M;
int F[111111];

ll dp[111111];
int cnt[111111], dame;

int main(){
  int i, j, k;
  int st, ed, res;
  ll sum;

  reader(&N,&M);
  rep(i,N) reader(F+i);

  dp[0] = 1;
  st = 0; sum = 0;
  rep(i,N){
    if(cnt[F[i]]==1) dame++;
    cnt[F[i]]++;
    sum = (sum + dp[i]) % MD;
    while(dame){
      sum = (sum - dp[st]) % MD;
      cnt[F[st]]--;
      if(cnt[F[st]]==1) dame--;
      st++;
    }
    dp[i+1] = sum;
  }

  res = dp[N];
  if(res < 0) res += MD;
  writerLn(res);

  return 0;
}

Current time: 2024年04月19日20時13分54秒
Last modified: 2015年01月21日00時53分44秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC017 ABC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：