yukicoder No.91 赤、緑、青の石
考えたこと
「あることが成り立つときの最大値」を求めれば良いため、
- アクセサリーを個作ることが出来るかどうかを調べる関数を作る。
- の値で二分探索する。
とすることで答えを求めることが出来ます。
コード(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について
アクセサリーが個作れるかを判断するにあたって、まず各からを引きます(その値をそれぞれとおきます)。
このとき、が全て非負整数であれば、アクセサリーを個作ることが出来るのは明らかですね。
しかし、の中に負の整数が存在した場合、値が正であるものから引いて負のものに加える、という作業が必要です。
この作業を全てのが正になるまで行うのは大変ですし、アクセサリーを個作れないときは、作れないと判断するまでループすると時間がかかってしまいます(それでも間に合うかもしれませんが)。
そこで、次のことを行いました。
ll changeableNum = 0; for(auto i : stone){ changeableNum += (i>0) ? i/2 : i; }
ここでlong long int型変数changeableNumというものを作っていますが、これは「他の色の石を作ることが出来る数」を格納する変数です。
ある石に対して、アクセサリーを個作ってもまだ石が個余っているとき、このchangeableNumにその余りをで割ったものの整数部分を加えます。
また、アクセサリーを個作るのに石が個足りないときは、このchangeableNumからを引きます。
そして最終的に、changeableNumが非負になった場合、「アクセサリーを個作ってもまだ石が余っている、あるいはちょうど使い切った」ということがわかるので、条件を満たすためtrueです。
一方、changeableNumが負になった場合、「アクセサリーを個作るにはあと個足りない」ということがわかるので、条件を満たさないためfalseです。
あとはこの条件calcを二分探索の関数BinarySearchに渡してやればOKです。
二分探索の初期位置について
問題の条件より、アクセサリーは最低個、最大で個作ることが出来ます。
よって、lowは、highはであることからとしました。
備考
二分探索の範囲をからとしているため、ループは回だけであり、実行時間制限に関しては全然問題ありません。
感想など
「『あることが成り立つときの最大値』には二分探索を用いれば高速に計算できる」ということが分かれば簡単にACすることが出来ますね。
問題を見て「これ二分探索かな?」と見極められるようになりましょう(自分へのメッセージ)。