Topcoder SRM 721 Div1 Easy - RememberWords
問題概要
ある連続した期間の前半d1日で合計w1個の単語を覚え、後半d2日で合計w2個の単語を覚えたい。任意の連続する2日間において覚える単語の数が高々1しか変わらないように単語を覚えるという制約のもとで、このような単語の覚え方が可能か判定せよ。
d1, d2, w1, w2 <= 109
解法
2分探索で前半、後半それぞれの1日に覚える単語数としてありえるものの最大・最小を求める。求めた最大最小の範囲内にある数はすべて端にもっていくことができるので、それで前半と後半を差1以内でつなげることができるかを見ればよい。
最小値は公差1の等差数列の初項になるはず(x, x+1, ... x+d-1という形を試していって、和がはじめにwを超えるときのxが最小値)なのでそれで2分探索をする。最大値も同じように公差-1の等差数列の初項になっているはずだが、こちらの場合は途中で項が0にぶつかる可能性があるので若干面倒。数列の項数をmin(d, 初項)でとればそのケースをカバーできる。
感想
書き直したら通ったけどなんで落ちたのかよくわからない
コード (C++)
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i=0;i<(n);i++) #define REP2(i,m,n) for (int i=m;i<(n);i++) typedef long long ll; class RememberWords { public: string isPossible(int d1, int d2, int w1, int w2) { ll d1min = binsearch_min(d1, w1); ll d1max = binsearch_max(d1, w1); ll d2min = binsearch_min(d2, w2); ll d2max = binsearch_max(d2, w2); cout << d1min << " " << d1max << " " << d2min << " " << d2max << endl; return (d1min - 1 > d2max || d1max + 1 < d2min) ? "Impossible" : "Possible"; } ll sm(ll a, ll n, ll d) { return n * (2 * a + (n - 1) * d) / 2; } ll binsearch_min(ll d, ll w) { ll hi = 1000000000; ll lo = -1; while (hi - lo > 1) { ll mid = (hi + lo) / 2; ll s = sm(mid, d, 1); if (s >= w) hi = mid; else lo = mid; } return hi; } ll binsearch_max(ll d, ll w) { ll hi = 1000000001; ll lo = 0; while (hi - lo > 1) { ll mid = (hi + lo) / 2; ll s = sm(mid, min(d, mid), -1); if (s <= w) lo = mid; else hi = mid; } return lo; } };