ICPC国内予選2017参加記

お疲れ様でした

f:id:odan3240:20170715103746p:plain

チーム

コンテストの様子

問題文を印刷する．模擬国内予選と同様にA問題も印刷してしまう．
最初のABCはチームメンバーそれぞれが担当することになっていたので，自分はC問題を読む．実装がちょっとつらそうだけど去年と同様に簡単なC問題なので，やはり4完しないとアジア予選には参加できないなと思う．

00:12 A問題 AC

B問題を解いている後輩がちょっと詰まっているみたいなので，A問題を解いた同期に様子を見てもらって，C問題を実装し始める．微妙にどこかバグってるなあ頭悪いなあとつらくなっていたら，B問題が実装できそうとのことなので，ソースコードを印刷してパソコンを交代する．

00:49 B問題 AC

印刷したソースコードを眺めていたら，頭の付いていない箇所を見つけたので修正する．それでもサンプルが一致しなくてデバッグしていると，外側の最小値を2回掛けていることがわかり悲しくなる．修正するとサンプルが一致したので提出した．

01:10 C問題 AC

個人的にいいペースで3完でき，何とかして次の問題を解きたいぞとなる．
E問題は実装を頑張れば通りそうだし，しっかり考察をすれば実装が軽くなる系の問題な気がしたが，順位表はD問題を通しているチームが圧倒的に多かったのでD問題を解くことに決める．
レシピと材料で2部グラフを作りフローを流せば解ける気がしてしまう．考察してる間に後輩にライブラリを写経してもらう．全部のレシピを試したことにして，材料が偶数個になるように辻褄を合わせるために消すレシピを最小化すれば，元の問題が解けることに気付く．この最小化の部分を最小費用流で解けそうだと感じて実装するがサンプルが一致しない．このまま時間切れで終了．

コンテストの感想

D問題はnの大きさで場合分けだったらしい．最初問題を読んだ時にsqrt(500)の値は計算していたのに気づかないのは悲しかった．考察の最中に愚直にbitDPすれば2**500だからつらいよねーとか嘘を言っていた悲しい．
やっぱ4完の壁は大きいと感じた．

解いたC問題のソースコード

gist.github.com

ICPCの感想

色々あって恐らく今年で引退になりました．ICPCは高校から競プロをやっていた関係もあって1年の頃から参加してきました．戦績はこんな感じです．

学年 解いた問題数 順位
1 2完 83位
2 3完 54位
3 3完 73位
4 3完 66位

今年うちの大学からICPCに参加した人のほとんどは来年も参加可能だし，日常的にAtcoderなどのコンテストに参加する人が出現し始めたので，来年以降に期待したいなと思います．
進路が確定したらJAG入りするのかなあ．

何はともあれお疲れ様でした．アジア予選進出された方は引き続き頑張ってください．

macでllvmをbuildする時に The specified item could not be found in the keychain. とエラーを吐く

背景

neovimに乗り換えた - odan’s diary に書いたように neovim のプラグインのzchee/deoplete-clang を使うために， Build llvm for OS X · GitHub で llvmをbuildする必要がある．

症状

error: The specified item could not be found in the keychain. というエラーメッセージを吐いてbuildが止まる

解決策

http://llvm.org/svn/llvm-project/lldb/trunk/docs/code-signing.txt に書いてあるように，lldb_codesign という名前の証明書を新しく作ればいい

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集．python の if __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スクリプトは，macOSに headlink がないことや，引数に空白を含む文字列が渡されることが想定されなかったりする．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-job や hourly-wage などの12種類のタグを付与しろ
ただし， part-time-job と full-time-job のように同時に付与されない排他的なタグも存在する
採点方法は12種類のタグのprecisionとrecallの総和からF値を計算する www.hackerrank.com

方針

やったことを時系列順に

深層学習

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

問題文を確認する

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

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

ググった結果 scikit-learn の OneVsRestClassifier を試してみる(内部的には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を貰い，map を unordered_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のフォロワーに元参加者の方から「勉強になってビールも飲めるぞ」と聞いていたので申し込みました．人が殺到すると抽選で決まるらしい？ ブログを書くまでが遠足らしいので，参加記を書きます．

シール

Githubとmixi 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に在籍する限りはカレンダーを作成すると思うので，今年記事を書いてくださった人もそうでない人も，来年参加していただけるとうれしいです．

良いお年を