読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

yukicoder No.91 赤、緑、青の石

問題

問題のURLはこちらです。
No.91 赤、緑、青の石 - yukicoder


考えたこと

「あることが成り立つときの最大値」を求めれば良いため、

  1. アクセサリーをn個作ることが出来るかどうかを調べる関数を作る。
  2. nの値で二分探索する。

とすることで答えを求めることが出来ます。


コード(C++)

#85548 No.91 赤、緑、青の石 - yukicoder

#include <iostream>
#include <functional>
#include <vector>
#include <cmath>

using ll = long long int;

ll BinarySearch(ll low, ll high, std::function<bool(ll)> check){
    if(high-low==1){
        return low;
    }
    ll mid = (high+low)/2; 
    if(check(mid)){
        return BinarySearch(mid, high, check);
    }else{
        return BinarySearch(low, mid, check);
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    ll R, G, B;
    std::cin >> R >> G >> B;
    
    auto check = [=](ll n) -> bool {
        std::vector<ll> stone({R-n, G-n, B-n});
        ll changeableNum = 0;
        for(auto i : stone){
            changeableNum += (i>0) ? i/2 : i;
        }
        return changeableNum>=0;
    };
    std::cout << BinarySearch(0, std::pow(2, 24), check) << "\n";
    
    return 0;
}

コードの説明など

以下のコード二分探索に用いている関数BinarySearchについてはこちらの記事を参照してください。
satanic0258.hatenablog.com

二分探索の条件calcについて

アクセサリーがn個作れるかを判断するにあたって、まず各R,G,Bからnを引きます(その値をそれぞれr,g,bとおきます)。

このとき、r,g,bが全て非負整数であれば、アクセサリーをn個作ることが出来るのは明らかですね。
しかし、r,g,bの中に負の整数が存在した場合、値が正であるものから2引いて負のものに1加える、という作業が必要です。

この作業を全てのr,g,bが正になるまで行うのは大変ですし、アクセサリーをn個作れないときは、作れないと判断するまでループすると時間がかかってしまいます(それでも間に合うかもしれませんが)。


そこで、次のことを行いました。

ll changeableNum = 0;
for(auto i : stone){
    changeableNum += (i>0) ? i/2 : i;
}

ここでlong long int型変数changeableNumというものを作っていますが、これは「他の色の石を作ることが出来る数」を格納する変数です。

ある石に対して、アクセサリーをn個作ってもまだ石がi個余っているとき、このchangeableNumにその余りi2で割ったものの整数部分を加えます。
また、アクセサリーをn個作るのに石がj個足りないときは、このchangeableNumからjを引きます。

そして最終的に、changeableNumが非負になった場合、「アクセサリーをn個作ってもまだ石が余っている、あるいはちょうど使い切った」ということがわかるので、条件を満たすためtrueです。
一方、changeableNumが負になった場合、「アクセサリーをn個作るにはあと|changeableNum|個足りない」ということがわかるので、条件を満たさないためfalseです。


あとはこの条件calcを二分探索の関数BinarySearchに渡してやればOKです。

二分探索の初期位置について

問題の条件より、アクセサリーは最低0個、最大で10^7個作ることが出来ます。
よって、lowは0、highは2^{23}<10^7<2^{24}であることから2^{24}としました。


備考

二分探索の範囲を0から2^{24}としているため、ループは24回だけであり、実行時間制限に関しては全然問題ありません。


感想など

「『あることが成り立つときの最大値』には二分探索を用いれば高速に計算できる」ということが分かれば簡単にACすることが出来ますね。
問題を見て「これ二分探索かな?」と見極められるようになりましょう(自分へのメッセージ)。