第4回 ドワンゴからの挑戦状予選に参加してみた

第4回　ドワンゴからの挑戦状

第4回、ドワンゴからの挑戦状の予選が開催されたので参加してみた。

A - ニコニコ文字列判定

まずA問題。数字のみが使われた4文字の文字列sが入力として渡される。数字x, yが存在して、sがxyxyのとき"Yes"を、そうでなければ"No"を出力する。

入力は必ず4文字で、数字のみなので、変な文字列が渡される心配をしなくてもよい。

#include <iostream>

int main()
{
    std::string s ;
    std::cin >> s ;

    if ( s[0] == s[2] && s[1] == s[3] )
        std::cout << "Yes" ;
    else
        std::cout << "No" ;
}

A問題は毎回とても簡単な傾向にある。私は最初の提出が、問題文をさっと見ただけでコードを書いてしまったので、"YES", "NO"を出力するようにしてしまい、間違えた。

B - 2525文字列分解

文字'2'と'5'からなる文字列sが入力として与えられる。その文字列を"25"の1回以上の繰り返しからなる2525文字列に分割する。文字を分割するときには、文字の相対的な順序を変えてはならない。分割できる最小数はいくつか。

この問題はとても簡単に解決できる。

文字列sから"25"を取り除く操作を繰り返して、空文字列になるまでの操作回数を数えた結果が答えだ。つまり何回s/25//gできるかを数えればよい。もし、文字列に対してs/25//gを適用しても文字列が変わらなかった場合、その文字列は2525文字列に分解できないので、-1を出力する。

文字列から"25"を取り除いた結果の文字列は、もしまだ2525文字列が存在するのであれば、必ず”25"が出現する。なので文字列が空になるまで繰り返しs/25//gすればよい。

実際のところ、この問題はbashとsedで解くことができる。sedのみで解くことはできるだろうか。どうやらsedは入力文字列を工夫すればチューリング完全であり、sedでチューリングマシンやテトリスを実装したと主張するWebサイトがあるが、詳しく読んでいないので真偽はわからない。

http://www.catonmat.net/blog/proof-that-sed-is-turing-complete/

さてコードに落としていこう。処理は簡単だ。入力の文字列にs/25//gを何回適用できるか数えるだけだ。ただし、空文字列ではないのに適用できなくなった場合、2525文字列に分割できないので-1となる。

このような問題を解くときは、すでに問題を解き終えたと仮定すると書きやすい。

まず、この問題を解く関数solveがすでに存在すると仮定する。この関数solveは文字列をstd::string &型で与えると出力すべき数値をint型で返してくれるとする。引数に渡した文字列は書き換えられるものとする。すると、もうすでに我々は問題を解き終えたわけなので、入力を受け取って関数solveに渡して出力するだけのコードを書けばよいことになる。

#include <iostream>
#include <string>

int main()
{
    std::string s ;
    std::cin >> s ;

    std::cout << solve( s ) ;
}

これで入出力の部分は書いた。あとは関数solveを実装するだけだ。

このような問題を解くときは、すでに問題を解き終えたと仮定すると書きやすい。

まず、文字列に対してs/25//gを行う関数remove_nicoがすでに存在すると仮定する。この関数remove_nicoはstd::string &型の引数を取り、s/25//gする。もしひとつ以上の"25"を置換したのであればtrueを、そうでなければfalseを返す。すると、我々はすでにs/25//gを実装し終えたわけなので、あとはこの関数remove_nicoを何回文字列に適用できるか数えればよいだけだ。ただし、空文字列ではないのにfalseを返した場合は-1だ。

int solve( std::string & s )
{
    int count = 0 ;
    while ( s.size() != 0 )
    {
        bool removed = remove_nico( s ) ;
        if ( removed ) // 適用した
            ++count ;
        else // 適用できなかったので2525文字列ではない
            return -1 ;
    }
    return count ;
}

さて、残りは関数remove_nicoさえ実装すればよい。実装方法としては、単に文字列を先頭から自分自身にコピーしていき、"25"はコピーをスキップすればよい。

bool remove_nico( std::string & s )
{
    auto dest = std::begin(s) ;
    auto src = dest ;
    auto end = std::end(s) ;

    // 文字を自分自身にコピーする
    while ( src != end )
    {
        // 文字列"25"ならばコピーしないことで除去
        if ( *src == '2' && *std::next(src) == '5' )
        {
            std::advance( src, 2 ) ;
        }
        else
        { // コピー
            *dest = *src ;
            ++dest ;
            ++src ;
        }
    }

    // 一度も"25"を除去していなければfalseを返す
    if ( dest == end )
        return false ;

    // 除去した"25"の数だけ文字列のサイズを減らす
    auto shrink = std::distance( dest, end ) ;
    s.resize( s.size() - shrink ) ;

    return true ;
}

しかしこういう処理を自前で書くのは面倒だ。s/25//gをしたいのであれば正規表現ライブラリを使えばいいのではないか。そう思う読者もいるだろう。実際、正規表現ライブラリはC++11で追加されている。問題は、この手の問題に正規表現ライブラリを使うというのは鶏を割くのに牛刀を用いるほど過剰であり、遅いということだ。そもそも正規表現ライブラリは柔軟なパターンマッチができるもので正規表現文字列からパターンマッチのためのデータ構造を構築する。そして、std::regex_replaceによる置換はin-placeでは行われない。今回の置換は削除なので、in-placeに処理できるが、汎用的なライブラリであるstd::regexにそれを望むことはできない。

それでも書くとなると、以下のようになる。

bool remove_nico( std::string & s )
{
    std::regex re("25") ;
    std::string out ;
    // s/25//g
    auto end = std::regex_replace( std::back_inserter(out), std::begin(s), std::end(s), re, "" ) ;
    // 置換しなかった
    if ( s.size() == out.size() )
        return false ;

    s = out ;
    return true ;
}

ちなみに、手書きの"25"削除をatcoderに提出すると実行時間は最大のテストケースで5msぐらいだが、regex_replaceを使う実装を提出すると50msぐらいかかる。実に10倍も遅い。remove_nicoを手動でインライン展開して、reとoutをループの外に出して使いまわす付け焼き刃の最適化も試してみたが、実行時間は変わらなかった。その程度の最適化はコンパイラーがやっているらしい。

とはいえ、10倍遅くても制限時間内だからいいといえばいい。B問題程度はさっさと解くためにこうしてもよいが、それならもっと簡単な言語を使ってもよいということだ。

C問題以降は私には解けないのでもっと強い人の解説を参考にしてもらいたい。