2014-12-01から1ヶ月間の記事一覧

今年の目標を振り返る

人生ゲーム 2014 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ 採点します。 algorithmのレート:6/6 思ったより上がった。 marathonの参加回数:1/6 機械学習系にも出ないと回数が増えないなー。 marathonのレート:3/6 3回しか出てないにし…

CodeFestival 2014 上海ツアー 参加記 〜コンテスト編〜

結果としては、 1位:snuke (GJ以外の8完) 2位:omeometo (HIJ以外の7完) 3位:アジアの人 (GHJ以外の7完) という感じで、優勝できました。やったー。 7完のままでも時間の差で勝っていたけど、8問目を残り30秒くらいで通して順位表を面白く出来て良…

CodeFestival 2014 上海ツアー 参加記 〜ボードゲーム編〜

上海で遊んだボードゲームについて書きます 5本のきゅうり ルールと写真 amazonのサジェストに出てきて、思わず名前買いした。基本的にカードの引き運がかなり強いんだけど、そんなに単純なゲームではない。 弱い手札が来ても、周りの様子とかを伺いながら…

CodeFestival 2014 上海ツアー 参加記 〜画像編〜

上海についてから初めて見た上海の風景 普通 1日目の観光 クルーズの円卓で回すために撮ったyosupo デパートにて。日本感漂う。 背の低いファミマ 小籠包作り 空港でぼっち飯してるyosupo

CodeFestival 2014 上海ツアー 参加記

0日目 (焼肉・前泊) ・ディスプレイとボードゲームがamazonから届くのを待っていた。(注文していたはずが、注文確定していなかったらしく、お急ぎ便で注文し直した) ・届いた。マルチディスプレイ快適すぎる ・TLはimosさんの結婚と、変数名の話しで盛り上…

文字列の頭良い感じの線形アルゴリズムたち3

昨日の記事の続きです。 Z algorithm 文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。 例えば、 aaabaaaab 921034210 こんな感じです。Z algorithmのテクニックはM…

文字列の頭良い感じの線形アルゴリズムたち2

昨日の記事の続きです。 Manacher 文字列が与えられた時、各 i について「文字 i を中心とする最長の回文の半径」を記録した配列 R を O(|S|) で構築するアルゴリズムです。半径というのは、(全長+1)/2です。 例えば、 abaaababa 121412321 こんな感じです。…

文字列の頭良い感じの線形アルゴリズムたち

この記事はAdvent Calendar 2014の12/1の記事として書かれました。 はじめに KMP、Manachar、Z algorithm の3つについて書きたいと思います。 1アルゴリズム/1日で追記して行きます。これらのアルゴリズムでは「求めたいものの特性を生かして、既に計算…