GCJ2017qual AをO(N)で解く

概要

長さNのbit列が与えられる。長さKの連続した列をflipして、全て1になるようにしたい。不可能ならIMPOSSIBLE、可能ならflipする最小数を答える。

略解

左から貪欲に0になっているところからflipする。背理法で証明できる。

largeケースですらなので普通にで解けてしまう。

高速化

flipを一様加算と見る。BITを使えばは自明。もう少し工夫する。

一様加算といえばBITの他にはimos法がある。今回はこれを使う。 imos法は微分した列を足した後に積分（累積和）するという手法である。一様加算の場合、微分した列は両端のみ足し込めば良く長さに依存しない。

しかし、足し合わせた後に逐一累積和を取れば意味がない。そこで、目標とする列も微分することを考える。 目標とする列は全て1である。これを微分すると、100….000となる。

また、最初に与えられた列も微分する必要があるが、足し合わせた後にmod 2を取ると考えると実は1も-1も等価であるためにとなる点を1とすれば良い。 後は、最初だけ1、他は0となるように（微分した）flipをする。

#include <bits/stdc++.h>
using namespace std;

string S;
int K;
vector<bool> vec;
int ans;

void flip(int x){
    vec[x] = vec[x]^1;
    vec[x+K] = vec[x+K]^1;
    ans++;
}

int solve(){
    cin >> S >> K;
    int L = S.size();
    
    ans = 0;
    vec.resize(L+1, false);
    
    vec[0] = S[0] == '+';
    for(int i=1; i<L; i++)
        vec[i] = S[i-1] != S[i];
    
    if(!vec[0]) flip(0);
    
    for(int i=1; i<L-K+1; i++) if(vec[i])
        flip(i);
    
    for(int i=L-K+1; i<L; i++) if(vec[i])
        return -1;
    return ans;
}

int main(){
    int T; cin >> T;
    for(int t=0; t<T; t++){
        cout << "Case #" << t+1 << ": ";
        
        int ans = solve();
        if(ans < 0)
            cout << "IMPOSSIBLE" << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

映像研には手を出すな!がヤベエ

映像研には手を出すな!を読んだ。感想を一言で言えば、「ヤベエ漫画が出て来やがったぜ」。 それ町*1のようなハイコンテクストなギャグを挟みながら、それでいてアツい漫画だった。

まだ読んでない？一話だけならタダで読めるぞ！ spi-net.jp

もしまだこの漫画を読まずにこの記事を読もうとしているなら辞めたほうが良い。こんな良い漫画のネタバレを見てしまうなんて勿体無い。早く本屋に走るかkindleで買え！

読んだか？読んだな！

以下つらつら好きなポイントやら気付きやらを羅列する。

浅草みどり

設定を考えるのが好きで、背景（というより世界観？）を描くのが得意。人物を描くのは得意ではない。 それ町の歩鳥っぽいキャラ。普段アホだけど憎めないやつで、ふとした時に冴えた事を言う。 「きっかけやら環境が整わんと何もできない*2」と主張するように、実は案外ビビリ。 作者の分身。作者はどうやら未来少年コナンが好きらしい。

水崎ツバメ

財閥令嬢。初登場シーン*3ではいけ好かない顔をしておる。 みどりとは対称的に人物（やその動き）を描くのが得意。 いけ好かない奴かと思いきや、みどりと同じ位アホ。

金森さやか

アホ2人のまとめ役。お金の話が好きで美脚（キャラ紹介）。 本作で一番好きなキャラ。

みどりがさやかにアニ研に行こうと誘った際、さやかはすげなく拒否している*4。 しかし、みどりが実際に絵を書いたのを見た途端（牛乳を要求はするけども）、行くことに同意する*5。 どうやらさやかはコイツはやる奴だと認めた相手であれば、そいつに投資してみようと思うタイプであるらしい。 ツバメの絵を見せられた際には、「どうです浅草氏。」とみどりの意見を仰いでいる*6。 この点からも、さやかがみどりを高く評価しているのが分かる。加えて、自分の詳しくない分野であるからきちんと専門家であるみどりの意見を聞く姿勢が良い。また、みどりらを職人として捉えて*7、彼女らが快適に過ごせる様に注力している。

アニ研に入れないなら映像研を作ってしまえなんて言い出すあたり、実はさやかは他の2人に比べて行動力がずば抜けている。面白いから投資してやるという気概は、自分が面白いモノを見たいという実は子供じみた動機に思える。 本作では全編を通して、みどりの妄想が現実を侵食する。いわばこれはごっこ遊びで、その世界に入れるのは少年の心を持っている人間である。にも関わらず、さやかもちゃっかり入っているのだ。ツバメやみどりのアホが際立っているけど、実は一番少年の心を持っているのはさやかかもしれない。

彼女は金が好きというよりも、金の大切さを理解している、という風に感じる。ただ単にがめついというよりは何かをやるためには金が必要という基本的な点（とはいえ高校生でそれをきちんと理解しているのはそう居ないと思う）を理解している。

ツバメがどうして手伝ってくれるのかと聞いた時、さやかは「金の為」と答える*8。 でも、これは方便だろう（みどりとアニ研に行く時にも牛乳を言い訳にしている、金は彼女にとって良い方便なのかもしれない）。 どうせ彼女がこの時考えていたのはこうだ。「なんだか知らんが、面白くなってきやがった」*9

まとめると、彼女は職人を尊敬し、彼らが自由に動けるように奔走する人間である。 彼女から受けるパッと見の印象からは印象からは遠いとても誠実で理想的なリーダー像がそこにある。 そういうキャラを好きになるなという方が無理なのだなぁ。

生徒会

さかき・ソワンデというハーフの書記の子が一番デキるっぽいのが面白い。 「細工は流々仕上げをご覧じろ」なんて言葉、日本人でも知らない人多そうなのにとか考えてた。 人は見かけによらないという話を入れたかったのだろうか。 彼女はさやかと似た人格であると思う。 つまり、自分が認めた人間であれば評価するというタイプ。

上映シーン

カッケエ。面白いのは、みどりが作った世界に生徒たちが引きずり込まれているところ*10。 よくある描写だけど、この作品ではもうちょっと違った趣がある。 先に述べたように、みどりの妄想が現実を侵食するが、それはあくまでも少年の心を持つ人間に対してであったはずである。 そういう世界観の中で、みどりらが作った世界の中に人々を取り込めた。そう考えると、ワクワクしますね。

妄想

金森さやかという人格はどうやって作られたのだろう。少し考えてみた。

さやかはツバメと似たような出自の人間だったら面白いなぁと考えていた。 まず、彼女のリーダーシップだ。 みどりやツバメのように、職人が「こういうリーダーが欲しい」という点に辿り着くことはあるだろう。 しかし、さやかはそういう職人ではない。彼女は何かに特化しているわけではないのだ。 そういう人間がどうやってあのリーダーシップを得たのだろう。 彼女が高校生という若さでその始点を得たのは、幼少期からの環境によるのではないかと考えた。 つまり、彼女の家庭は何かを経営していたのではないだろうか。その家庭で受けた教育により彼女は今の人格を得たのでは無いだろうか。 実は彼女が山奥の財閥だったりしたら面白い。

しかし、彼女は別段金持ちという雰囲気を出していない。 それは、彼女が家に反抗している故ではないか。 ツバメがさやかに「足長いね」と言った時に、さやかは軽く受け流している*11。 さやかはスタイルが良いし、多分化粧をすれば中々に美人だろう（ほんまか？）。 自分の容姿のような親から貰ったモノを使わずにやってやるぜという意志からそういう行動をしているとかだったら面白い。

という様なことを考えていたけど、ツバメは金があるはずなのに部のために金を使おうとしてない、なんでだろう。 なんかそれに対する描写あったっけ。

*1:映像研のみどりはそれ町の歩鳥の匂いを感じる

*2:p8 1コマ目

*3:p8 3コマ目

*4:p7 1コマ目

*5:p9 6,7コマ目

*6:p20 2コマ目

*7:p108 6コマ目

*8:p22 5コマ目

*9:p156

*10:p153

*11:p52 4コマ目

競プロ勢のためのデバッグテクニック

Facebook Hacker Cup Round1の問題をオーバーフローと配列外参照で2問落としてしまい、反省を込めてデバッグテクニックを調べました。

競技勢がやらかすケアレスミスなバグの多くはこの2つだと思うので、この2つのみについて述べていきます。また、僕は普段の実装にMacを使っているので、gccのフリをしたMac仕様Clang（クソ）についても言及します。

オーバーフロー

これは-ftrapvオプションを付けてコンパイルしたファイルを実行すればオーバーフローした瞬間に検知（abort）する事が出来ます。

しかし、どこで死ぬのかがわからずこのままでは使い勝手が悪いので、-g（デバッグ）オプションも付けてコンパイルした後に、gdbで実行すると良いです。

#include <iostream>
using namespace std;
 
int main(){
    int x = 10000000;
    int y = 10000000;
 
    cout << x * y << endl;
}

$ clang++ -ftrapv -g overflow.cpp 
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) r
Starting program: /tmp/a.out 

Program received signal SIGILL, Illegal instruction.
0x00000000004008cf in main () at overflow.cpp:8
8       cout << x * y << endl;

これはUbuntuでビルドした最新のClang++、Mac版Clang++でも動きます。 Ubuntuにもとから入っていたg++では__GI_raiseでSIGQUITを送出して終了した点で終了しました。（これはよく考えたらg++ではなくてgdbがデフォルトでユーザーのプログラムの中まで戻ってくるかどうかというだけかもしれない？あと、No such file or directory.と出ているのがややこしいですが、これは多分gdbのエラーメッセージ。）

$ g++ -ftrapv -g overflow.cpp 
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) r
Starting program: /tmp/a.out 

Program received signal SIGABRT, Aborted.
0x00007ffff74ab418 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54
54  ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.

一応、backtraceをすればどこで死んだかは分かります。

(gdb) bt
#0  0x00007ffff74ab418 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54
#1  0x00007ffff74ad01a in __GI_abort () at abort.c:89
#2  0x00007ffff7842522 in __mulvsi3 () from /lib/x86_64-linux-gnu/libgcc_s.so.1
#3  0x00000000004008b7 in main () at overflow.cpp:8
(gdb) frame 3
#3 0x00000000004008b7 in main () at memory.cpp:8
8              cout << a * b << endl;

Ubuntuにはgdbがデフォルトで入っているので、ICPCでも使えますね。

配列外参照

これはg++とMac版Clang++で対応が若干変わります。

g++

g++の場合、最初に#define _GLIBCXX_DEBUGを書くことで検出出来ます。 最初に書かないと動かないので注意してください。 これは、vectorファイルの中に

#ifdef _GLIBCXX_DEBUG
# include <debug/vector>
#endif

というコードがあるためです。つまり、include前であれば良いですが、誤りを避けるために最初に書いておくことをおすすめします。

#define _GLIBCXX_DEBUG
#include <vector>
using namespace std;

int main(){
    vector<int> a(10);
    for(int i=0; i<100; i++)
        a[i] = 1;
    return 0;
}

例によってgdbを使います。

$ g++ -g memory.cpp 
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) r
Starting program: /tmp/a.out 
/usr/include/c++/5/debug/vector:409:error: attempt to subscript container 
    with out-of-bounds index 10, but container only holds 10 elements.

Objects involved in the operation:
sequence "this" @ 0x0x7fffffffdd00 {
  type = NSt7__debug6vectorIiSaIiEEE;
}

Program received signal SIGABRT, Aborted.
0x00007ffff74ab428 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54
54  ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) bt
#0  0x00007ffff74ab428 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54
#1  0x00007ffff74ad02a in __GI_abort () at abort.c:89
#2  0x00007ffff7b0af95 in __gnu_debug::_Error_formatter::_M_error() const () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#3  0x000000000040110c in std::__debug::vector<int, std::allocator<int> >::operator[] (this=0x7fffffffdd00, __n=10) at /usr/include/c++/5/debug/vector:409
#4  0x0000000000400ba8 in main () at memory.cpp:8
(gdb) 

Mac版Clang++

Mac版Clangの場合、_GLIBCXX_DEBUGの代わりに_LIBCPP_DEBUGを用います。 _LIBCPP_DEBUGの設定した値によってデバッグレベルが変わるらしく、0か1をdefineすれば良いのですが、何故か1を指定するとバグりました。

#define _LIBCPP_DEBUG 0
#include <vector>
using namespace std;

int main(){
    vector<int> a(10);
    for(int i=0; i<100; i++)
        a[i] = 1;
    return 0;
}

$ g++ memory.cpp
$ ./a.out
vector[] index out of bouns
Abort trap: 6

ここまではICPCで使うことも想定して電子的な準備に該当しない領域でどこまで出来るのか考えました

valgrindを使う方法

Facebook Hacker CupやGoogle Code Jam、または一般のプログラミングに関してはこれが一番やりやすいかもしれません。 -gオプションを付けてコンパイルした後

valgrind ./a.out

とするだけで詳細な結果が出てきます。

$ g++ -g -O0 test.cpp 
$ valgrind ./a.out
==1120== Memcheck, a memory error detector
==1120== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==1120== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==1120== Command: ./a.out
==1120== 
==1120== Invalid write of size 4
==1120==    at 0x10000156D: main (test.cpp:7)
==1120==  Address 0x100a8e068 is 0 bytes after a block of size 40 alloc'd
==1120==    at 0x10000A681: malloc (in /usr/local/Cellar/valgrind/3.12.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==1120==    by 0x10004F7DD: operator new(unsigned long) (in /usr/lib/libc++.1.dylib)
==1120==    by 0x10000179E: std::__1::vector<int, std::__1::allocator<int> >::allocate(unsigned long) (new:156)
==1120==    by 0x1000016B1: std::__1::vector<int, std::__1::allocator<int> >::vector(unsigned long) (vector:1070)
==1120==    by 0x1000015CC: std::__1::vector<int, std::__1::allocator<int> >::vector(unsigned long) (vector:1073)
==1120==    by 0x10000152E: main (test.cpp:5)
==1120== 
==1120== 
==1120== HEAP SUMMARY:
==1120==     in use at exit: 22,153 bytes in 191 blocks
==1120==   total heap usage: 258 allocs, 67 frees, 27,993 bytes allocated
==1120== 
==1120== LEAK SUMMARY:
==1120==    definitely lost: 0 bytes in 0 blocks
==1120==    indirectly lost: 0 bytes in 0 blocks
==1120==      possibly lost: 0 bytes in 0 blocks
==1120==    still reachable: 0 bytes in 0 blocks
==1120==         suppressed: 22,153 bytes in 191 blocks
==1120== 
==1120== For counts of detected and suppressed errors, rerun with: -v
==1120== ERROR SUMMARY: 90 errors from 1 contexts (suppressed: 0 from 0)

追記

オーバーフロー時の挙動がMacとUbuntuで異なっていたのはどうやらftrapvの実装の違いのせいのようです

@aki33524 clangはftrapvの実装にundefinedなオペコードぶち込んで対応してるらしい https://t.co/3Yq4hde8JU
" -ftrapv flag will cause clang to intenionally insert ud2"

— るくす (@RKX1209) 2017年1月16日

tf-idfを使ったDbpediaの型推定

卒論が上手く行かないので逃避していたらまぁまぁ良さそうなので公開しておく。

前提

DbpediaとはWikipediaを元に半自動で変換したLODである。

各リソース（記事）にはclass（人とか政治家とか虫とか）が定義されたりされなかったりする。

全リソースの3割ほどにclassが定義されておらず、これを推定する需要がある。

この前のISWCのデモセッションでDbpediaの型（class）推定をしようとしている研究があったのが心に残っていた（全然手法違うけど）。

卒論でデータを眺めていたらふとtf-idfで上手く行くように見えたので試してみた。
というかこれをもっと筋良くした研究が既にあると思うけどパッと出てこなかった。Dbpediaの自動変換の過程で似たようなことをやっている気がする。詳しい人教えてください。

アイデア

基本的なアイデアとしては
「A is writer of B」
という関係があれば、Aはおそらく作家だろうしBはおそらく本だろうという推定が出来るというところ。

つまり、リソース（Wikipediaの記事1つに該当）間のプロパティ（Wikipedia間のリンクに相当、ただのリンクではなく種類がある）
を特徴量として扱う。

tf-idfについては無限に資料があるので詳しく語らないが
「リソースを文書とする」
「（方向、プロパティ）の組を語彙とする」
というアイデアをtf-idfに適用した。

また、2つの文書間の類似度はcos類似度によって表される。
そこで、あるリソースAと他の任意のリソースBのcos類似度を計算して、Bにclassが定義されていれば類似度をclassの推定値として重畳する。

この時、足し合わせたあとにそもそもそのclassを持つリソースがいくつあるかで除したり、推移的なtype定義を用いたりするとよい。

最終的に、最も推定値の大きなclassが推定結果である。

所感

簡単な割に結構上手く行ってくれる。
例えばバラク・オバマにはclassが定義されていない。これを推定するときちんとpolitician - Wikidataと出てきた。

ただ、当然だがプロパティ関係が殆ど存在していないようなリソースは推定を誤る。恐竜が「虫」に推定されたりしていた。
他には、1735年などの年度シリーズが殆ど「場所」として推定されていた。
これは日本語版Dbpediaのデータが悪いようで、birthPlaceとして人との間に関係が定義されていた（birthTime？的なものにしてくれ……）。

これを発展させるとすればプロパティの種類だけではなく、その先に存在しているリソースのclassなども推定すべきだろう。
「A is writer of <instance of Movie>」であれば、Aは作家は作家でも監督？とかそういった推定が出来るかもしれない。

結局これは辺に種類が付いた有向グラフのクラスタリング問題に帰着できそうで、何か機械学習で上手く出来たりするのかなぁというところ。

コードはこれです。
GitHub - aki33524/typeprediction