競プロサークルの話

この記事は「競プロ!!」 競技プログラミング Advent Calendar 2017の8日目の記事です．投稿が遅れて申し訳ありません

adventar.org

この記事では弊学の競プロサークルで行っている活動について書きたいと思います．

新入生勧誘

2年前までは所謂新歓期にサークル員の勧誘は行っておらず，プログラミングや数学が得意そうな学生を直接スカウトする仕組みでした．しかし競プロサークルがあまり認知されていない*1こともあって，中々新しい人は入っていきませんでした．実際自分の1年下の学年は僕が2年生になるまで誰一人いませんでした．
そこで弊学で4月の新歓期にブースを構えてチラシを配布することにしました．これまでチラシ作りに関するノウハウがなかったので苦労しましたが以下のようなチラシを作って配布しました*2．100枚印刷していましたが，50枚も配布できなかったのでもっと少なくていいと思います．配布枚数とサークル員のコミュ力には正の相関があると思うので来年以降は見定めてください．

この効果もあって2016年度は10人以上，2017年度は7人ぐらいが興味を示してくれました．2016年度当初の2年生以上のサークル員の数は5人だったので急に増えて驚きました．このことが前期の活動内容に大きく影響します．

前期

前に書いた通りたくさんの1年生が入ってくれました．その1年生の殆どはプログラミングについて知らず，サークルとしてプログラミングとはなんぞやということを教える必要に迫られました．しかしこれまでは，優秀そうな学生をスカウトするという方針だったため，チラシ同様にプログラミングを教えるというノウハウがありませんでした．
2016年度は幸いにも自分の同期が，他の部活で1年生にC言語を教えていた経験があり彼に頼むことにしました．内容としてはC言語の基本的な文法などを抑えた後，C++の便利な機能を紹介するというものでした．人数が多くなったためパソコンの数も足りなくなり部室*3で活動を行うことを諦めて，大学の演習室を借りて行いました．
2017年度は自分がC++を1年生に教えました．1人で毎週勉強会用のパワポを1から作るのは大変だったので，なんとかして分業する or 手を抜く方法を考えたほうがいいです．日程は以下の通りでした． f:id:odan3240:20171213232158p:plain

1回の勉強会の流れは，その日扱うトピックについて紹介→バチャコンでそのトピックに関する問題を解いてもらうでした．バチャコンを使うことで誰がどの問題にハマってるか確認しやすかったです．バチャコンに使う問題はRiPProの方からABCのAB問題に対して，C++のどの文法の知識を使えばいいかタグ付けされた問題リストを頂いていたので，それを参照して選びました．
一応ACM-ICPCの国内予選のA問題は解けるようになって欲しいと思っていましたが，1年生に国内予選の感想を聞くと難しかったようです*4．どうすればプログラミング未経験者を数ヶ月でA問題を解けるようになってもらうかも今後の課題です．
C++勉強会用に作ったスライドはクオリティの高いものではないので，一般公開する予定はないのですが，同じようにサークルで1年生向けに勉強会を開く時に使いたいという人がいれば差し上げます．

これまでは週1の活動だったので，1年生向けにプログラミングの講習会を開くと自分たちの勉強会が消えてしまいました．そこで上級生向けの勉強会を別の日に行うことにしました．この勉強会はバチャコンを開催し問題に取り組み，その後問題をどう解いたかを話し合う形式です．

後期

まず，前期にたくさんいた1年生はほとんど来なくなりました．これはある程度は仕方ないと考えています．

2016年度より後期は週ごとにアルゴリズムかデータ構造と担当を決めて，輪講形式の勉強会を開きました．これはせっかく集団で競プロをやっているので何かしらの知見を共有したいとの理由で始めました．2017年度のスケジュールは以下の通りです．

f:id:odan3240:20171213233738p:plain

しかしこれも難しいなあと感じます．

それと前期同様に皆で集まってバチャコンの問題を解く勉強会も別の日にやっています．

最近

もうちょっとサークルらしくしようという声が上がり，その一つとしてロゴを作りました．作成には Build a Website - Squarespace を使いました．

f:id:odan3240:20171213234424p:plain

このアイコンは皆でコンペした結果wheson氏が作ったものが採用されました．

twitter.com

他にもロゴのステッカーも作る話や，外部向けのサークル紹介サイトを作る話が挙がっています．続報があればここに追記するかもしれません．

おわりに

弊学の競プロサークルの活動についての紹介をしました．自分が認識している問題点とはしては以下の通りです．

  • 数ヶ月でICPC国内予選A問題を解けるようになるには
  • 1年生から4年生まで全ての人が嬉しい輪講形式の勉強会の方法

いつか改善されてほしいですね．

ここまで書いていてあれですが，実は弊学には競技プログラミングサークルはありません．どういうことかというと，自分の所属している競技プログラミングをする団体はサークルや部活ではなく，学生プロジェクトというものに分類されているため厳密にはサークルとは異なります．やってる内容自体はサークルと変わりないのですが，部費がタダだったりRUPC,JAG夏合宿などに参加するために大学から金銭的な援助が得られるので色々お得だなあと思いながら活動しています．ただ，他の人に紹介する時に手間なのでいつもサークルだと言い張っています．

*1:大学の掲示板にチラシが貼ってあるだけ

*2:2017年度版，2016年度のはどっかいった

*3:厳密には違う

*4:それはそう

bashからzshに乗り換えた話

この記事は、 OIT Advent Calendar 2017の2日目の記事です。

前置き

元々OIT Advent Calendarに弊学の梅田キャンパスを「がっこうたんけんした話」を書くつもりでしたが外が寒くてダメでした．何か記事を書くネタを考えたところ最近zshを使い始めたのでそのことを書くことにしました(偶然にも2日連続シェル環境の記事になった)．

dotfiles

最初に貼っておくとdotfilesは以下にあります

github.com

Docker

また以下のコマンド群をコピペするだけで僕のzshを試せます！

docker run --rm -it odanado/zsh zsh
./install.sh && ./deploy.sh
source ~/.zshenv && source ~/.zshrc

動機

周りに影響されてfishを触ってみたところ，デフォルトで入っているauto suggestion機能がとても便利に感じました．ほぼ何もカスタマイズされてないbashで作業をするのは目に見えない時間を失っているようで嫌だったので，bashを辞めることを決意しました．
乗り換えるshellを選ぶ上で前から気になっていたzshと，周りの人が使っているfishで悩みましたが，zshの方が色々カスタマイズできてネット上に情報が多そうだったので，zshを選びました．

プラグインマネージャ

まず最初にプラグインマネージャを選びました． Prezto や oh-my-zsh や Antigen などもありましたが， zplug がいいとの情報が多かったので zplug を選択しました．後述しますが実際使ってみて最高でした

インストールしたプラグイン

zsh-users系

目についたやつを入れていきました

peco

pecoはリアルタイムgrepみたいなコマンドです．GO言語で実装されていて厳密にはzshのプラグインというわけではないんですが， zplug だとこういったものも zplug "peco/peco", as:command, from:gh-r でインストールすることが可能です．この柔軟性が最高だと思いました．

ghq

これまでは ~/git 以下にひたすらgit cloneしたリポジトリを集めてましたが，ghqを使えば管理が楽になります．これも zplug を使って zplug "motemen/ghq", as:command, from:gh-r でインストールできます．

anyframe

pecoと連携するためのプラグインです．ほしい関数が用意されているので使うのにキーバインドやaliasを設定するだけで使えるようになって便利．

powerline

ターミナルのステータスバー？をかっこよくするやつ． zplug は他人のzshファイルを読み込むこともできて， zplug "powerline/powerline", use:"powerline/bindings/zsh/powerline.zsh" でインストール可能です(ほんと最高)． デフォルトのconfigだとかっこいい三角形を表示するためにpowerline用のフォントをインストールする必要があります．しかし三角形を表示するためにフォントをインストールのは大げさだと思い，configで"default_top_theme": "ascii" としています．他にも設定を弄って最終的にこんな表示になりました． f:id:odan3240:20171202222956p:plain

その他設定

ヒストリ

どうやらデフォルトではヒストリを保存しないぽいので設定しました

export HISTFILE=${HOME}/.zsh_history
export HISTSIZE=1000
export SAVEHIST=500000
setopt hist_ignore_all_dups # 同じコマンドをヒストリに保存しない
setopt hist_reduce_blanks # 無駄なスペースを消してヒストリに保存する
setopt share_history # ヒストリを共有

ssh-agent関係

tmux内でもssh-agentが使えるように以下の記事の設定をコピペしました

qiita.com

CIとか

TravisCIとDockerを使ってgithubにpushされるたびに，zplugでのプラグインのインストールが成功することと，zshenv及びzshrcの読み込みが成功することをテストするようにしました．本当はちゃんど動作するところまでテストしたいと思っていましたが方法がわからず，ないよりマシの精神でインストールとロードまでをテストしています．この辺の知識がある方がいれば教えていただきたいです(あとneovimの起動もテストしたい)．

おわりに

bashからzshに乗り換えてインストールしたプラグインや設定を紹介しました．今回zshに乗り換えたことでシェル環境の快適度が増して個人的にとても満足しています． zshにはこんな便利なプラグインがあるよ！とかこの設定書くと便利だよ！などの情報をお持ちの方はぜひ教えてください．

SIMD-oriented Fast Mersenne Twisterのpythonラッパーを書いた

SIMD-oriented Fast Mersenne Twister とは

SIMD命令を使うように設計されたMersenne Twisterのこと．普通のMersenne Twisterより高速に動作する．3DSのあるゲームソフトで擬似乱数を生成するために使われていたりする

動機

SFMT(SIMD-oriented Fast Mersenne Twister) を使う時はいつもCでプログラムを実装して，それをpythonからsubprocessで呼び出していた．この方法だと使える言語に制限があるAWS Lambda など使えない．
そう思って作ったがこの記事を書くにあたって改めて調べるとバイナリも一緒にアップロードすれば使えるらしい．まあ，バイナリを作ってアップロードするという手間が省けると思うことにする．

すでに作ってる人はいたが sfmt_genrand_real1 しか実装されておらず， sfmt_genrand_uint64 を使いたい自分の要望にはマッチしていなかった． GitHub - mochizuki-ichiro/pysfmt: SIMD-oriented Fast Mersenne Twister for Python Cythonの勉強も兼ねて自分で実装することにした．

コード

github.com

pypiにもアップロードしたので pip install pysfmt でインストール出来る

問題点

coverageを計測したかったけど何故かできていない http://cython.readthedocs.io/en/latest/src/tutorial/profiling_tutorial.html#enabling-coverage-analysis にあるように .coveragerc に設定を書いたけどダメだった

condaをパッケージマネージャとしてインストールする

動機

conda コマンドは便利だけどシステムのpythonは上書きしてほしくない． python-venv ぐらいのノリで conda コマンドを使いたい
pytorchはcondaコマンドでインストールすることを推奨してるので，こっちでインストールしたい

方法

実はPyPIにcondaコマンドは登録されていてこれをインストールすればよい．
ただ単純に pip install conda でインストールするだけでは以下のように condaにpip経由でインストールしたことを怒られる

ERROR: The install method you used for conda--probably either `pip install conda`
or `easy_install conda`--is not compatible with using conda as an application.
If your intention is to install conda as a standalone application, currently
supported install methods include the Anaconda installer and the miniconda
installer.  You can download the miniconda installer from
https://conda.io/miniconda.html.

しかしこれは4.3系からの仕様なのか，4.2系を入れると特に怒られずにcondaコマンドを使える．つまり pip install conda==4.2.7 でインストールすれば良い

とりあえずこれで conda install や conda create が使えているので良しとする

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の自動補完プラグイン