SRM721 Lv1 : RememberWords
作成日：2017.09.28
最終更新日：2017.09.28
問題概要
はじめの$d_1$日で$w_1$個、つづく$d_2$日で$w_2$個単語を覚える。
初日を除いて1日で覚える単語の数は前日との差が$1$以下になるようにしなければならない。
このような単語の覚え方は可能かどうか判定せよ。
制約
$1 \leq d_1 , d_2 \leq 10^9$
$0 \leq w_1 , w_2 \leq 10^9$
考え方
はじめの$d_1$日及びその後の$d_2$日それぞれだけで考えた時は常に可能である。
よって単語を覚え始めてから$d_1$日目と$(d_1 + 1)$日目に覚える単語の数の差が$1$以下にできるかが分かれば良い。
そのために考えるべきことは、$d_1$日目及び$(d_1 + 1)$日目それぞれに覚える単語の数として適切なものの範囲である。
以下はじめの$d_1$日のことのみを考える。
$d_1$日目に覚える単語の数を$n$とする。
この時に連続する2日で覚える単語の数の差が1以下という制約を守ると、覚えられる単語の数は$n - d_1(d_1 - 1)/2$以上$n + d_1(d_1 + 1)/2$以下の範囲に含まれる。
$w_1$はこの範囲に含まれている必要があるから、$w_1 - d_1(d_1 + 1)/2 \leq n \leq w_1 + d_1(d_1 + 1)/2$である。
但し1日に覚える単語が負になることは許されないので、$n \geq 0$が課せられる。
また同じ理由で、$n < d_1 - 1$の時には$w_1 \geq n(n+1)/2$を満たしていなければならない。
後ろの$d_2$日においても同様に$n$の範囲を求めることができる。
これら2つの範囲が2以上離れていれば不可能であり、そうでない場合は可能である。
ソースコード
マクロ等はこちら
class RememberWords {
public:
string isPossible(int d1, int d2, int w1, int w2) {
LL p1 = 0 , p2 = 0;
while((p1+2) * (p1+1) / 2 <= w1) ++p1;
while((p2+2) * (p2+1) / 2 <= w2) ++p2;
LL l1 = max((LL)0,(w1 - (LL)d1 * (d1-1) / 2 + d1 - 1) / d1);
LL r1 = (w1 + (LL)d1 * (d1-1) / 2) / d1;
LL l2 = max((LL)0,(w2 - (LL)d2 * (d2-1) / 2 + d2 - 1) / d2);
LL r2 = (w2 + (LL)d2 * (d2-1) / 2) / d2;
if(d1 > p1) r1 = min(p1,r1);
if(d2 > p2) r2 = min(p2,r2);
--l1;
++r1;
return !(r2 < l1 || r1 < l2) ? "Possible" : "Impossible";
}
};解法まとめ
$d_1$日目、$(d_1 + 1)$日目に覚える単語の数として適切なものを求める。(4-12行)
2つの範囲が2以上離れていれば不可能、そうでない時は可能である。(13-15行)