ドワンゴのプログラミングコンテストをクリアできなかったお話

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

ドワンゴが主催するプログラミングコンテストの予選が、24日に行われたそうだ。筆者はクリアできなかったが、簡単なものだけ解説する。本格的な解説が読みたい人は、わざわざこの記事を読まずとも、以下で解説されているようだ。

「dwangoプログラミングコンテスト」予選問題解説 // Speaker Deck

A: プレミアム会員 - dwangoプログラミングコンテスト | AtCoder

ニコニコ動画には、プレミアム会員という制度があります。このプレミアム会員制度には月額一定の額を支払うことで加入できます。

ニワンゴくんは、この n ヶ月間連続してプレミアム会員です。 また、x ヶ月前に月の一定支払い額が 525 円から 540 円に変わったことを知っています。 つまり、この n ヶ月のうち最近の x ヶ月間は月額 540 円支払っていて、それ以外の月では 525 円払っていたことが分かっています。

n と x が与えられるので、この n ヶ月間でニワンゴくんがプレミアム会員制度に支払った合計額を出力してください。

\(525(n-x) + 540x\)を計算すればよい。

#include <iostream>
 
int main()
{
    int n = 0 ;
    int x = 0 ;

    std::cin >> n >> x ;
 
    int payment = ( n - x ) * 525 + x * 540 ;
 
    std::cout << payment << '\n' ;
}

B: ニコニコ文字列 - dwangoプログラミングコンテスト | AtCoder

0 から 9 の数字から成る文字列 S が与えられます。

ある文字列 X について、X="25" または X="2525" または X="252525" …… というふうに "25" を何回か繰り返した文字列になっているとき、X はニコニコ文字列であるといいます。 たとえば "25" や "25252525" はニコニコ文字列ですが、"123" や "225" はニコニコ文字列ではありません。

あなたの仕事は、文字列 S について、ニコニコ文字列となるような連続した部分文字列の取り出し方が何通りあるかを答えることです。 文字列として同じであっても、取り出し位置が異なっていれば別々に数えます。

与えられた文字列から連続した"25"をすべて探し出し、25の数を数える。N個の"25"が連続した文字列の部分文字列の取り出し方は、1+2+3+...+N通りあるので、\(\frac{N(1 + N)}{2}\)で計算すればよい。

ただし、Sの長さは100000以下であるとのことなので、もし\(\frac{N(1 + N)}{2}\)の計算に32bit符号付き整数を使っていた場合、50000回連続した文字列が渡されると、50001 * 50000を計算しようとするとオーバーフローしてしまう。

連続した"25"文字列は、C++11で追加された<regex>ライブラリを使えばよい。

#include <iostream>
#include <string>
#include <regex>

unsigned long long int count( unsigned long long int n )
{
    return ( 1 + n ) * n / 2 ;
}

int main()
{

    std::string str ;
    std::cin >> str ;

    std::regex re(R"((?:25)+)") ;

    std::sregex_iterator iter( str.cbegin(), str.cend(), re ) ;
    std::sregex_iterator end ;

    unsigned long long int sum = 0 ;
    for ( ; iter != end ; ++iter )
    {
        auto n = iter->str().length() / 2 ;
        sum += count( n ) ;
    }

    std::cout << sum << '\n' ;
}

ただし、このコードはatcoderを通らない。理由は、atcoderのC++11のコンパイラーがGCC4.8.1という2年前の化石バージョンで、libstdc++がregex_iteratorをサポートしていないからだ。そのため、以下のようにregex_searchを複数回呼び出すというマヌケなコードを書かなければならない。

#include <iostream>
#include <string>
#include <regex>

unsigned long long int count( unsigned long long int n )
{
    return ( 1 + n ) * n / 2 ;
}

int main()
{

    std::string str ;
    std::cin >> str ;

    std::regex re(R"((?:25)+)") ;

    std::smatch m ;

    unsigned long long int sum = 0 ;

    auto iter = str.cbegin() ;
    auto end = str.cend() ;


    while ( iter != end )
    {
        std::regex_search( iter, end, m, re ) ;
        auto n = m.str().length() / 2 ;
        sum += count( n ) ;

        iter = m[0].second ;
    }

    std::cout << sum << '\n' ;
}

と思ったが、これも時間制限内に終わらない。Wandboxで試しても終わらないので、どうもlibstdc++ 4.8.1のregexライブラリには問題があるようだ。

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

2年前のC++コンパイラーなど使うべきではないという教訓が得られた。

C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoder

期待値の計算方法がわからないのでモンテカルロ法で解こうとしたが、必要な精度が出ずに敗北した。小数点以下6桁は辛い。

なんでも、必要な精度を出すためには、1兆回は試行しなければならないそうだ。制限時間は2分。すると、一回の試行は0.12ナノ秒で終えなければならない。無理だ。

本の虫: 全プログラマーが知るべきレイテンシー数

最終的に以下のようなコードを書きちらしたが、もちろん必要な精度は出ない。

#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <future>
 
enum { Rock = 0, Paper = 1, Scissors = 2 } ;
 
template < typename Iter, typename RNG >
unsigned long long int play( Iter begin, Iter end, RNG rng )
{
    unsigned long long int i = 0 ;
 
for ( ; ; ++i )
{
    int n = std::distance( begin, end ) ;
 
 
    // 勝者決定判定
    if ( n == 1 )
    {
        break ;
    }
 
    // じゃんけん
    std::generate( begin, end, rng ) ;
 
 
    // 出された手が 1 種類の場合 
    int first_hand = *begin ;
    bool b = std::all_of( begin, end,
        [=](int x) { return x == first_hand ; } ) ;
 
    if ( b )
    {
        continue ;
    }
 
    // 出された手が 2 種類以上の場合
 
    // 手をカウント
    
    auto rock = std::count( begin, end, Rock ) ;
    auto paper = std::count( begin, end, Paper ) ;
    auto scissors = std::count( begin, end, Scissors ) ;
 
 
    // 出したプレイヤーの数が最も少ない手に注目する。 
 
    // そのような手が 3 種類あった場合
    if ( rock == paper && rock == scissors )
    {
        continue ;
    }
 
 
    auto hands = { rock, paper, scissors } ;
    auto minor = std::min( hands ) ;
 
    // 出ていない手がある場合
    if ( minor == 0 )
    {
 
        typename Iter::difference_type h[3] = { rock, paper, scissors } ;
        std::remove( h, h + 3, 0 ) ;
        auto m = std::min( h[0], h[1] ) ;
        end = begin + m ;
        
    }
    else {
        // すべての手が出た場合
        end = begin + minor ; 
    }
   
}
 
    return i ;
 
}
 
 
constexpr unsigned long long int trial = 10000 ;
 
 
unsigned long long int gamer_zyanken( int n )
{
    std::mt19937 engine ;
 
    std::uniform_int_distribution<> dist( 0, 2 ) ;
 
 
    std::vector<int> players( n ) ;
 
    unsigned long long int sum = 0 ;
 
    for ( int i = 0 ; i != trial ; ++i )
    {
        sum += play( players.begin(), players.end(), [&]{ return dist(engine) ; } ) ; 
    }
 
    return sum ;
}

 
int main()
{
    int n ;
    std::cin >> n ;
 
    auto f1 = std::async( std::launch::async, gamer_zyanken, n ) ;
    auto f2 = std::async( std::launch::async, gamer_zyanken, n ) ;
    auto f3 = std::async( std::launch::async, gamer_zyanken, n ) ;
    auto f4 = std::async( std::launch::async, gamer_zyanken, n ) ;
 
    unsigned long long int sum = f1.get() + f2.get() + f3.get() + f4.get() ;
 
    double result = double(sum) / double(4 * trial) ;
 
    std::cout << result << '\n' ;
}