ちゃっくのメモ帳

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

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

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を狙うには修行不足(特に僕はチームのマスコットをしていたので).


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

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の睦月ちゃんを勧誘しなくてはならない。

アドベントカレンダー

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

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

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

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

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

卒論。死んだ。

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

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版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

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関数として定めることができる.(多分ここが1番重要.ステップ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さんごめんなさい(土下座))

ARC085 D ABS

問題
D - ABS

自分の解法はO(N^2)だが解説の方法がO(1)だった。
この解説に最初ちょっと納得できなかったのでメモ

どこで納得が行かなかったかというと「Xがa_iまで取った時,Yはa_{N-1}までとる」という部分がよくわからなかった。
というのは「Xが途中までとって,その後Yがうまく選択したらもっと低い/高い値がでるのでは?」と考えたから。。。

「Xがa_iまで取り,そのあといくつかYが取った」場合を考える
f:id:chakku000:20171112022741p:plain

こんな感じで...

もしこの結果がmax(a_N-a_{N-1},a_N-W)よりも小さくなった(つまりYが良い選択をできた)とする。
この場合,Xは前からi個を選択したのが,「Xがスコアを最大化しようとする」という前提に反しているので矛盾。よって前からi個をXが選択してスコアがより低くなることはない。

逆にXが前からi個選択して結果がmax(a_N-a_{N-1},a_N-W)よりも大きくなったとする。
この場合,Yはa_{N-1}までを選択することでスコアをa_N-a_{N-1}にすることができる。
従って,max(a_N-a_{N-1},a_N-W)を超えることはない。


これで最初に提示した疑問は解決した...はず...

(考察に漏れがあればtwitterにでもリプください)

Vimconf2017に行ってきたんだよ

Vimconf2017に参加してきました
VimConf 2017 - An international Vim Conference

場所は秋葉原富士ソフト アキバホール.めっちゃでかい会場だった.
到着したらVimconfTシャツを貰ったりしてた.


発表

@haya14busa さんの発表
Vim,Me and Communityという発表.
EasyMotionの話とかIncsearch.vimの話とかこれまでのはやぶささんとvimの話を特に検索,移動周りの話を中心にしていた.
スライドに入っているいらすとやの絵が選択がうまかった...

@fatih さんの発表
vim-goの発表.
vim-goを使うためにgo言語をやりたいと思わせてくれる素晴らしい発表だった.

vim鼎談
@mattn_jpさん@kaoriyaさん@k-takataさんの話.
@mattn_jpさんを初めて見たけど服を着ていた.
spell checkを使うべきだと言ったりしていた.
(ただ,これを聞いてspell checkを使用してみたが意図的なものまでエラーとしてでてしまうのでgitのコミットとかくらいになら...って感じがする)
あとlanguage server(vim-lsp)とかの話も出てきた.これらは全く知らなかったので少し調べたい.

@cocoponさんの発表
Creating Your Lovely Color Schemeという発表
Iceberg.vimを作った人によるcolorschemeの作り方講座.
「コンセプトを決めて色はコンセプトにそって決める」や「主なカラーパレッドをまず作る」「カラーパレットは最初に1色決めてあとは色相の変化で」など,素晴らしい知見が得られた.
直後にカラースキーム弄り始めてしまった.

@t9mdさんの発表
vmpの発表
ATOMvimプラグインについての発表
Mutationとかの話

@senopenさんの発表
Vim and Compatibilityという発表
どこでも動くvimrcを作るみたいな話.キーワードはWrite .vimrc Once Wrok Vim Anytime/Anywhere.
POSIX原理主義の方だった.Vimの歴史とかも語られる.
確かにどこでも動くvimrcは魅力ではあるが,それを作るための労力は大きそう.とくにエンコーディングにも詳しく語っていた.
どこでも動くvimrcを書きたいならこのスライドは見るべき.そうでなくとも1度は見ておくべきって感じの発表だった.

@ShougoMatsuさんの発表
暗黒美夢王ことShougoさんの発表
正直この方の発表を目当てにvimconfに参加したみたいなところがある.
発表内容はNeosnippet.vim + Deoppet.nvim
Deoppet.nvimを使うなら来年まで待つべきらしい.
Deoppet.nvimにはExtended markというものが使用される.
といった内容.そしてdeopleteがVim8に対応したらしい.Windowsだとプロセス間通信が非常に遅いらしい.

@dice_zuさんの発表
How ordinary Vim user contributed to Vimという発表
Vimのコントリビュータになるためにはみたいな話.「毎日Vimをビルドして使っていると」とか「ある朝Vimをビルドして起動してみると」とか言ってて笑った.

@p_ck_さんの発表
The new syntax highlighter for vimという発表
vimのsyntaxは正規表現を使っているが,正規表現は人間には早すぎるので, iro.vimを作ったみたいな話.
iro.vimはパフォーマンスが良いらしい.

@lambdalisueさんの発表
gina.vimの紹介
Vimanという言葉が出てきた.どうもVimを使いやすくしようとする人々のことであるらしい.
gina.vimはGitを扱えるVimプラグインらしく,いまVimでgitを扱うならこれなのかな
発表を聞いてこのプラグインを入れてみたくなった.


感想

どの方の発表も素晴らしかった.個人的にはcocoponさんとfatihさんの発表が好きだった.
英語での発表者もいたが,同時通訳してくれていて嬉しい(同時通訳自体が1つのコンテンツだった)

お昼ごはん凄く美味しかった


Vim coffee

懇親会

Shougoさんと話すことが出来た.neoincludeがdeopleteに対応してるとかの話を聞けた.
aiya000さんのLT. Either Monadをvitalに入れた話とか.
koturnさんとryunixさんとも会うことができた.

Vimconfとても楽しかったです.
発表者の方々,発表お疲れ様です.
スタッフの方々,企画運営ありがとうございました.

json4sを使ってみた

scalajsonを扱いたいと思ったのでやったことのメモ

用意したjson
gist.github.com
pythonで生成したら日本語が...

とりあえずjson4sを使うためにbuild.sbtに

libraryDependencies += "org.json4s" %% "json4s-jackson" % "3.5.0"

とした.

URLからjsonを取ってきてjson4sでパースし,shigureに対応する要素を出力ということをしてみた

import scala.io.Source

import org.json4s._
import org.json4s.jackson.JsonMethods._

object Main{
  def main(args:Array[String])={
    val url = "https://gist.githubusercontent.com/chakku000/ea3bce545c397b2bbc3f211e074847d1/raw/fc0744f530bf993a5c059254a8101adc650d11ec/poi.json"
    val source : scala.io.BufferedSource = scala.io.Source.fromURL(url)
    val contents : String = source.mkString
    val json = parse(contents)    // JsonのAST表現
    val maps = json.values.asInstanceOf[Map[String,Any]]  // JsonのAstをMapに変換

    val shigure = getFromOption(maps.get("shigure"))
    println(shigure)
  }

  def getFromOption(v : Option[Any]) : String = {
    v match{
      case Some(s) => s.asInstanceOf[String]
      case None => ""
    }
  }
}

となった.

いくつかわからないことがあった.
一つは json.values.getClassとするとscala.collection.immutable.Mapとでるのでgetができるかと思ったが,json.values.getとするとjson.Valuesのメンバじゃないと怒られてしまう.なんでだろう?

感想

Scalaを初めてみたが,コップ本も詰んであるままなので読まないと....
質問できる人がほしい...

追記1

json.Valueにgetメンバがないと怒られるのは,json.valuesの型が静的にはMapして解釈できないのでは?という指摘を受けた.asInstanceOfで明示的に型を指定すれば静的にMap型として解釈できるのではというものである.

追記2

上のコードはもう少し簡単にできるらしいです.こんな感じで

import scala.io.Source

import org.json4s._
import org.json4s.jackson.JsonMethods._

object Main{
  def main(args:Array[String])={
    val url = "https://gist.githubusercontent.com/chakku000/ea3bce545c397b2bbc3f211e074847d1/raw/fc0744f530bf993a5c059254a8101adc650d11ec/poi.json"
    val source : scala.io.BufferedSource = scala.io.Source.fromURL(url)
    val contents : String = source.mkString
    val json = parse(contents)    // JsonのAST表現
    //val maps = json.values.asInstanceOf[Map[String,Any]]  // JsonのAstをMapに変換

    implicit val formats = DefaultFormats
    val shi : String = (json \ "shigure").extract[String]
    println(shi)
  }
}