ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

rogy14で卒業旅行に行ってきたっぽい！

rogy

rogy14のメンバーで卒業旅行に行ってきた
日程 : 3/14 ~ 3/16
場所 : 下呂温泉
宿 : 湯本館
メンバー : 夕天 工場長 ○ー○○ らりお けり sekiseki ラスト ymduu aktz たくあん まいん Rin Mizuho おかゆ りあん ちゃっく
ハッシュタグ : #rogy14卒業旅行

1日目

6:20 起床
急いで旅支度
6:40 出家
集合場所に向かっていたら大量の遅刻報告が....
7:00 自由が丘着
集合時間に集合場所に行ったら3,4人しかいなかった。バグか?
レンタカーの手続きしたりして待ってた
8:00 出発
運転するぽい。
車内に響渡るオタクソング♫
自由が丘を出た直後に夕天号とちゃっく号の行く方向が逆になる。
とりあえず談合坂へ向かう。
環八がめちゃくちゃ混んでた。
10:15 談合坂SA
朝食を食べた。談合坂あんぱん、あんまり美味しくない。大岡山あんぱんの勝利。
12:30? 駒ケ岳SA
とくにやることなし
相変わらず車内に響き渡るオタクソング♫
14:30くらい? 中津川
夕天たちは異常速度で下呂に向かってた。
僕らと工場長は途中でお昼ご飯。
どて煮丼美味しかった。

~ これ以降時刻怪しい ~
下呂着。
僕はりあん、sekiseki、たくあんと小川屋というホテルの温泉に入りに行った。
そのあと周辺散策をしたり...

夕食を食べた後はだらだら....
個人的に旅行先で夜散歩するのはめっちゃ好き


2日目

朝食の後に二度寝して起きたら宿には僕とりあんしか残ってなかった。情報系は朝弱すぎる問題。
午前中は合掌村へ....

五平餅を食べた。めっちゃ美味しい。

午後は車で飛騨高山の方へ...
飛騨古川駅で君の名はの聖地巡礼



君の名はの広告とかまだ結構あった

ラボ土産に「聖地の酒」というものを買った。
君の名はの映画に出てくる入れ物に入ってるやつは高かったので買えなかったが、その隣に売られてる聖地の酒が安く見えて商売上手だな〜と思ったり
(写真撮り忘れたのでりあんのツイートのやつを...)

下呂に戻ってからは白鷺の湯へ...
sekisekiは一人で高山に行ったがバスか電車を逃して夕食の時間に帰ってこれずorz....(食べれはした)

3日目

最終日。
来るときに予想より時間がかかったので11時ごろには出発。
18時くらいには東京につけたので渋滞は回避できたので楽だった。
ご飯食べたり、適当な駅によって人を下ろしながらレンタカー返却して21時。

さいごに

とっても楽しい旅行だった!
またM2のときにみんなで行きたいね！
企画してくれた人ありがとうございます！

「君の名は。」Blu-rayスタンダード・エディション

「君の名は。」Blu-rayスタンダード・エディション

おとな旅プレミアム 飛騨高山・白川郷 飛騨古川・下呂温泉 (おとな旅PREMIUM)

おとな旅プレミアム 飛騨高山・白川郷 飛騨古川・下呂温泉 (おとな旅PREMIUM)

Codeforces #462 Div2C Div1A A Twisty Movement

Codeforces 競技プログラミング

codeforces.com

問題概要

長さnの数列aが与えられる。
数列aの要素は1,2のどちらか。
区間[l,r](l,rは自由)を1度だけ反転する。
反転した後の数列aにおいて最長の非減少数列の長さを求めよ
(非減少数列は p_1 < p_2 < ... < p_k に対してa_{p_1} \leq a_{p_2} \leq ... \leq a_{p_k}を満たすような数列)

解法

この問題は O(N) , O(N^2)解法が存在する

O(N^2)解法

1. Segment Treeで区間に含まれる2(もしくは1)の個数を管理
2. DPで区間[l,r)に含まれる最長の2....21....1(非連続でもよい)を計算する。この2...21...1は[l,r)をひっくり返すと区間[l,r)における最長の非減少数列になる
3. 各l,rに対して[0,l)に含まれる1の数 + [l,r)の最長の2...21...1列 + [r,N)に含まれる2の数を計算する
この計算を行えば3で求めた値の最大値を出力すればよい

これはO(N^2logN)だが、SegmentTreeで管理している部分を累積和とかで管理すればO(N^2)になる。

struct RSQ{
    public:
        int n;
        vector<int> data;
        RSQ(int n_){
            n = 1;
            while(n<n_) n*=2;
            data.resize(2*n-1);
            for(int i=0;i<2*n-1;i++) data[i]=0;
        }
        void update(int k,int a){
            k+=n-1;
            data[k]=a;
            while(k>0){
                k=(k-1)/2;
                data[k]=data[k*2+1]+data[k*2+2];
            }
        }
        int query(int a,int b,int k,int l,int r){
            if(r<=a or b<=l) return 0;
            if(a<=l and r<=b) return data[k];
            else return query(a,b,k*2+1,l,(l+r)/2)+query(a,b,k*2+2,(l+r)/2,r);
        }
        int query(int a,int b){ return query(a,b,0,0,n); }
};

int main(){
    int N; cin >> N;
    RSQ rsq(N);
    vector<int> a(N);
    rep(i,N){
        cin >> a[i];
        a[i]--;
        rsq.update(i,a[i]);
    }

    vector<vector<int>> dp(N+10,vector<int>(N+10,0));
    rep(i,N+1) dp[i][i+1] = 1;

    for(int len=0;len<=N;len++){
        for(int l=0;l<N;l++){
            int r=l+len;
            if(l+1<N and l<N and l+1<=r and r<=N){
                if(a[l] == 1) chmax(dp[l][r],dp[l+1][r]+1);
                else chmax(dp[l][r],dp[l+1][r]);
            }
            if(r-1>=0 and r-1<N and l<=r-1){
                if(a[r-1] == 0) chmax(dp[l][r],dp[l][r-1]+1);
                else chmax(dp[l][r],dp[l][r-1]);
            }
        }
    }

    ll ans = -1;
    for(int l=0;l<N;l++){
        for(int r=l;r<=N;r++){
            ll tmp = l-rsq.query(0,l)+dp[l][r]+rsq.query(r,N);
            ans = max<ll>(ans,tmp);
        }
    }
    cout<< ans << endl;
}

O(N)解法

数列aを4つの領域に分割する(領域0,領域1,領域2,領域3とする)。
"領域0に含まれる1の個数 + 領域1に含まれる2の個数 + 領域2に含まれる1の個数 + 領域3に含まれる2の個数"を最大化すればよい。
この領域1と領域2の範囲を反転させることで領域0,領域2の反転,領域1の反転,領域3の順になり、領域0,2から1を、領域1,3から2を選択することで最長の1....12....2を作れる。
具体的な実装は
dp[i][j] := a[i]が領域jに含まれる時、a[i]までで、領域0から領域jまでに最大でいくつ"領域に対応した数字(1,2)"が含まれるか
をもったdpをすれば良い。
更新作業は
dp[i][j]に対して、a[i-1]がどの領域に含まれ、a[i]の数字がなにであるかを考えればよいので、
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + (a[i] == "領域に対応する値")
となる

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N) cin >> a[i];

    vector<vector<int>> dp(N+10,vector<int>(4,0));
    if(a[0]==1){
        dp[0][0] = dp[0][2] = 1;
        dp[0][1] = dp[0][3] = 0;
    }else if(a[0]==2){
        dp[0][0] = dp[0][2] = 0;
        dp[0][1] = dp[0][3] = 1;
    }
    for(int i=1;i<N;i++){
        for(int j=0;j<4;j++){
            if(j==0 or j==2){
                if(a[i]==1){
                    chmax(dp[i][j],dp[i-1][j]+1);
                    if(j-1>=0) chmax(dp[i][j],dp[i-1][j-1]+1);
                }else if(a[i]==2){
                    chmax(dp[i][j],dp[i-1][j]);
                    if(j-1>=0) chmax(dp[i][j],dp[i-1][j-1]);
                }
            }else if(j==1 or j==3){
                if(a[i]==1){
                    chmax(dp[i][j],dp[i-1][j]);
                    chmax(dp[i][j],dp[i-1][j-1]);
                }else if(a[i]==2){
                    chmax(dp[i][j],dp[i-1][j]+1);
                    chmax(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
    }

    ll ans = -1;
    rep(i,4){
        chmax(ans,dp[N-1][i]);
    }
    cout << ans << endl;
}

感想

この問題、Div2Cにしては難しい気がするけどO(N^2)解法なら思いつきたかった....
結構良問だと思うけどどうだろう?

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

[改訂第3版]C++ポケットリファレンス (POCKET REFERENCE)

[改訂第3版]C++ポケットリファレンス (POCKET REFERENCE)

江添亮の詳説C++17

江添亮の詳説C++17

SRM723Div1Easy TopXorer

競技プログラミング Topcoder

概要

要素数nの配列xが与えられる。
0 \leq i \lt nに対して 0 \leq a[i] \leq x[i]を満たすような配列aに対して
a[0] xor\ ... xor\ a[n-1]の最大値を求めよ

解法

基本的に最大の数の最上位bitを1にして、残った数でそれ以下のbitを1にしていくみたいな気持ち。例えば1100,0100があれば1100->1100,0100->0011にすれば排他的論理和は1111になって最大。
これをするために、左のbitから確定していき、もし左からi番目のbitが1である要素がxに複数あった場合は1つをi番目のbitを1にし、別の要素をi番目のbitを0にしてi+1番目以降を全て1にすれば排他的論理和が最大になる

class TopXorer {
    public:
    int maximalRating(vector <int> x) { // x[i] <= 10^9
        int n = x.size();   // n <= 50
        sort(all(x));
        reverse(all(x));

        vector<int> cnt(40,0);
        for(int i=0;i<n;i++){
            rep(j,31) if(x[i] & (1 << j)) cnt[j]++;
        }

        for(int i=31;i>=0;i--){
            if(cnt[i] > 1){
                cnt[i]--;
                for(int j=0;j<i;j++){
                    cnt[j]++;
                }
                break;
            }
        }

        int ans = 0;
        for(int i=0;i<32;i++){
            if(cnt[i] > 0) ans |= (1 << i);
        }

        //rep(i,n){
        //    cout << x[i] << "\t" << static_cast<bitset<11>>(x[i]) << endl;
        //}
        return ans;
    }
};

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド

IQ1のICPC2017 アジア地区ナコーンパトム大会参加記

競技プログラミング 感想 ICPC

2017/12/19~25でICPC2017 アジア地区ナコンパトム大会に参加してきました。
チームIQ1はchakku(夕立),kuwa(吹雪),tjake(睦月),shimomireコーチ(提督)の4人で参加しました。

12/19 日本→バンコク

羽田から出発
羽田に早くついたので朝食を食べてた。
吹雪ちゃんがパスポートを拾う。中を見たらコーチの提督さんのだった。笑う。
持ち物検査で夕立がひっかかって時間を溶かす。カッターを没収される。

飛行機
日本映画は銀魂と3月のらいおんとあとひとつなんかしかなかった。
着陸時に酔って死ぬ。
バンコクに着く。
夕食がタイの味がする。あまり美味しくない。パイナップルは美味しいのでパイナップルばっかり食べる。

12/20 バンコク観光→ナコーンパトム

ワット・ポーに行く。
ワット・ポーからホテルまで歩いたら地獄になった。
多少ぼったくられても日本円にしたら数百円なのでタクシー使うべき。
そのあとナコーンパトムへ。
吹雪ちゃんと睦月ちゃんの部屋はダブルベッドだった。笑った。


夕食。
吹雪ちゃんと睦月ちゃんが天ぷらうどん頼んだらうどんがなくて笑った。

夕食後。
タイで郊外なので星でも見えないかなって思いながら夜外に出る。
提督さんが「こういう暗いところ野犬でそう」って言った直後に目の前に野犬が現れる。
吹雪ちゃん「いるやん！！！」。全員で撤退。
(タイの野犬は狂犬病を持っている可能性が高く噛まれると死亡らしいです。生き残ったら論文に乗れるらしいです。IF72の論文に掲載されるレベルらしいです。)

12/21 ICPCナコーンパトム大会1日目

迎えの車が来ない。焦る。
現地で農工,名工チームと会う。日本からは農工,名工,東工と工業の文字を掲げる大学が集まった。
Hecさんに「ファンなのでサインください」と言って出張書類にサインをもらう

オープニングセレモニー。オープニングムービーがかっこよすぎる。

Practice
夕立がAを担当するはずが問題を正しく理解できず死亡Ω＼ζ°)ﾁｰﾝ
Bを吹雪ちゃんが解く。
Cは睦月ちゃんが解いて実装するがバグる.3人でデバッグするが間に合わず。
Cの解法は上位2つを記録しておくみたいなので蟻本に似たようなのをダイクストラでやってたなぁって気持ちになる。

農工,名工チームと雑談した後ホテルに帰る。

12/22 ICPC コンテスト当日

相変わらず朝7:45に迎えのバス

コンテストまではロビーのソファーで寝てた(人の目を気にしろ)

コンテスト。
問題が紙でしか配られない。
夕立はA~D担当という予定
A問題は簡単な数式の最大値求めるだけで簡単に思えたが、30分以上経ってもAC数が少ないので自分の思考が間違ってるのではないかという不安で実装できない。途中でBを読むことにする。
その間に吹雪ちゃんはHを提出するがTLE.精度と時間が微妙に足らないらしい。
C,Gの提出ACが多いので吹雪ちゃんがC問題,G問題をやる。
この後の動きをあまり覚えていない。
1.5時間くらいでA問題を最初の考えのまま実装する。有理数クラスを作ったがオーバーフローを避けられないのでdoubleで実装しなおしたりしてテストケースは通る。しかしどうしても問題の簡単さに対してAC数が少なく変なケースがあるのではと思ったりして提出しない。
開始から3時間くらいしてAをそのまま出してみたらACしてしまい無駄な時間を過ごしたことにめちゃくちゃ後悔する。

途中でコンテストがいきなり停止する。夕立はてっきり休憩時間だと思いこんで「休憩があるコンテスト親切っぽい〜」とか適当なことを言う。

再開。
この時点で睦月ちゃんが2問くらい通してる(1問だったかも).
次に夕立はLをやる。ユニークな数字で数列を2つに分けていくと良さそうと思ったがどうしても計算量が足らない。試しに提出してみてもTLE。
吹雪ちゃんと睦月ちゃんはE,Hをやるが通らず。
夕立はLの計算量減らさなくても適切に枝刈りしてけば悪いケースほど早く刈られるのではという仮説を立てて適当に実装したらTLEがWAになり轟沈。

結果的に吹雪ちゃんと睦月ちゃんがサンプルさえ理解できないと言っていたE問題はclarを見たら問題が変更されていた。
吹雪ちゃんと睦月ちゃんブチギレ。
H問題はbtkさんがfloat128で通ったと言っていた。笑う(笑えない)。
L問題はマージテクの逆と聞いた。天才か? 正直想定解法他にあるのではと思っているがわからない。誰か教えてほしい。kyuridenamidaさんの解法が想定解法っぽい?
https://twitter.com/kyuridenamida/status/944239703716270080

ちなみにLは過去に全く同じ問題が出題されているらしい。ウケる。
問題が紙でしか配られないから睦月ちゃんが100行くらいのテストケース手打ちしてるのは面白かった

IQ1は15位でWFは遠い....悲しい...

エンディングムービーめっちゃかっこよかった。
タイの剣とか棒とかトンファーとか持った人たちが戦う演舞見た。めっちゃカッコ良かったので夕立も剣士として生きていこうか考え始める。

そのあとコンサートに行ったが爆睡して記憶なし。

夜にお腹がすいて提督さんと買い出しに行ったら7匹の野犬と遭遇。そのうち1匹がついてきてビビる。狂犬病は一発で逝けるらしいので死が形を持ってついてきた感じ
買い出しから帰って飲んだビールはあまり美味しくなかった。

12/23 ICPC旅行

ICPCに参加した人たちで日帰り旅行。nocowさんと一緒に回ったりしていた.
鐘も叩いたので煩悩が消えた


旅行解散後にタイマッサージを受けたらめちゃくちゃ痛かった。
夜は屋台で焼肉
衛生的にはあまり良くなさそうな気はしたが問題なかった

12/24 バンコクへ移動

バンコクへ移動した。
コンテストまでは体調崩さないように日本的なもの食べてたが思い切ってトムヤンクンとか食べた。口に合わない。

ボートに乗って遊んだりしてた。夜は一風堂食べた。美味しい....
ミスドも食べたけどミスドは日本のほうが美味しい。

12/25 帰国

東京寒い。

感想

来年は睦月ちゃんは新しい艦娘(未定)になるので現在のチームIQ1で参加するコンテストとしてはおそらく最後のコンテストだった。ちょっと消化不良感はあるがそれでも楽しかった。
やはりWFを狙うには修行不足(特に僕はチームのマスコットをしていたので).


来年までに修行をする必要があるが東工大はまず国内予選を通過するのが難しい....頑張りタイ

D17　地球の歩き方　タイ　2018?2019

D17　地球の歩き方　タイ　2018?2019

IQ1の振り返り

この記事は
IQが1 Advent Calendar 2017 - Adventar
の25日目の記事です。
メリークリスマス！！今年のクリスマスはICPCでタイです。

IQが1アドベントカレンダーの最終日として2017年のIQ1を振り返ろうと思います。
ホントはICPC2017タイ大会の記録でも書こうかとおもったのですがこちらのほうが25日目っぽいかなということで...

IQ1とは

高IQ集団メンサとかいうやつらがいるなら低IQ集団IQ1がいてもよくない?
という気持ちで名乗ってる。自らがIQ1だと思う人たち名乗ってくれ。
(わりと疑問なんだけど高IQ集団の人たちってどんな気持ちで「高IQ集団に所属してます」っていうんだ?誇らしいのか?)

CTF

どこかでIQ1という一人チームをつくって参加した気がするがなんだったかな...記憶がない...
CTFの勉強もしたかったがスマブラでIQが溶けててできなかった。

競技プログラミング

snackdownに葦くんとIQ1というチームを作って参加。日本時間では異常時間でクソ辛かったことしか覚えていない。。結果は予選で敗退。

ICPCはこれまでに記事にしたとおりkuwaさんとtjakeさんとIQ1というチームを組んで参加した。
去年はtjakeさんと組んでいたがもう一人が抜けたのでkuwaさんを勧誘するまで何人か断られて辛かった。国内予選は通過したが,アジア地区はつくば大会とナコンパトム大会で14,15位。通過できず。
tjakeさんは今年で出場権がなくなるので新たなるIQ1の睦月ちゃんを勧誘しなくてはならない。

アドベントカレンダー

これが１番書きたかったこと！！
IQが1アドベントカレンダーに参加してくれたみなさん、IQが高い記事もあったけど毎日楽しく読ませてもらいました！！ありがとうございます！
どんな適当なことを書いてもIQが1という免罪符を振りかざしたら許されそうと意味で参加しやすいと思ってくれたら嬉しい....
なんか最初に冗談で真面目な記事を投下したら真面目に乗ってきてくれた人が多かった！！！すみません...
個人的に特に好きだったのは1億円の機械を破壊したかもめさんの
IQ1と謝罪行脚
です.1億円の機械破壊はインパクトでかすぎる...
他にもhadroriさんの
私のIQを1にしたものたち - hadrori.jp
はIQ1感が高い。

みなさんIQ1のはずなのに遅刻者がでなかったことに驚いた。この記事が最初で最後の遅刻者にならないことを祈る。

今年やりたかったけどやれなかったこと

IQが1Tシャツ,パーカーの作成。
これはやれなかった理由が「デザインがめんどくなった」「欲しい人に受け渡すのがめんどくさそうだった」です。気が向いたらやります。
デザインはりあんが上げてたので受け渡しだけなんですが正直めんどいので催促されまくったらやるかもくらいです。
コミケで売る案とかもあったのですが売れる気がしないのでやめました。

今年やらないといけなかったのにやらなかったこと

卒論。死んだ。

ICPC2017 アジア地区つくば大会に参加してきたんだよ

競技プログラミング ICPC 感想

12/16~18で行われたICPC2017 アジア地区つくば大会に参加してきました。
大会にはtjakeさん(睦月ちゃん),kuwaさん(吹雪ちゃん)とchakku(夕立)でチームIQ1として参加してきました。

12/16 エクスカーションと歓迎会

エクスカーションはJAXAに行く。午前の部と午後の部があるらしいが東京近郊に住んでいる人は午前になる?
7:30 起床 (つらい)
初めてのつくばエクスプレス。とかどうでもいいがとにかく遠い。誰だ「つくばはつくばエクスプレスがあるから近い」とか言ったやつは!!
北千住でAshurとmonmanと遭遇。
10:16 つくば着
つくば駅でrianとtjakeさんと遭遇。なんかバスに乗ってJAXAに行った。

JAXAでラボにお土産を買う。
JAXA離脱。

つくばカピオに到着。受付登録をして会場に入ったらコーチのshimomireさんの名札とかを貰って先に入場してしまいshimomireさんが入れなくなる。
PracticeでIQ1 clarを投げる.「自分たちのPenを使っていいですか」とか....

懇親会に行く。誰かが紹介喋ってくれるだろうと全員が思っていたのにマイクを受け取ったのが失敗。

宿へ行く。大浴場が壊れてて風呂に入ったらほぼ水だった。この季節に水風呂は勘弁してくれ。

12/17 コンテスト当日

7:00 起床 (つらい)
9:30 コンテスト開始

担当
ADEF 夕立
BGHI 吹雪
CJK 睦月

ここから結構時系列おかしくなってる(記憶があやふや)。

AはDPやるだけ。Bは吹雪ちゃんが辛そうにしていた。Cは睦月ちゃんが誤読?してサンプルが理解できないらしく代わりに読んだ。
吹雪ちゃんがBをAC。
睦月ちゃんがCを実装。
Dは見た瞬間に辛そうなオーラが漂っていたのでパス。
夕立はEを読み解ける気はしてた(これは気がしただけだった)。吹雪ちゃんは気がついたらGHIあたりを読んでいた。
夕立がFを読もうとするが問題文が理解できなくて吹雪ちゃんに読んでもらう。ふと横をみたら睦月ちゃんが画面に中指を立てていた。
睦月ちゃんがCをAC。このあたりで1時間くらい経過。
僕はEを実装。サンプルは通るが嫌な予感がしていることを伝えたら吹雪ちゃんからストップがでた。Standingsを見てもEはそんな簡単に通らなさそうなので再考察。結果的にはO(N^2)かかっているのでTLEをするだろうことに気がつく。
K問題も読んだが,「辺の数が頂点数+15?」の制約をどうすればいいかわからないのと順位表的に解くべきでないと判断して放置。
Eはわからないので睦月ちゃんにお願いし、夕立はFを考えたり吹雪ちゃんとIを考えたり。
睦月ちゃんがEで停止しちゃっているので一旦担当問題の変更をする。睦月ちゃんと吹雪ちゃんがIをやり夕立がF(とE)を考える。
気がついたらIが通ってた。順位表を確認したらGが結構通されていた。Gはやるべきでないと判断があったので手を出さなかったが解くことに変更。よく考えたら平面にするだけ。ただ対応する平面が特定するのがめんどくさそうだなって思ってたら吹雪ちゃんが周期性があるので大丈夫というので実装をお願いする。夕立がEを考えて,睦月ちゃんがFを考えてたら睦月ちゃんへの問題の伝達をミスっていることが分かった。
吹雪ちゃんがGを通し,吹雪ちゃんと睦月ちゃんでFを夕立がEを考える。
Fの考察が終了したらしいが、ライブラリを印刷してこなかったので睦月ちゃんが実装を辛そうにしていた。
吹雪ちゃんがEの考察に入り、一応それっぽい解法を考えたので夕立は紙コーディング。
睦月ちゃんが実装終了したがpython3で提出したらTLEした。python2はpypyで実行されるのでpython2に書き直して提出するとRuntime Errorが出てしまう。
この時点で残り20分。夕立のE実装と睦月ちゃんがC++で書き直すのどちらがいいか考えた結果夕立がEの実装をする。
サンプルは通ったがWAを出してしまう。実装ミスを疑って入るが考察が間違っている可能性もありどうしようもなくなっているあいだにコンテスト終了。

結果ABCGIの5完で14位。

f:id:chakku000:20171218212522p:plain
懇親会が開かれる。

IBMさんから企業賞を頂いた。タンブラーだった。これはコップとして使うものなのか水筒として使うものなのかわからないがまあいいか...
いろんな人と話せた。楽しかった。

帰宅する。つくば→北千住だけでもめっちゃ遠いのに北千住からまた乗り換えして家まででとても遠いので疲れた。

12/18 企業見学

10:00 起床 (遅刻を確信)
10:20 集合時間のはずだが布団からでれず
確実に遅刻だがつくばエクスプレスが遅れているらしいのでセーフということにする。
午前はIndeed。高いところからの眺めが良かった。
お昼に1階でサーロインステーキ食べた。美味しかった。写真とりわすれたことを後悔。
午後はLINE。JKラインあるあるが面白かった。高いところからの眺めが良かった。

全体

コンテストは僕がEが解ける問題だと思いこみ(実際強い人なら解けるだろうが)Eをやり続けていたのはあまりよくない気がする。
あと問題の伝達をミスってtjakeさんが誤解したままずっと考察していたのは失敗だった。
このチームにしては珍しく蟻本とTLE本を持ってきた。
ライブラリは持っているなら印刷して持ち込んだほうがよい。
チーム全体の動きとしては詰まったら交代したりいい感じに相談しながら解けたので良かったのでは?

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド

Aho-Corasickに動的にキーワードを追加する

プログラミング

この記事はIQが1Advent Calendarの1日目の記事になります.
「起床時間とか就寝時間が1日目の記事になる」と言っていましたが,ギリギリ実装が間に合った(バグってるかもしれないが)ので起床時間と就寝時間はやめて文字列照合アルゴリズムについて紹介することにしました.
IQ1でもわかるように書くつもりです(これは嘘でIQ1なのでまともな文章が書けない)
(AhoなのでIQ1と指摘を受けました. IQ1はAhoですがAhoさんはwikiを見てもわかるとおりすごい人です.IQが異常に高そうです)

Aho-Corasickについて

複数のキーワードに対する文字列照合アルゴリズムとしてAho-Corasickというものがある.
Aho-Corasickについては Alfred V.Aho and Margaret J.Corasick Bell Laboratories "Efficient String Matching: An Aid to Bibliographic Search"という論文にかかれている.
このキーワード群を静的に構築する方法は下のブログに書いてある.
d.hatena.ne.jp
これのC++の実装はalgoogle.
algoogle.hadrori.jp

簡単説明するとTrieを構築した後にTrieでの検索に失敗した際の遷移関数を定義することで効率的に文字列照合を行うというものである.

このブログではキーワードを動的に追加する方法を紹介する.

キーワードの動的な追加方法

共立出版からでている「情報検索アルゴリズム」を参考に...

言葉の定義

goto関数 : 検索に失敗しない場合の遷移
failure関数 : 検索に失敗した際の遷移

この関数については上のブログでも定義されてる...(そっち見たほうがいい)
Aho-Corasickはこのfailure関数を幅優先探索で構築する.

これを動的に行う場合,更新による影響が及ぶ部分だけを更新すればよい.
更新による影響が及ぶ範囲というのは,新しく追加された部分にfailure関数が到達する部分である(これによりoutput関数も更新されるので).
下の図ではノード9,10に相当する.

これを動的に行うには,2つの段階が必要.
1. 追加するキーワードに対応するノードを作成し,追加されたノードのfailure関数とoutput関数を更新する
2. 既存のグラフのfailure関数とoutput関数を更新する

例えば...
既に構築されているキーワード群は { "ab", "abcde" , "bc" , "bab" , "d"}とし,新しく "bcde"を追加するとします

1ステップで赤色の更新を, 2ステップで緑色の更新を行います(output関数の更新は省略しました)
f:id:chakku000:20171201003835p:plain

ステップ1

赤いノードの追加 : Trieと同様なので省略
赤いfailure関数の追加
f:id:chakku000:20171201004809p:plain
node1->node2はfailure関数を,赤い線は追加されるnode2->node4というfailure関数を意味する.
薄い水色の部分は同じ文字の並びを意味する.

上の図の関係を見つければ,赤い辺をfailure関数として定めることができる.(多分ここが１番重要.ステップ2もこの考え方)

ステップ2

緑のノードの追加.
ここでも2つめの図と同じような考察をする.
例えば1つめの図のノード8のfailure関数は4を指す(f(8) = 4) .
そうすると
8 <-> node1
4 <-> node3
9 <-> node2
11 <-> node4
の対応が見え,図1における 9 -> 11 (つまり図2におけるnode2->node4)を貼ることができる.

図1においてこれを行うためには ノード4がノード8のfailure遷移先であることをノード4は知っている必要がある.そのためfailure関数の逆関数,逆failure関数も保持しておく必要がある.

ステップ2は繰り返し適用することで更新が必要な状態は全て更新される.
この繰り返し更新するのはqueueを用いて行えばよい

実装

C++における実装. addが動的にキーワードを追加する部分.
それ以外ははどろりさんの実装を真似ている.

class AhoCorasick{
    private:
        const int nodeSize = 30;
    public:
        vector<AhoCorasick*> nodes;
        AhoCorasick* failure;
        set<AhoCorasick*> rev_failure;
        vector<int> matched;    // 対応ノードにpattern[i]がマッチした
        vector<string> pattern;
        AhoCorasick() : nodes(nodeSize),failure(nullptr){
            for(int i=0;i<nodeSize;i++) nodes[i] = nullptr;
        }
        void rootinit(){
            for(int i=0;i<nodeSize;i++) nodes[i] = this;
        }

        // 静的に追加(from algoogle)
        void insert(const vector<string> pattern_){
            pattern = pattern_;
            // Trie構築
            AhoCorasick *r = this;
            failure = this;
            rev_failure.insert(this);
            for(int i=0;i<pattern.size();i++){
                r = this;
                for(int j=0;j<pattern[i].size();j++){
                    int c = pattern[i][j]-'a';
                    if(!r->nodes[c]) r->nodes[c] = new AhoCorasick;
                    r = r->nodes[c];
                }
                r->matched.push_back(i);
            }

            // 辺生成
            queue<AhoCorasick*> que;
            for(int i=0;i<nodeSize;i++){
                if(!this->nodes[i]) this->nodes[i] = this; // 存在しないノードのfailure
                else{
                    this->nodes[i]->failure = this; // 深さ1のfailure関数は全てrootに接続される
                    this->rev_failure.insert(this->nodes[i]);
                    que.push(this->nodes[i]);
                }
            }

            // failure関数の更新とmatchedの更新
            while(!que.empty()){
                r = que.front();que.pop();
                for(int i=0;i<nodeSize;i++) if(r->nodes[i]){
                    AhoCorasick* sfx = r->failure;
                    while(!sfx->nodes[i]) sfx = sfx->failure;
                    r->nodes[i]->failure = sfx->nodes[i];
                    sfx->nodes[i]->rev_failure.insert(r->nodes[i]);
                    copy(sfx->nodes[i]->matched.begin(),sfx->nodes[i]->matched.end(),back_inserter(r->nodes[i]->matched));
                    que.push(r->nodes[i]);
                }
            }
        }

        // 動的に追加
        void add(const string& keyword){
            int idx=0;
            int depth=0;  // 遷移回数
            AhoCorasick *r = this;
            vector<AhoCorasick*> s(keyword.size()+1,nullptr);   // s[i] : keyword[i-1]で遷移した先
            s[0] = this;
            // rootからの遷移は深さ1以上の状態からの遷移とことなる特徴を持つので特別に扱う
            if(nodes[keyword[0]-'a'] == this || nodes[keyword[0]-'a'] == nullptr){  // 対応するgoto関数が定義されているか?
                // 先頭文字に対するgoto関数が定義されていない場合,深さ1の状態だけは生成
                nodes[keyword[0]-'a'] = new AhoCorasick;
                s[1] = nodes[keyword[0]-'a'];

                nodes[keyword[0]-'a']->failure = this;      // 深さ1のfailure関数は必ずroot
                this->rev_failure.insert(nodes[keyword[0]-'a']);

                idx = 1;
            }else{
                // 先頭文字に対する状態遷移がある場合はgoto関数がfailになるまで既存の状態遷移をたどる
                while(idx < keyword.size() and s[idx]->nodes[keyword[idx]-'a']){
                    s[idx+1] = s[idx]->nodes[keyword[idx]-'a'];
                    idx++;
                }
                depth = idx;
            }


            //状態遷移の追加とfailure関数,matchedの更新
            for(int i=idx;i<keyword.size();i++){
                // 新しいノード作成
                s[i]->nodes[keyword[i]-'a'] = new AhoCorasick;
                s[i+1] = s[i]->nodes[keyword[i]-'a'];

                // 新しいノードの親ノードのfailureを辿る
                AhoCorasick *state = s[i]->failure;
                while(!state->nodes[keyword[i]-'a']) state = state->failure;

                // 新しいノードのfailure関数を設定
                s[i+1]->failure = state->nodes[keyword[i]-'a'];
                state->nodes[keyword[i]-'a']->rev_failure.insert(s[i+1]);

                // 新しいノードのmatchedを決定
                s[i+1]->matched = state->nodes[keyword[i]-'a']->matched;
            }

            // 追加ノードが無い場合のs[n]を定義
            if(!s[keyword.size()]) s[keyword.size()] = s[keyword.size()-1]->nodes[keyword[keyword.size()-1]-'a'];
            s[keyword.size()]->matched.push_back(pattern.size());

            // 既存状態の更新

            // 追加状態の親はs[depth]
            r = s[depth];

            queue<pair<AhoCorasick*,int>> que;
            for(AhoCorasick* node : r->rev_failure){
                que.push(make_pair(node,depth));
            }

            while(!que.empty()){
                r = que.front().first;
                int i = que.front().second;
                que.pop();
                while(i<keyword.size() and r->nodes[keyword[i]-'a']){
                    AhoCorasick* state = r->nodes[keyword[i]-'a'];
                    state->failure->rev_failure.erase(state);
                    state->failure = s[i+1];
                    s[i+1]->rev_failure.insert(state);
                    r = state;
                    i++;
                }

                if(i>=keyword.size()) r->matched.push_back(pattern.size());

                for(AhoCorasick* node : r->rev_failure){
                    que.push(make_pair(node,i));
                }
            }
            pattern.push_back(keyword);
        }

        // ret[tのindex] := t[index]から開始する文字列はpattern[ret[index][i]]にマッチする
        // 例えば pattern[0] = a , pattern[1] = ab , t = ab なら ret[0] = {0(a),1(ab)}
        vector<vector<int>> match(const string& s){
            AhoCorasick* r = this;
            vector<vector<int>> ret(s.size());
            //map<int,vector<int>> ret;
            for(int i=0;i<s.size();i++){
                int c = s[i] - 'a';
                while(!r->nodes[c]){
                    r = r->failure;
                }
                r = r->nodes[c];
                for(int j=0;j<r->matched.size();j++){
                    int sz = pattern[r->matched[j]].size();
                    ret[i-sz+1].pb(r->matched[j]);
                }
            }
            return ret;
        }
};

コメント

なんか実装バグってる気がする....(正しく実装できてる気が全くしない)
「情報検索アルゴリズム」の本にはキーワードの削除も載ってたけどそっちまで読む元気はなかった...

なんか間違いとかあったらtwitterにでもお願いします(正直このコードがバグっててもデバッグはしたくない)

情報検索アルゴリズム

情報検索アルゴリズム


AhoなのでIQが1!!!! (Ahoさんごめんなさい(土下座))