yukicoder No.91 赤、緑、青の石

問題

考えたこと

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

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

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

コード(C++)

#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にその余り $i$ を $2$ で割ったものの整数部分を加えます。
また、アクセサリーを $n$ 個作るのに石が $j$ 個足りないときは、このchangeableNumから $j$ を引きます。

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