cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
ほげ2012/07/04 00:51自分は while(L<R) で回して if(query(C)) R=C; else L=C+1; の更新式でした。閉区間[L,R]で考えて、query(C) == false の時は C を閉区間から追い出して良いので次の範囲は[C+1,R]になる感じです。ループ終了条件と返す値は分かり易いのですが、条件を満たす側が逆な場合等に丸め方向と更新式を変える必要があるのがネックでした。半開区間の方が扱い易そうですね。
cafelier2012/07/04 02:21コメントありがとうございます。> query(C) == false の時は C を閉区間から追い出しこういう考え方を知りたかったのです！なるほど、閉区間で書くイメージもできてきました。どのやり方も一長一短あるとは思うのですが、特にTopcoderで他人のコードを読むときに、自分のスタイルと違うのを見て詰まってしまう自分が勿体ないなあと思いまして。
cafelier2012/07/22 18:09「閉区間 & trueでもfalseでもmidを常に追い出す」という方針を教えていただいた。なるほど。https://twitter.com/nabesan_tofu/status/226959241632690178https://twitter.com/nabesan_tofu/status/226964459439136768
presented by cafelier/k.inaba under
閉区間[L,R]で考えて、query(C) == false の時は C を閉区間から追い出して良いので次の範囲は[C+1,R]になる感じです。
ループ終了条件と返す値は分かり易いのですが、条件を満たす側が逆な場合等に丸め方向と更新式を変える必要があるのがネックでした。
半開区間の方が扱い易そうですね。
> query(C) == false の時は C を閉区間から追い出し
こういう考え方を知りたかったのです！なるほど、閉区間で書くイメージもできてきました。
どのやり方も一長一短あるとは思うのですが、特にTopcoderで他人のコードを読むときに、自分のスタイルと違うのを見て詰まってしまう自分が勿体ないなあと思いまして。
https://twitter.com/nabesan_tofu/status/226959241632690178
https://twitter.com/nabesan_tofu/status/226964459439136768