読者です 読者をやめる 読者になる 読者になる

neovimに乗り換えた

導入したプラグインと導入にあたってハマったことのメモ

github.com

プラグイン管理

dein.vim を入れた.
管理の方針としてはプログラミング言語毎に toml ファイルを用意して, on_ft で言語に応じてtomlファイルを読み込むようにした.それ以外は適当に1つのファイルに纏める

common.toml

一般的なプラグインを管理するtomlファイル

cespare/vim-toml

tomlファイルをシンタックスハイライトするため

tomasr/molokai

colorscheme で molokai を使うため

Shougo/deoplete.nvim

補完プラグイン

Shougo/neosnippet

snippet管理プラグイン.競プロのライブラリはこのプラグインを通じてシュッと挿入される

Shougo/neosnippet-snippets

よく使われるsnippet集.pythonif __name__ == '__main__': とか使用頻度が高い

mattn/sonictemplate-vim

vim時代は thinca/vim-template を使っていたけど,こっちの方が良さそうに思えたので乗り換えた.
:Template kyopro で競プロ用のテンプレートが挿入される

Shougo/unite.vim

正直使いきれてない

kmnk/vim-unite-giti

uniteからgitを叩く(?)プラグイン

scrooloose/nerdtree

vimの左側がかっこよくなる

Xuyuanp/nerdtree-git-plugin

かっこよくなる時にgitの状態を表すアイコンが追加される

scrooloose/syntastic

ソースコードの文法とかをチェックしてくれる.pythonはlintツールに flake8 を設定してる

itchyny/vim-cursorword

カーソルの上にある単語にアンダーラインを引いてくれるプラグイン.たいぽのチェックに役に立つ

itchyny/lightline.vim

status がかっこよくなる

cpp

rhysd/vim-clang-format

ソースコードに対して自動的にclang-formatを実行してくれる.スペース+cfで実行するようにキーマップを設定した

zchee/deoplete-clang

clangを使って自動補完してくれる
macOSだとclangのheaderファイルがなくて自前でbuildする必要がある.ただREADMEにリンクしてあるbuildスクリプトは,macOSheadlink がないことや,引数に空白を含む文字列が渡されることが想定されなかったりする.forkして修正した

arakashic/chromatica.nvim

clangを使ってシンタックスハイライトするプラグインvim時代は justmao945/vim-clang を使っていたけどneovimには対応していないらしく,作者もこっちを使えと言っている

python

tell-k/vim-autopep8

ソースコードを対してautopep8 を実行してくれるプラグイン.clang-formatのやつと同じくスペース+cfで実行される.

zchee/deoplete-jedi

pythonの自動補完プラグイン

Indeed Machine Learning CodeSprint Tagging Raw Job Descriptions

復習がまだ済んでないけどブログを書いてとりあえず供養する

問題概要

求人広告の文章が与えられるので,広告に part-time-jobhourly-wage などの12種類のタグを付与しろ
ただし, part-time-jobfull-time-job のように同時に付与されない排他的なタグも存在する
採点方法は12種類のタグのprecisionとrecallの総和からF値を計算する www.hackerrank.com

方針

やったことを時系列順に

深層学習

深層学習試せばいけるやろwという気分になる.この時は12種類のタグに対して独立に採点されることを認識しておらず,12種類のタグを sigmoid_cross_entropy 同時に予測しようとする.スコア 284.62

問題文を確認する

問題文を確認して12種類のタグをそれぞれ予測してもいいこと知る.排他的なグループ内で素性BoWでSVMを使って多値分類してみる.スコア 460.04

トップはスコア700超えていてすごいなあ

ググった結果 scikit-learnOneVsRestClassifier を試してみる(内部的には12回2値分類をしたことになる).スコア 476.53

つらい

素性にbinaryのBoWやtf-idfなどを試すと,binaryのBoWがいい精度を出した.スコア 544.15

おわりに

分類器に XGBoost や ランダムフォレストを試してみるがだめ
最終的に語彙数を増やしたり,ストップワードを除去してスコア 557.97
最終順位は242人中97位だった.悲しい

感想

機械学習の手法を色々試したりしてただけで,1週間が過ぎてしまってエラー分析とかが全くできなかった…
名前は聞いたことあったけど,触ったことのない機械学習ツールの使い方を覚えた
NLPの趣味なので,lemman化などの前処理を知らなかったのが悔しい
こういう企業の機械学習コンペ増えてほしい

github.com

RUPC2017参加記

すっかり遅くなってしまった

1日目

okaduki さんとhaji149 さんとでチーム名oohajiで参加した.色々あって自称div2 onlyチームだった

A問題

haji149さんが通した

B問題

二つの周期が重なるところはgcd取れば計算できるので愚直に計算するだけ
紙コーディングしておいたおかげかOnsiteのFAを取れた

C問題

okaduki さんが通した

D問題

okaduki さんが4連続ぐらいしかしないよねって言って通した

E問題

最初,魔法の効果が適用されるのはi番目の文字だけだと誤読していて,XとY独立に貪欲にやるだけだと勘違いしていた
haji149 さんの助言で,普通の最大化DPとRとL,UとDを反転させた最大化DPを解けばいいことになる
実装も手伝ってもらった

F問題

okadukiさんが色々考察して辺を逆に張って10回Dijkstraすればいいことに気付いてAC.つよい

K問題

haji149 さんがフローやん!!って言って通してた.つよい

懇親会

お腹ペコペコだったのでずっと食べ続けていた.他の参加者とお喋りするのも楽しかった

感想

3時間コンテストだとちょっと実装バグらせて時間を溶かすと一瞬で終わるので,4時間コンテストは嬉しかった.チームの他の人達が強くて本当にdiv2か??って思った.

2日目

TTJR さんとyurahuna さんとでチーム名toy18で参加した.18はチーム全員が18卒なことから

A問題

問題に図が書かれていて苦手な算数要素が含まれていそうな問題でつらくなる
適当な式変形をしていたら,yurahunaさんが読んでいたC問題が構文解析らしくswapする
yurahunaさんがかなりつらそうだった

B問題

TTJR さんが通した

C問題

「NLPerは構文解析が好き」,「odan氏はNLPのプロ」という仮定のもとC問題を任された(後者は明らかに嘘)
BNFが書かれているけど+か-でsplitするだけなので,構文解析パートはそこまで難しくなかった

D問題

TTJR さんが取り組んでいて,相談に乗りながらデバッグしていたけどサンプルしか一致しないくて困っていた
yurahuna さんが違うDPの更新式を考え出してそれでACした

E問題

yurahunaさん がFA取っていてプロ

F問題

制約が小さいならフローだけど,大きいので解けるのか??という気持ちになる
yurahuna さんに相談すると答えの値は高々2なことを教えてもらう(プロ)
Kについてのアルゴリズムを考えると,元々ある障害物をDFSで探索すれば良さそうなことになる
助言を貰いながら 置く障害物の個数 dfs(現在位置, 障害物を置いた回数) のmin を取る再帰を書いた
提出するがTLEを貰い,mapunordered_map に書き換えるが,読めないコンパイルエラーを吐かれて時間切れ
コンパイルエラーの原因は hash関数を unordered_map 型の変数を宣言するより後に書いていたのが原因だった

懇親会

ウコンを受け取ってしまい,大変申し訳有りませんでした….
お刺身が美味しかった

感想

5時間コンテストは最後の方お腹が空いてしまうので,つらい
F問題はコンテスト中に通しておきたかったなあ

3日目

omurice__ さんとthreepipes_sさんとでチーム名mod_3 で参加した

A問題

問題文の並び替えて回文にできるようなセットにしたい という部分を見逃していて時間を溶かした

B問題

omurice__ さんが通した

C問題

threepipes_s さんが通した

D問題

omurice__ さんから,問題概要と速度の取りうる範囲が小さいので拡張Dijkstraで解けるとの方針を教えてもらって,そのまま実装した
辺を舐めるfor文内でif文+continueを書いていなくて遅いDijkstraを実装していたせいで,WAをもらってしまった

感想

Dijkstraは,辺を舐めるfor文内のif文+continueはあってもなくても,実行時間はさほど変わらないだろうと思い込んでいたけど,そうではなかったので次からは気をつけたい

感想

今年もRUPCも楽しかったです.来年も開催されるなら参加したい
普段学内でチーム練習する時はわりと殺伐としているんですが,RUPCみたいにワイワイチーム戦をするのもいいのかなあと思いました
運営陣+作問陣の方々,懇親会スポンサーのRCOさん,ありがとうございました

第5回 mixi git challengeに参加してきました

mixi git challengeとはミクシィ・グループが主催するgitの使い方に関するコンテストです.twitterのフォロワーに元参加者の方から「勉強になってビールも飲めるぞ」と聞いていたので申し込みました.人が殺到すると抽選で決まるらしい? ブログを書くまでが遠足らしいので,参加記を書きます.

シール

Githubmixi git challengeに関するシールを貰いました.PCにペタペタ貼る人なのでこれはとても嬉しい. f:id:odan3240:20170130214842j:plain f:id:odan3240:20170130214852j:plain

ご飯

節分が近いということで巻き寿司が入ったお弁当が支給されました.寿司をカレーで近似した前回よりは,近似制度が高いと思いました.チームメンバーと社員の方とで楽しく食べました. f:id:odan3240:20170130212402j:plain

コンテストについて

2人チーム制で同じ関西からやってきた人とチームになりました.運営側がチームを指定しているので優しい.
コンテストに使われた問題については言及できないので,チーム体制についてちょっと書きます.うちのチームはわりといいチームワークが取れていたと思います.
最初に取り組む問題はあらかじめ決めておき,解けた人から順番に次の問題に取り掛かろうという方針でした.しかしコンテストが始まってみるとお互い最初の問題からハマってしまいました.そのため最初1時間は正の点数を取れないまま過ぎ,その時点では最下位でした.
流石に何かおかしいだろうと考え,取り組んでいる問題の概要や解答の方針を相手に伝え,お互いの担当する問題をスワップすることにしました.交換してみると相方がハマってたのが嘘みたいにスッと通すことができて,とても興奮しました.
人は深く集中するとそれと同時に視界も狭くなり,簡単なミスに気付かなくなってしまいます.しかしその時に誰かに相談したり,先入観のない他の人に取り組んでもらうことで,簡単なミスを回避できたのかなと思いました.チームメンバーは大事大事.
大きく出遅れたのは痛かったですが,「多くのチームが解いている問題は簡単だろう」「落としているチームが多い問題は何かハマる要素があるから回避しよう」,などとと順位表から難易度を推測して次に取り組む問題を決めていきました.お互い競プロ経験者だったので順位表から問題難易度を見積もることには慣れていた気がします.
後半の追い上げもあって最終的には11チーム中4位で終わることができました.欲を言えば最初にハマって溶かした1時間にもっと問題を解きたかったし,3位以上は表彰されるので最後に取り組んでいた問題を間に合わせたかったです.

懇親会

待ちに待ったビール f:id:odan3240:20170130214426j:plain おつまみ f:id:odan3240:20170130214451j:plain コンビニからそのまま持ってきたようなおでん f:id:odan3240:20170130214445j:plain

社員の方と沢山お話できました.懇親会含め社員さんから聞いた話で印象に残ったのは次の通りです.

  • イケイケな開発体制で開発している
  • ミクシィ・キャリア・チャレンジという社内で転職できる制度がある
  • mixiは業務時間内に行われる勉強会を主催できる

どれも自分には魅力的でした.

感想

最高のイベントでした.問題を流用している関係上1度参加すると次は参加できないのですが,記憶を消してまた参加したいと思ってしまうほどでした.問題入れ替わってまた参加できたりしないかな
これからは大学の人などに宣伝,布教していきたいと考えています.あと作問できたら学内でgit challengeを主催してみたいなとも思っています.

運営をしてくださったミクシィ・グループさん,ありがとうございました.

OIT Advent Calendar 2016について

この記事は,OIT Advent Calendar 2016を作成した経緯や思いなどを書くポエム的なものです.

www.adventar.org

OIT Advent Calendar

作成するまで

Advent Calendarという文化は数年前から認知しており,いつか自分でも記事を書いてみたいと思っていました.
そんな中ある日,OITのAdvent Calendarをやれば面白いんじゃないか?と思い立ちました.

数日後,他のAdvent Calendarが作成され始めているのをTLで観察し,流れに任せて自分も作っちゃえと思い作成しました.

参加者について

11月頭はカレンダーを作ったものの中々参加者が集まらず,こんな気持ちになってました.

裏では大学の同学年や先輩後輩だけでなく,OBの方や先生に記事を書いて貰えないかと頼み込みしていました.そのおかげ(?)か12月が始まった頃には25日中13日が埋まっていました.
Advent Calendarが始まってみると公開された記事を読んだ人がカレンダーに登録したことや,僕の知らないところで勧誘してもらったこともあってあっという間にカレンダーの日付が埋まりました.最初の頃の不安はするだけ無駄だったんだと前向きになれました.

結果的に在校生だけでなく,OBや先生といった幅広い人に参加して貰えました.嬉しい.

作成した経緯

大きく分けて以下の二つがあります.

アウトプットする場が欲しかった

アウトプットする時に情報をまとめることでそれについての理解が更に深まるだけでなく,文章を書く能力の向上や情報を発信することで自分のアピールに繋がると言われています.ただ自分は,何か締め切りや目標を設定しないと動けない人間なので,Advent Calendar を良いきっかけにしようと考えて作成しました.記事の内容が非技術系でもオッケーにしたのはこのためでもあります.

同じ大学の人をもっと知りたかった

普段大学での行動範囲は狭いため知り合いは少なく,もっと大学の人やその人の考え,スキルなどを知りたいと思っていました.
そのため,自分の知らない人がカレンダーに登録することを作成当初から願っていたのですが,無事それも達成することが出来ました

最後に

僕がOITに在籍する限りはカレンダーを作成すると思うので,今年記事を書いてくださった人もそうでない人も,来年参加していただけるとうれしいです.

良いお年を

STLの練習問題

この記事は,Competitive Programming (その2) Advent Calendar 2016 - Adventar の13日目の記事です.

www.adventar.org

大学では競技プログラミングの勉強会を週2回のペースで開催しており,先週の勉強会のテーマはC++STLでした.
アルゴリズムの練習に良さそうな問題集は AOJ ジャンル分けメモ - ひよっこプログラマのプログラミング頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏 がありますが,STLの練習に良さそうな問題を集めたブログは見つかりませんでした*1

そこで自分のソースコードgrepしてSTLの練習に良さそうな問題をピックアップしました*2.今年のKUPCの懇親会でYazatenさんとSTLの練習になるような問題がなかなか見つからないという話題もあったので公開します(必要そうなSTLの部分は白文字で書いています).

AOJ

回文数

URL: Palindromic Number | Aizu Online Judge
必要そうなSTL: string

Princess's Marriage

URL: Princess's Marriage | Aizu Online Judge
必要そうなSTL: pair, sort

Kagisys

URL: Kagisys | Aizu Online Judge
必要そうなSTL: set

列車の編成パートII

URL: Organize Your Train part II | Aizu Online Judge
必要そうなSTL: set,string

英語の文章

URL: 単語の出現頻度 | Aizu Online Judge
必要そうなSTL: map

入力候補

URL: Input Candidates | Aizu Online Judge
必要そうなSTL: map

Atcoder

高橋君とパスワード

URL: B: 高橋君とパスワード - AtCoder Beginner Contest 032 | AtCoder
必要そうなSTL: set,string

座圧

URL: C: 座圧 - AtCoder Beginner Contest 036 | AtCoder
必要そうなSTL: map

(問題数が圧倒的に少ない...)

*1:誰か知っていたら教えてほしいです

*2:string,map,setを主に集めた

オセロ大会のこと

この記事は,OIT Advent Calendar 2016の11日目の記事です。

www.adventar.org

改めて自己紹介

2日目にも記事を書きましたがもう一度
現在OITのIS科3回生です.
IM科の研究室に所属しています.
HxS*1とか競技プログラミングチーム*2に所属しています.
このOIT Advent Calendarの企画をした人です.

オセロ大会

オセロ大会とはIS科学科長のF教授がOITの内部で年に1回開催している,オセロゲームプログラミングコンテスト(学内のみ)のことです.この大会は1回生から3回生に参加資格があります.
勝敗の判定は,AI同士の対戦は先手後手を入れ替えて2回対局し,最終石差によって勝者を決めるというものです.
大会の形式は参加者を4つの予選ブロックに割り振った中で総当たり戦を行った後,予選ブロック上位者が決勝に進みそこでも総当たり戦を行って優勝者を決めるというものです.

なんやかんやで1回生の時から3年連続で参加し続けており,今年度の大会がちょうど昨日で,大会に参加出来るのは3回生までというルールもあって引退(?)となったので,オセロの盤面の表現評価関数, ゲーム木探索アルゴリズム大会の様子辺りを中心にこれまでの振り返りをしたいと思います.

1回生

オセロ大会を知ったきっかけは何だったか明確には覚えていませんが,きっと競技プログラミングチームに参加するうちにF教授に勧誘されたんじゃないかと思います.

  • 盤面の表現
    4回生の先輩から受けたアドバイスもあってオセロの盤面は64bitの整数型2つで表現していました. しかし手の生成は愚直にfor文でループを回すものだったため激遅でした.これで爆速になると勘違いしていたのだから恥ずかしい.
  • 評価関数
    局面の評価関数はとても単純なもので,自分の石の数に隅を取っている数を足したものでした.中盤終盤共に同じ評価関数を使っていたし,この頃の自分にはゲームAIにおける評価値って概念を持っていなかった気がします.
  • 探索アルゴリズム
    オセロAIについて解説しているサイトに必ずと言っていいほどMinMax法なるアルゴリズムが紹介されていたため,これを実装してみることにしました.競技プログラミング再帰関数は書き慣れているためか簡単に書き上げることができました.
    その後AlphaBeta法を知るけど時間もなく一応動いてるものを壊したくない思いもあって実装せず,本番はMinMax法を実装したAIで大会に参加しました.
  • 大会の様子
    C#のスレッドを使って探索を並列化したと言っている人や,ちゃんと中盤と終盤でAIの方針を切り替えている人がいて,自分のプログラムではきっと太刀打ちできないだろうなあと不安でした.しかし実際対戦してみるとその人達のAIがバグっていたせいか,相手を全滅させて予選を勝ち抜くことができました.
    決勝でもなぜか勝ちを重ねることができ,最後の試合は自分と同じく競技プログラミングチームに所属している3回生の先輩との対戦でした.
    1回目の対局では1-63で大敗し,2回目の対局もそうなるだろうと予想していましたが,先輩のプログラムの思考時間が制限*3に引っかかり幸運にも64-0*4で勝つことができました.結果的に2局の合計最終石差では自分が1石差でリードしているため勝ち判定になりました.最後は怪しい勝ち方でしたがオセロ大会で優勝することができました.1回生が優勝するのは大会史上初だったらしいです.

2回生

この年が一番オセロAIの開発に打ち込んでいました.The FFO endgame test suite の#40の完全読みにかかる時間をひたすら短縮していました.最初は完全読みに5分ぐらいかかっていたけど最終的に12秒までに短縮できました.
詳しいことはここに書いてあります. odan3240.hatenablog.com

  • 盤面の表現
    手の生成もビット演算で行う所謂BitBoardを実装しました.これでFFOの#40が1分以内に終わるようになった記憶があります.

  • 評価関数
    機械学習ベースのものにしようと考えていたけど時間が足りず,人間が盤面1マスずつ重みを付けたもの+辺や角を意識した評価値になりました.

  • 探索アルゴリズム
    中盤のアルゴリズムは以下の本を参考にNegascout法を採用しました.中盤では11手先を読むように設定していました.

    ゲーム計算メカニズム (コンピュータ数学シリーズ 7)

    ゲーム計算メカニズム (コンピュータ数学シリーズ 7)

    • 作者: 岸本章宏,柴原一友,鈴木豪,小谷善行
    • 出版社/メーカー: コロナ社
    • 発売日: 2010/02/08
    • メディア: 単行本(ソフトカバー)
    • 購入: 3人 クリック: 66回
    • この商品を含むブログ (7件) を見る
    終盤はZebraの作者が速さ優先探索*5がいいと言っているらしい*6のでそれを採用しました.これによってFFOの#40が20秒台になったはず.
    空きマスが20個以下になったら完全読みするように設定していました.

  • 大会の様子
    前日までAIのバグ取りをしていました.Visual StudioでBOM付きじゃないUTF-8を使うと意味不明なバグを踏むので気をつけましょう.
    この年はCODE RUNNERと日程が被っていたので,学科の友達にAIだけ預けました. その友人に結果を聞いたところによると,ランダムに手を打ってくるAIに時間超過で負けた以外は全勝で優勝したらしいです.

終了直後は来年はもっと強いAIを開発して優勝しようなという気持ちに溢れていました.

3回生

1年前の大会直後は意気込んでいましたがこの年が一番やる気がありませんでした(悲しい).
プログラム自体は1年前のものとほぼ変わらず,置換表のバグを修正した程度でした.

  • 大会の様子
    F教授曰く参加者のレベルが低調な大会だったらしいです.参加者に1回生,2回生が1人もいなかったし,強制参加のF研の人たちは200行程度のとりあえず動作するオセロプログラムだったし僕も全く取り組んでなかったし仕方ないねって感じです.
    無事3連覇できたけど真面目に取り組んでなかったためか,喜びは薄かったです.

できればtensorflowで機械学習をやり直したり,Lazy SMPを実装したり,将棋所みたいなGUIのアプリを組んで参加したかった...
終盤ソルバの高速化に喜びを覚えたように評価関数のlossを小さくすることに喜びを覚えるようになったらまた開発を再開するのかなあ

おわり

結局一番オセロAIの開発の打ち込んでいたのは2回生の時でした.情報収集とコーディンを繰り返す日々で,OBの人のオセロAI開発ブログを発掘するなんてこともありました.
この時の経験によってプログラミング技術の向上だけでなく,単体テストを書いてTravis CIでコードの品質を担保するなど開発体制の勉強にもなったので,大会に参加出来たことに自分は満足しています.夏休みのインターンに申し込んだ時は話すネタにもなって選考を通過できましたし.

真面目に取り組むとAIを強くすることは楽しいしメリットもあるので,参加資格があるOITの人は是非参加してみるといいですよ.

*1:HxS wiki - HxSコンピュータサークル

*2:ACM-ICPCに参加するためのサークルのような組織

*3:1手の思考時間は5分まで

*4:ルールでバグや時間超過を起こすと無条件に64石を得る

*5:着手可能数が少ない順に探索するアルゴリズム

*6:強いオセロプログラムの内部動作