ででどん

1≦X≦10⁹から条件を満たすXを探します。
sortされた整数列から探すわけなので二分探索が出来そうです。

c++にはlower_boundやupper_boundといった便利なライブラリがありますが、
今回は初めての二分探索なのでまずは自分でいちから作ってみます。

たしか二分探索は半分の位置を見て次調べるのが前か後ろか決めるようなものだったと思うので、

int left=0,right=1e9;
int mid=(left+right)/2; //500000000

とします。
今回の問題の条件を満たすか調べます。

    if(a*mid+b*d(mid)<=x)right=mid;
    else left=mid;

条件を満たす場合には右端を縮めて、
満たさない場合には左端を縮めます。

ちなみにd(mid)は整数midの桁数を返す自作関数です。

int d(int mid){return to_string(mid).size();}

これを何回かループさせて答えを探索するはずなのですが、ループの抜け方がイマイチ分かりません。
安直に左端leftと右端rightが一致したら抜けるようにしてみましょう。

あと、デバッグ用の出力を追記したり、型をlong longで統一させたりしています。

    ll left=0,right=1e9,mid;
    while(right!=left)
    {
        mid=(left+right)/2;
        printf("%lld %lld %lld\n",left,mid,right);
        ll t=a*mid+b*d(mid);
        if(t>x)right=mid;
        else left=mid;
    }
    cout<<mid<<endl;

これにサンプル10 7 100を入れると、

f:id:h1guch:20200212022334j:plain

こうなります。
無限ループです。
ただ答えの9には辿り着けているので嬉しいです。
実際10分くらい9にすら辿り着けなくて悪戦苦闘していたので十分嬉しいのです。

ループ

正しいループの抜け方を考えます。
9と10が境目です。
境目の左側は条件を満たし、右側は条件を満たしませんつまり、このleftが条件を満たす最大値を示します。

whileの抜ける条件をright-left!=1として最後にleftを出力させてみます。

    ll left=0,right=1e9,mid;
    while(right-left!=1)
    {
        mid=(left+right)/2;
        printf("%lld %lld %lld\n",left,mid,right);
        ll t=a*mid+b*d(mid);
        if(t>x)right=mid;
        else left=mid;
    }
    cout<<left<<endl;

こうなります。

f:id:h1guch:20200212022922j:plain

きれいですね。
他のサンプルでも試しましたが、サンプル２以外は上手く機能しました。
サンプル２は2 1 100000000000です。
これはお店に売られている最大整数が買えるパターンです。
このパターンも拾えるように修正をして提出をします。

提出

using namespace std;

ll d(ll mid){return to_string(mid).size();}

main()
{
    ll a,b;
    ll x;
    cin>>a>>b>>x;

    //まず最大整数を買えるのかどうか調べとく
    ll c=1e9;
    if(a*c+b*d(c)<=x)
    {
        cout<<c<<endl;
        return 0;
    }

    ll left=0,right=1e9,mid;
    while(right-left!=1)
    {
        mid=(left+right)/2;
        //printf("%lld %lld %lld\n",left,mid,right);
        ll t=a*mid+b*d(mid);
        if(t>x)right=mid;
        else left=mid;
    }
    cout<<left<<endl;

}

無事ACしました。
とりあえず二分探は寒色系を目指すにあたっての必須科目だと思うので自分の手足のように使いこなせるようになりたいです。
対戦ありがとうございました。

ここまでお読みいただきありがとうございました。

*1:ぬるぬるさんが作られた神サイトです。

精進記録

言語はc++です

はじめての二分探索

ででどん

ループ

提出