Submission #340424


Source Code Expand

/**
 * A - ニコニコ文字列2
 *
 * http://dwango2015-honsen.contest.atcoder.jp/tasks/dwango2015_finals_1
 *
 */

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>

const int MAX_PASSWORD_LENTH = 252;
const int MAX_REQUIRED_NICO_PATTERNS = 252;

int password_length = 0;
int required_nico_patterns = 0;
std::string input_string;

long long int dp[ MAX_PASSWORD_LENTH ][ MAX_REQUIRED_NICO_PATTERNS ][ MAX_PASSWORD_LENTH ];

/**
 * 条件を満たすパスワードのパターン数を再帰的にカウントする
 *
 * @param n 文字列の現在のインデックス
 * @param m 現在までに出現しているニコニコ文字列パターン数
 * @param o 現在まで連続しているニコニコ文字列の文字数
 */
long long int count_password_pattern_recursive( int n, int m, int o )
{
	// std::cout << "(" << n << "," << m << "," << o << ")" << std::endl;
	
	if ( dp[ n ][ m ][ o ] >= 0 )
	{
		return dp[ n ][ m ][ o ];
	}
	
	if ( n == input_string.size() )
	{
		return m >= required_nico_patterns ? 1 : 0;
	}
	
	long long int password_patterns = 0;
	
	if ( input_string[ n ] == '2' && o % 2 == 0 )
	{
		password_patterns = count_password_pattern_recursive( n + 1, m, o + 1 );
	}
	else if ( input_string[ n ] == '5' && o % 2 == 1 )
	{
		password_patterns = count_password_pattern_recursive( n + 1, m + ( o + 1 ) / 2, o + 1 );
	}
	else if ( input_string[ n ] == '?' )
	{
		for ( int x = 0; x < 10; x++ )
		{
			if ( x == 2 && o % 2 == 0 )
			{
				password_patterns += count_password_pattern_recursive( n + 1, m, o + 1 );
			}
			else if ( x == 5 && o % 2 == 1 )
			{
				password_patterns += count_password_pattern_recursive( n + 1, m + ( o + 1 ) / 2, o + 1 );
			}
			else
			{
				password_patterns += count_password_pattern_recursive( n + 1, m, x == 2 );
			}
			
			password_patterns %= 1000000007;
		}
	}
	else
	{
		password_patterns = count_password_pattern_recursive( n + 1, m, 0 );
	}
	
	dp[ n ][ m ][ o ] = password_patterns % 1000000007;
	
	return dp[ n ][ m ][ o ];
}

int main( int argc, char** argv )
{
	memset( dp, 0xFF, sizeof( dp ) );
	
	std::cin >> password_length >> required_nico_patterns;
	std::cin >> input_string;
	
	std::cout << count_password_pattern_recursive( 0, 0, 0 ) << std::endl;
	
    return 0;
}

Submission Info

Submission Time
Task A - ニコニコ文字列2
User jepupu
Language C++ (G++ 4.6.4)
Score 0
Code Size 2372 Byte
Status WA
Exec Time 544 ms
Memory 125864 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 20
Status
AC × 2
AC × 5
WA × 6
RE × 11
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All 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
Case Name Status Exec Time Memory
sample_01.txt AC 284 ms 125812 KB
sample_02.txt AC 281 ms 125808 KB
subtask1_01.txt AC 263 ms 125804 KB
subtask1_02.txt AC 282 ms 125788 KB
subtask1_03.txt AC 274 ms 125792 KB
subtask1_04.txt AC 276 ms 125796 KB
subtask1_05.txt WA 294 ms 125796 KB
subtask1_06.txt AC 286 ms 125800 KB
subtask1_07.txt WA 325 ms 125800 KB
subtask1_08.txt WA 307 ms 125804 KB
subtask1_09.txt WA 273 ms 125796 KB
subtask1_10.txt WA 286 ms 125804 KB
subtask1_11.txt RE 536 ms 125800 KB
subtask1_12.txt RE 533 ms 125808 KB
subtask1_13.txt RE 532 ms 125808 KB
subtask1_14.txt RE 533 ms 125804 KB
subtask1_15.txt RE 540 ms 125804 KB
subtask1_16.txt RE 527 ms 125804 KB
subtask1_17.txt RE 516 ms 125796 KB
subtask1_18.txt WA 265 ms 125804 KB
subtask1_19.txt RE 514 ms 125796 KB
subtask1_20.txt RE 510 ms 125804 KB
subtask1_21.txt RE 518 ms 125864 KB
subtask1_22.txt RE 544 ms 125800 KB