余裕のススメ - Motsu_xe 競プロのhogeやfuga

またわけわからん記事を作りやがって。銀行コンが思いの外早く終わった暇つぶしに付き合ってくれや。

本記事では、その名の通り余裕のススメをしたいと思います。人生何事も余裕を持つことは大事ですよね、そう思いませんか？私はそう思います。ギリギリを生きてもいいことはありません、余裕、そう！余裕を持ちましょう。

本題

まあこのブログは競プロブログなので競プロの話なんですが、コンテスト5分前には飯と風呂を済ませて、考察用紙とPCをちゃんと準備して挑もうね、、、とかいう話ではありません。

全人類の99割が苦手としている、植木算。あるいは剰余時の切り捨て、切り上げ、四捨五入。境界条件とか考えるとき、異常に難しいアレについてのお話です。難しくないですか？難しくないですね。ご静聴ありがとうございました。

もちろん丁寧に考察して、境界がどこになっているのかを調べることは大事ですし、難しい問題でそういうところをサボると後々後悔します。ただ簡単な問題でそこに手間取って今回のようなタイムアタックに乗り遅れてしまってはいけません。そんなときに、思考量を雑に減らせる素敵なテクニックを共有したいと思います。知ってる？ご静聴ありがとうございました。

具体例

今回の銀行コンで2回ほど使いましたし、私自身たまにお世話になるテクニックなので、具体例を交えつつ説明していきます。

ex. 1) 三井住友信託銀行 プログラミングコンテスト2019 C - 100 to 105

問題へのリンク

全部大体100円ですから、個数が大体 $\frac{x}{100}$ 個くらい。個数 $n$ を決めると、 $100n$ 円から $105n$ 円は全て作れることがわかるので、あとは可能性のある個数を全て確かめればいいです。大体 $\frac{x}{105}$ 個から $\frac{x}{100}$ 個くらいだけど、端っこに自信がないなぁ。そんなあなたはギリギリを攻めすぎです。計算量に余裕があるんだから、そんなギリギリを攻めなくていいんです。私のAC解はこちらです。

int main(){
    int x;
    cin>>x;
    for(int i=x/105-2;i<x/100+2;++i){
        if(i<=0) continue;
        int y=x-100*i;
        if(y>=0&&y<=5*i) return cout<<1<<endl,0;
    }
    cout<<0<<endl;
}

端っこよくわからないけど2個ずらせば流石に大丈夫なはずなので、これで雑に提出してACです。後述する方法でもうちょっと楽にかけます。

ex 2) 三井住友信託銀行 プログラミングコンテスト2019 F - Interval Running

問題へのリンク
infinityや0の場合はまあ自明な考察で除外して、 $a_1\lt b_1, a_2\gt b_2, a_1t_1+a_2t_2\gt b_1t_1+b_2t_2$ の場合だけ考えましょう。考察をするとしばらくは1周期で2回交わり、最後に1周期で1回だけ交わったり交わらなかったりして、それ以降は交わりません。なのでまあ二分探索をしたいという気持ちになりました。以下は私のACコードの一部です。

ll l=0,r=s/d+2,m;
    while(r-l>1){
        m=(l+r)>>1;
        if(t1*b1>=m*d+t1*a1) l=m;
        else r=m;
    }
    if(t1*b1==l*d+t1*a1) cout<<2*l<<endl;
    else cout<<2*l+1<<endl;

二分探索時の初期値の決め方は結構めんどいと思います。例えば雑に上限をでかくしてしまうと、今回の場合計算途中でオーバーフローしてしまったりします。しかし、適当な上限だと高さが足りない場合もあります。今回は、適当に考察すると大体 $\frac{s}{d}$ は上限になりうることがわかるので、適当に2足して安全にしています。このように思考を適当にできるので、提出までの時間が多少短くなって良いです。

ex 3) 三井住友信託銀行 プログラミングコンテスト2019 B - Tax Rate

問題へのリンク
大体答えの候補は $\frac{n}{1.08}$ くらいなんですが、正直誤差とか端数とかの処理考えるのがめんどくさいです。よく見ると制約の $n$ が小さいので、候補として $n$ 以下の数字を全て考えます。以下が私のACコードの一部です。

    int n;
    in>>n;
    fr(i,n+1){
        int x=i;
        x*=108;
        x/=100;
        if(n==x) return cout<<i<<endl,0;
    }
    cout<<":("<<endl;

この方法を使えばC問題でもより楽ができましたね。

いかがでしたか？

人生余裕があるのはいいことだなぁという気持ちになってきたんじゃないでしょうか。
ここまで余裕のススメを書いてきましたが、余裕はオススメしません(は？)。雑な境界把握は考察力の低下にも繋がりますし、多少バグを埋め込む確率も上がるかもしれません。今回のような簡単な問題であまり時間を割きたくないというときの小手先のテクニックにすぎないということには留意しておいてください。まああくまで暇つぶし記事です、あんまり参考にしないでね。それでは、さようなら〜！