Submission #340427

---

Source Code Expand

/**
 * A - ニコニコ文字列２
 *
 * 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 現在までに出現しているニコニコ文字列パターン数 ( ただし上限 required_nico_patterns )
 * @param o 現在まで連続しているニコニコ文字列の文字数
 */
long long int count_password_pattern_recursive( int n, int m, int o )
{
	// std::cout << "(" << n << "," << m << "," << o << ")" << std::endl;
	
	if ( n == input_string.size() )
	{
		return m >= required_nico_patterns ? 1 : 0;
	}
	
	if ( m >= required_nico_patterns )
	{
		m = required_nico_patterns;
	}
	
	if ( dp[ n ][ m ][ o ] >= 0 )
	{
		return dp[ n ][ m ][ o ];
	}
	
	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, input_string[ n ] == '2' );
	}
	
	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

Judge Result