ICPC2014参戦記

ICPC2014国内予選参加しました。
結果は5完の24位でアジア地区予選には自明に進めないのでここでおしまい。

解いた問題と方針

相方にAを任している間に、C,Eの実装を考えて、
Aが終わった後、Cを通す。
疲れたので相方にBを任せている間に、Dの方針を聞いたり他の問題考えていた。
Bが終わった後、DとEを連続して実装して通す。
F、Gは歯がたちませんでした。

C問題

はじめは二部探索かな、と思ったが、判定関数考えているうちに直接求まることに気がつく。

まず、各々のx軸上の区間のビルの高さの最大値を求める。ビルが存在しなければ0とする。
i<=0となるような[i-1,i]区間ではx=iの地点がより太陽が先に見えてしまう。
i>0となるような[i-1,i]区間ではx=i-1の地点がより太陽が先に見える。
よってそれぞれの区間について、太陽が先に見えるx座標とそこの高さに円が到達する時間を求める。
そのうち最小のものが答えとわかる。

r<=20という制限により、区間中に存在するビルの高さの最大値は愚直に求まり、
到達する時間については2次方程式をさくっと解くだけ。

D問題

相方から聞いた方針を具体化しただけ。

文字数がたかだか20なので、各文字について変換されたorされないと仮定して復号化、それを暗号化してちゃんと元に戻るかを計算すれば大丈夫、
というもので実装した。
各文字について変換したかどうかをビットマスクで表現して、’z’を復号化するときだけは例外処理。
ちゃんと元に戻った文字列は記録し、最後にソートして出力。

ただ、この方針、すぐには実装できるのだが、最大で2^20*20*25の計算となり、500000000くらいとなり、普通のプロコンだと通用しない計算量となってしまった。
（暗号化するかしないかのパターンで2^20通り、暗号化で20*25の処理が入る）
ただ、ICPCは制限時間が無く、手元で実行し出力ファイルを提出すればいいだけなので、
出力を待っている間、他の問題を実装していれば問題なく正解をもらえた。

もうちょい何とかするとすると、暗号化するところの処理を文字の出現位置とかをメモすることで高速化するか、
DFSとかで暗号化できないような文字列は探索しないようにすることでそもそも判定の手間を減らすとかか。
あと、ビットマスクの探索順を工夫すれば最後のソートはいらない。
まあ、いずれも実装が複雑化しそうなので、これはこれでよかったのかなあ。

E問題

自明に木構造をしているので、木DP的な何かかなと当たりをつける。
ノード数が300と少ないので、全ての点について根であると仮定した場合で回しても十分間に合いそう。
終点についてもそれぞれについて終点としてみて試せば300*300*300で間に合うんじゃないか、となったが、
擬似コード書き始める時点で、終点を固定して探索するの厄介だなあと考え、もうちょっと考えなおしてみる。

そこで、始点と終点が同じであるパターンからまず考える。
始点をAとしておく。
葉、つまりこの先に何もない島につながっている橋はわざわざ渡る必要もなく、即座に撤去すれば良い。
そうではない島(Bとおく)につながっている橋は、まず、Bより先にある橋を撤去する必要があるので、一度その橋をわたらなければならない。
Bについても、Aに戻るためには同じ橋を渡らなければならないので即座には撤去できず、Bよりも先にある橋を全て撤去してBに戻り、
Aに戻り、やっとA-B間の橋を撤去出来る。
つまり、ある島を始点とした場合、それを根にした木と考えた時、葉をつなぐ橋は即座に撤去し、そうでない橋は2回渡った後撤去することで、
全ての橋を撤去できる。始点と終点が同じならこれが最小コストのはずだ。

始点と終点が異なる場合、最後に終点まで行くとき、そのパス上にある橋を渡ることになるが、この時、戻る必要性がないので、渡った時点で即撤去できる。
つまり、始点と終点が異なる場合、始点から終点までのパス長ぶん戻るコストを節約できるという訳である。
よって、始点と終点が異なる場合の最終コストは始点を固定した場合、その始点から最も長い長さの葉ではない島を終点とした時である。

コードとしては、DFSで始点と終点が同じと仮定した場合のコストを計算しつつ、始点からその島までのコストを持つことで最も遠い島を探すようなコードになった。
最も遠い島に関してと始点と終点が同じ時のコストを計算するDFSを分けてもDFS1回の計算量が高々ノード数程度なので、十分に間に合う。

#感想・反省
3度目の参戦となり、今までの反省を活かせたんじゃないかなと思っている。
1度目は個人としての能力があまりにも低すぎた＆相方がガチ勢だったので、足を引っ張るだけのゴミだったのだが、
2度目は自分の能力もそれなりについて、相方もほぼ同レベルだったが、結構足を引っ張ってしまったと反省していた。
原因はちゃんと実装を細かいレベルで考えていなかったことで、
方針は立っても細かいところでつまり1台しか使えないパソコンをかなり占有してしまった。

今回は相方が実装している間に、実装の細かいところをじっくりと考えたので、実装はかなり早く終わったのではないかな、と思っている。
前回の僕であれば、Eで始点・終点それぞれ固定して探索しようで行けると思い込んで実装に詰まっているところだった。
あと、チーム全体和やかな雰囲気だったので、練習量も個人の能力もそこそこだった割にはいい成績を残せたのかなと。

ただ、今回も反省はあって、入出力パターンの確認はしっかりやるべきだった。
これで1回躓いてしまった。ロスは小さかったかもしれないが、やはり、事前に意識すべき範囲であった。

#まとめ
ICPCにおいて最も重要なこと、それはパーフェクト・ハーモニー、完全調和だ！

（強い人に怒られそう）

Vimでコードリーティング

C言語で書かれた比較的大きなプログラムを読むことになったので、
やり方をちょっと調べながら試している。

今まではVim+ctagsでタグジャンプして読み進めるで対応していたが、
大きめで呼出がアッチコッチ飛ばされたりするとなかなかつらい。
また、一度読んだところも頭に入らず、もう一度読むという事もしばしば。

ということで、この辺を参考にする
人間とウェブの未来 - GNU GLOBALとvimで巨大なコードでも快適にコードリーディング
ひらメソッド初心者奮闘記（PDF）

ひらメソッドっていうのは、コードを読みながら、
関数ごとにwikiのページをつくって、ボトムアップに読んで行きましょうというもの。
コードを読む時、GNU GLOBALとVimを連携させることで、定義にポンポン飛べる。

で、wikiなのだが、pukiwikiを使って管理しろみたいなページを結構見かけたけど、
環境構築面倒だし、pukiwikiは更新止まっているとかいう噂も聞いたしで気が進まない。
なので、Vimwikiを使うことにした。
Vimwiki : Vimエディタ上で動作するWiki環境

僕がVimwikiを導入した時、なぜかページを編集するたびエラー吐いて何かなあと思ったら、
シンタックスファイルで使われているoptionsとかいう変数が
他のプラグインと衝突していたらしく、
optionsをvimwiki_optionsとかに置換したらなおった。

まだ、手探り感あって上手くいくかわからんが、とりあえずこれで。

Eigenで疎行列を扱う

ある方程式とかを解くときに、行列をつくるということはよくやるが、
その内の非ゼロ要素が極端に少ない場合、行列がムダにおおきくなってしまうので、
疎行列用のクラスを使ってやる必要がある。

Eigenの場合、SparseMatrixという疎行列クラスがあるので、これを使えば行列のように
簡単に扱えて便利だった。
boostとかにも疎行列用のクラスはあるのだが、どこのサイトで見たか忘れたが、各種ライブラリと速度比較してEigenはかなり優秀だそうで。

検索しても情報が少ないが、公式のチュートリアルとリファレンスが最もまともな資料だった（ともに英語）。
Tutorial page 9 - Sparse Matrix
SparseMatrix< _Scalar, _Options, _Index > Class Template Reference

要素のセット方法を探すのに結構手間取った。
個別に要素をセットするときはinsertメソッドを使い、
まとめてセットするならTutorialのFirst
Exampleにあるみたいに、Eigen::Tripletのvectorをつくってから、setFormTripletsでやるのが楽かなって感じ。

markdownをvimで扱う

最近、ノーパで授業ノートを取る機会が増えてきた。
今まではプレーンテキストで何とかしていたのだが、さすがに整形しないとあれなのでmarkdown記法を使うことにした。

そのために以下のプラグインを導入。

vim用のmarkdownのシンタックスファイル。
数年前はバグがあるとか叩かれていたみたいだけど、最近も更新されているようなのでそういうことはもうないと思われる。
少なくとも、僕はまだバグに出会っていない。

編集のプログラムをその場でさっと実行するためのプラグイン。
これを使うことで、markdown記法のテキストをサッと整形してブラウザでプレビューさせることができる。

vimから指定したURLをブラウザで立ち上げるプラグイン。
quickrunと組み合わせて使った。

これらのプラグインを導入した後、vimrcに以下の記述を追加。

let g:quickrun_config = {}
let g:quickrun_config.mkd = {
            \ 'outputter' : 'browser',
            \   'command': 'pandoc',
            \   'exec': '%c --from=markdown --to=html %o %s %a',
            \ }

pandocはmarkdownのテキストをhtmlに変換するコマンド。
他にももっといいのがあるらしいのだが、aptで簡単に導入できるので今回はこれを使った。

これで<Leader>rでブラウザで仕上がりがプレビューできる。

参考：
vim-quickrunとMarkedでmarkdown編集が快適になった - Glide Note -グライドノート
Vim-users.jp - Hack #230: Markdown形式の文書を書く2 (quickrun0.5.0対応版)

本当はリアルタイムでプレビューとかする方法もあるらしいが、とりあえずこれで満足した。

VimShellを久々に使ってみたら便利だった

以前、VimShellを使おうとして入れてみたのだが、はっきりとした理由は忘れたが、いまいちなので使わなかった。
が、久々に使ってみると普通のシェルのように使えるようになっていた。

##install
ここから

導入にはvimprocが必要で、加えてunite.vimとneocomplcacheがないと、一部の拡張機能が使えない。

##使い方
:VimShellでshellになる
インサートモードで入力、コマンドモードでは普通にいつものvimみたいに動いて、
ヤンクとかもできる。
インサートモードではCtrl+lでコマンドの履歴表示、tabで補完がつかえる。
:VimShellPopで画面の一部でVimshellが起動するのでちょっとしたコマンドを起動するには便利。
:VimShellInteractive [任意のインタプリタ]
はスクリプト言語を走らせるのにはかなり便利で、vimで編集しているテキストをそのインタプリタに送りつけるという事ができる。

非同期でコマンドを実行してくれるので、
コンパイルしながらちょっとコードの確認とかいうこともできる。

以前はインタプリタはiexeとかしないと動かなかったんだけど、そういうこともないみたい。

##欠点
bashrcやzshrcとの連携機能は無いので、そっちで独自の設定をみっちりやっていると使いにくいかもしれない。
エイリアスくらいなら自動変換ツールくらい誰かつくっていそうなものだが。

コマンドの補完はやはり賢くない気がする。加えて、個人的にneocomlcacheの動作がイマイチだと思ったので普段は使わないのだが、
これを使わないと、ファイル名補完くらいしか効かない。

あと、gnuplot -persistでプロットしたグラフがgnuplot終了後消えてしまった。

とかまあまあ、完全なシェルとしてはさすがに使えないにしても、十分に使う価値のあるツールだとは思う。
更新も活発だし、作者はzshを目標としているらしいので、これからもどんどん良くなっていくのではないでしょうか。

git pullをrebaseで行う

複数人でリモートのレポジトリをいじるとリモートの変更を
git pullでひっぱって来ないといけないわけだが、
git pullはremoteの変更をgit fetchして取ってきてから、
その変更を自分の追跡ブランチにmergeをするということをしている。
そのため、場合によっては無駄にマージコミットができてしまい、気が分岐しているように見えて、
ログの参照性をさげてしまう。
そこでpull時にmergeの代わりにrebaseを使い、そのようなことを避けるオプションがある。
git pull –rebase

見えないチカラ: 【翻訳】あなたの知らないGit Tipsによると、
git config –global pull.rebase true
としてあげると全追跡ブランチでpull時はオプション無しでrebaseを使うようになる。(Git 1.7.9から)

ただし、rebaseでpullしてくると

1. 追跡ブランチからブランチを切る
2. そのブランチに対して追跡ブランチにマージコミットを打つ（その間、追跡ブランチには何もコミットしていない）
3. 追跡ブランチでpull

とすると、マージコミットが消えて、その追跡ブランチからブランチを切ったという情報が消えてしまった。
これはマージコミットをリバートするときはどちらを残すか明示的に指定しないといけないように、
どちらが本来の流れか分からなくなるからか？
にわかだからよくわかりません＞＜

Gitでのミスリカバリー

##マージコミットをリバート
うっかり間違ったブランチで–no-ffでmergeを打ってしまった場合、
revertでそのコミットの変更を消すコミットをつくることができる。
ただし、このときどちらのブランチを残すのかという事を指示してあげる必要がある。
git logなどで、その時のマージコミットのログを見ると、どのコミット同士をマージしたのかということが書いてある。
それを見てどちらを残すかを-mオプションで指定する。

詳しくはここの80ページ目あたりが親切。

##リモートレポジトリに対してリセットをする
Gitでリモートリポジトリを巻き戻す - @tmtms のメモを参考にした。

まず、リセットしたいレポジトリのバックアップレポジトリをつくる。
これはいざ間違えた時の対策。
git push origin tar_bak

つづいてgit reflogして戻したい地点を見つける
*** HEAD@{0}: hoge
*** HEAD@{1}: hogehoge
*** HEAD@{2}: hogehogehoge
*** HEAD@{3}: hogehogehogehoge
…
hogehogehogeの地点まで戻りたいとして、
git push -f origin HEAD@{2}:tar
とすればよい。こうすると、origin/tarの指すコミットが移動する。

他の人にも影響することなので、やるときは注意。

Ubuntuのgccでリンクのオプションが無視される問題について

Ubuntuを10.04から12.04にアップデートした際、
gccで-lで指定したファイルが全然リンクされないという問題があった。
たとえば、
gcc -lm main.c
として、main.cで普通にmathライブラリを使うようなファイルを書くと、
そんな関数の実体見つからんよ、と怒られていた。

ちょっと検索したらこんなの見つかった。
Ubuntu日本語フォーラム / math.h へのリンクがうまくいかない
どうやら、Ubuntuのあるバージョンからgccの–as-neededというオプションが
デフォルトで有効になるような親切設計になったらしく、
これがあると-lのオプションはソースファイルの後に置かないと無視されるようになるらしい。
なので、
gcc main.c -lm
とすればいいのだが、makeの暗黙ルールでLDFLAGSはソースの前に置かれるようなっているので、なんかルール書き換えるのは癪。

そこで、LDFLAGSに
-Wl,–no-as-needed
というオプションを追加してやると、–as-neededオプションが無効化された。

しかし、なんでこんなオプションをデフォルトで有効にしてしまったのか。

gitでのbranchでの開発

最近何かとgitを使うことが多くなったので、branchの作り方から
mergeの仕方まできちんと学ばなきゃなと思い立って色々調べた。

##リモートブランチの扱い方
“gitのリモートブランチを使って作業を行う流れのメモ - 那由多屋 開発日誌”

##merge
ブランチつくったら、あとでマージしなきゃいけない。
実はgitのマージにはいくつか種類があるらしく、これはきちんと把握しておく必要が有りそう。
“図で分かるgit-mergeの–ff, –no-ff, –squashの違い - アジャイルSEを目指すブログ”
これを読む限り、基本的には–no–ffでマージコミットをきちんとつくるのが
あとでログ見返すときにも良さそうな気がする。

##うっかりマージミスした時の対処。
commitを取り消すコマンドであるresetは使い方を誤るととんでもないことになるので気をつけなければならない。
このへんが参考になりそう。
git で merge をとりけす法 - ToMmY Makes Love with Codes
~nabeken/diary/ : git で間違って merge してしまった場合 (fast forward でマージしてしまったのを取り消したい)

##rebaseコマンドについて
誰かがrebaseコマンド使えない奴はgit使えるうちに入らないと言っていたので調べた。
コミットに対して直接変更を加えるので危ないことは確かっぽいが、
小さなmergeをしたい時とかはこっちのほうが良いのかもしれない。
少なくとも知っておいて損はないと思うので。
図で分かるgit-rebase - アジャイルSEを目指すブログ

##間違ったブランチを変更してしまった！
gitならこんなことまで出来るんだって感じ。
記事読んで理解するのにちょっと時間かかった。
別のトピックブランチにしてしまった複数のコミットを移動する - ToMmY Makes Love with Codes