2018-01-14

第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問題以降は私には解けないのでもっと強い人の解説を参考にしてもらいたい。

ドワンゴ広告

ドワンゴからの挑戦状本選は2月3日。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2018-01-08

fair use権利を侵害するYouTubeのContent IDと戦うために著作権侵害するゲーム批評家の話

Game Critic Uses Brilliant Workaround For YouTube's Copyright Bullshit

Jim SterlingはYouTubeに動画を投稿するゲーム批評家である。動画によるゲーム批評を行うためには、ゲームの動画を引用する必要がある。しかし、ゲームの動画をYouTubeで引用すると困った問題に巻き込まれる。Content IDだ。

YouTubeではContent IDという仕組みが設けられている。これは、ある動画が著作権者の事前に登録した動画にマッチする場合、その動画に対して著作権者が著作権を主張し、取り下げたり、あるいは広告を出して収入を著作権者に回したりする仕組みだ。

しかし、批評のための引用は各国の法律で「著作権の例外」にあたり、著作権が及ばないと定められている。例えば日本では著作権法の第32条、アメリカ合衆国ではfair use、イギリスではfair dealingにより、著作権の例外であり著作権が及ばないと法的に定められている。ゲームの批評のために必要な範囲の引用には著作権が及ばない。著作権が及ばない以上、当然屈辱的なContent IDマッチによる取り下げや広告収入の横取りは、本来ならば著作権を不当に主張している人間による著作権侵害である。

しかし、Googleは人間が問題に対処しないことで悪名高い企業であり、不当なContent IDマッチの取り下げ要求にはまともに人間が対応しないためにどうしようもない。

さて、Jim Sterlingは収入をPatreon経由で得ており、YouTubeの広告には依存していない。そのため、YouTubeには広告を表示しない設定にしているのだが、ひとたびContent IDにマッチしてしまうと否応なく広告が有効にされてしまうという問題を抱えている。

そんなJim Sterlingが、最近自衛のために行っている行動は、Content IDの仕組みを逆手にとったものだ。上の動画では、任天堂の最近のゲームには新規性がなく過去の成功体験を引きずって使いまわしているだけだという旨の批評を行っている。しかし、動画にはなぜか、何の脈絡もなくMetal Gear Solid V, Grand Theft Auto V, Beyond: Two Soulsといったゲーム動画が使われている。これはなぜか。

Jim Sterlingは過去の自分の動画の中でContent IDにマッチした、既知のContent IDマッチ動画を意図的に使うことによって、動画に複数の大企業のContent IDマッチした著作権主張者を作り出している。複数の著作権主張者が同じ動画に著作権主張をした結果、どの著作権者の主張も認められず、結果として動画には収益横取り広告がつかなくなる。

しかし、その利用方法は正統な批評のための引用ではなく、結果的の著作権侵害ではある。32条、fair use, fair dealingといった著作権の例外の権利を保証させるために、あえて著作権侵害を起こす必要があるとは皮肉なものだ。しかしJim Sterlingによれば、結果的にこれが効果的な方法なのだという。

著作権は誤った考えであり私の生きているうちに世界的に破棄されるだろう。

2018-01-02

Clangをブラウザー上で実行してC++をWebAssemblyにコンパイルして実行するデモ

Clang In Browser

タイトル通り。WebAssemblyにコンパイルされたClangをブラウザー上で実行してC++をWebAssemblyにコンパイルしてブラウザー上で実行するデモ

この有名なトークが現実的になってしまう。核戦争によって滅んだ人類がブラウザーを共通プラットフォームとしてブラウザー上でOSを動かす話。

The Birth & Death of JavaScript