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行)

SRM721の他の問題 Lv2 Lv3

広告

自己紹介

プログラミングとかUTAUとかドット絵とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告