2013 TCO Round 1C Easy - TheArray (×○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12455&rd=15585
・最初のスタート位置firstと最後の位置last、移動できる回数nと一度に移動できる最大数dが与えられる。
・スタート位置からn回移動し、最後に最後の位置に到達している必要があるとき、
途中で到達しうる最大の高さを求める。
解き方
・問題として２分探索が使えそう。
・ある位置を考えた時、スタート位置から到達するために必要なターン数と、そこから最後の位置に到達するためのターン数の和がｎ以下であればよさそう。
・２分探索の最小値はスタート位置もしくは最後の位置のうち小さいもの、最後に得られた値と小喜一のうち最大のものが答えになる。
→System Passed
・他の解き方、というか一番わかりやすい解き方として、nは10^6で全探索できるので
各ターンにおいて最初の位置から到達しうる高さ、最後の位置から到達しうる高さのうち最小の
ものを取り、そのうち最大のものを求めれば簡単。
・反省：全探索できる変数、探索を考えてみる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TheArray {
public: int find(int n, int d, int first, int last) {
if(d==0)return max(first,last);
long long low=min(first,last),high=1e+9;
while(high-low>1){
long long mid=(low+high)/2;
long long cnt=0;
cnt+=(labs(mid-first)+d-1)/d;
cnt+=(labs(mid-last)+d-1)/d;
if(cnt>=n)high=mid;
else low=mid;
}
return max((int)low,max(first,last));
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TheArray {
public: int find(int n, int d, int first, int last) {
if(d==0)return max(first,last);
long long low=min(first,last),high=1e+9;
while(high-low>1){
long long mid=(low+high)/2;
long long cnt=0;
cnt+=(labs(mid-first)+d-1)/d;
cnt+=(labs(mid-last)+d-1)/d;
if(cnt>=n)high=mid;
else low=mid;
}
return max((int)low,max(first,last));
}
};
