|
これは、Competitive Programming Advent Calendar Div2012の14日目の記事です。
前回、（Verifyについてはもっと効率の良い手法を考えていますがいつ完成するかわかりません…。）と書きましたが、今回はその中身についてです。
ライブラリが正しく動くことを確かめることをVerifyと言いますが、「正しい」とはどういうことか考えてみます。
アルゴリズムが「正しく」、それを「正しく」実装しているライブラリは「正しい」と言えます。
きちんと定義してやると…などとやっているとめんどくさい上、実用上意味がなくなってしまいます。
競技プログラマーならこう答えるべきです。
「入力に対して正しく出力するライブラリは正しい」
いわゆる「通れば正義」です。
じゃあどうやって正しく出力していることを確認するかという話になります。
何かのライブラリを作った時にそのライブラリを使う問題を使ってVerifyすることはよくあります。
しかしこの方法だと問題を探す手間がかかりますし、一部バグっていても答えに影響を及ぼさないためバグが発見できないことがあります。
そこで、Verify用問題集を作ることによって機能毎に正確なVerifyをできるようにすればいいというのが今回の結論です。
Verify用問題集に必要な機能は以下の２つです。
→どう見てもrimeです。本当にありがとうございました。
rimeとはnya3jp氏によって作成された問題セット作成補助ツールです。
rimeの問題セットとしてVerify用問題集を作ればローカルでライブラリのVerifyを行うことができます。
ただし、問題集に入っていないアルゴリズムを実装したときは比較対象がないため正しいかどうかわかりません。
問題集は十分に充実していなければなりませんが、１人で全部構築することはとてつもなく大変です。
というわけで「集合知」です。
Githubに僕の作った問題集がありますので、ここにpull requestしていただければ問題集が充実してみんな幸せになれます。
まだ幾何の一部しか問題をセットしていません。みなさんのpull requestお待ちしております。
というわけで、他力本願なライブラリVerify方法の紹介でした。ではでは〜。
