dwangoプログラミングコンテスト

Submission #621200

Source codeソースコード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double 
 
using namespace std;
 
#define MAX_N 255
#define MAX_X 255

#define mod 1000000007

int N, X;
string S;

//dp[pos][nico_counting_cnt][nico_count][2]
LL dp[MAX_N][MAX_N][MAX_X][2];

int main(){

  cin >> N >> X;
  cin >> S;

  X--;

  dp[0][0][0][0] = 1;

  for(int pos = 0; pos < N; pos++){
    for(int nico_counting_cnt = 0; nico_counting_cnt <= X; nico_counting_cnt++){
      for(int nico_cnt = 0; nico_cnt <= X; nico_cnt++){
	for(int flag2 = 0; flag2 < 2; flag2++){
	  
	  //直前の文字が2であったとき
	  if(flag2){
	    
	    if(S[pos] == '?'){
	      
	      //?に5を割り当てるとニコニコ文字列になる
	      if(nico_counting_cnt + 1 + nico_cnt <= X){
		dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][1];
		dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] %= mod;
	      }
	      //?に5以外の数字を割り当てる

	      //2を割り当てない場合
	      dp[pos+1][0][nico_cnt][0] += 8*dp[pos][nico_counting_cnt][nico_cnt][1];
	      dp[pos+1][0][nico_cnt][0] %= mod;
	      
	      //2を割り当てる場合
	      dp[pos+1][0][nico_cnt][1] += dp[pos][nico_counting_cnt][nico_cnt][1];
	      dp[pos+1][0][nico_cnt][1] %= mod;

	    }
	    else if(S[pos] == '2'){
	      
	      dp[pos+1][0][nico_cnt][1] += dp[pos][nico_counting_cnt][nico_cnt][1];
	      dp[pos+1][0][nico_cnt][1] %= mod;

	    }
	    else if(S[pos] == '5'){
	      dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][1];
	      dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] %= mod;
	    }
	    else{
	      dp[pos+1][0][nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][1];
	      dp[pos+1][0][nico_cnt][0] %= mod;
	    }

	  }
	  
	  //直前の文字が2以外であった時
	  else{
	    
	    if(S[pos] == '?'){
	      
	      //?に2を割り当てればnico_countingを継続した状態を引き継げる
	      dp[pos+1][nico_counting_cnt][nico_cnt][1] += 
		dp[pos][nico_counting_cnt][nico_cnt][0];
	      dp[pos+1][nico_counting_cnt][nico_cnt][1] %= mod;

	      //?に2以外を割り当てる場合
	      dp[pos+1][0][nico_cnt][0] += 9*dp[pos][nico_counting_cnt][nico_cnt][0];
	      dp[pos+1][0][nico_cnt][0] %= mod;

	    }
	    else if(S[pos] == '2'){
	      
	      dp[pos+1][nico_counting_cnt][nico_cnt][1] += 
		dp[pos][nico_counting_cnt][nico_cnt][0];
	      dp[pos+1][nico_counting_cnt][nico_cnt][1] %= mod;

	    }
	    else{
	      
	      dp[pos+1][0][nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][0];
	      dp[pos+1][0][nico_cnt][0] %= mod;

	    }

	  }

	}
      }
    }
  }

  LL ans = 1;
  for(int i = 0; i < N; i++){
    if(S[i] == '?'){
      ans *= 10;
      ans %= mod;
    }
  }
  
  LL tmp = 0;
  for(int nico_counting_cnt = 0; nico_counting_cnt <= X; nico_counting_cnt++){
    for(int nico_cnt = 0; nico_cnt <= X; nico_cnt++){
      for(int flag2 = 0; flag2 < 2; flag2++){
	if(dp[N][nico_counting_cnt][nico_cnt][flag2] > 0){
	  tmp += dp[N][nico_counting_cnt][nico_cnt][flag2];
	  tmp %= mod;
	}
      }
    }
  }

  cout << (ans-tmp)%mod << endl;
  
  /*
  for(int i = 0; i <= N; i++){
    for(int nico_counting_cnt = 0; nico_counting_cnt <= X; nico_counting_cnt++){
      for(int nico_cnt = 0; nico_cnt <= X; nico_cnt++){
	for(int flag2 = 0; flag2 < 2; flag2++){
	  fprintf(stderr, "(i,nico_counting_cnt, nico_cnt, flag2),(%d,%d,%d,%d) := %lld\n", i, nico_counting_cnt, nico_cnt, flag2, dp[i][nico_counting_cnt][nico_cnt][flag2]);
	}
      }
    }
  }
  */

  return 0;

}

Submission

Task問題 A - ニコニコ文字列2
User nameユーザ名 takoshi
Created time投稿日時
Language言語 C++ (G++ 4.6.4)
Status状態 WA
Score得点 0
Source lengthソースコード長 4465 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
All 0 / 20 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 25 ms 796 KB
sample_02.txt AC 26 ms 932 KB
subtask1_01.txt AC 25 ms 928 KB
subtask1_02.txt AC 26 ms 916 KB
subtask1_03.txt AC 25 ms 916 KB
subtask1_04.txt AC 24 ms 796 KB
subtask1_05.txt WA
subtask1_06.txt AC 159 ms 39324 KB
subtask1_07.txt AC 74 ms 16160 KB
subtask1_08.txt AC 283 ms 57376 KB
subtask1_09.txt WA
subtask1_10.txt WA
subtask1_11.txt WA
subtask1_12.txt AC 920 ms 141992 KB
subtask1_13.txt AC 58 ms 11172 KB
subtask1_14.txt AC 1174 ms 255520 KB
subtask1_15.txt WA
subtask1_16.txt WA
subtask1_17.txt AC 1233 ms 254752 KB
subtask1_18.txt AC 1107 ms 254756 KB
subtask1_19.txt WA
subtask1_20.txt WA
subtask1_21.txt AC 23 ms 932 KB
subtask1_22.txt AC 25 ms 800 KB