Go Home [AtCoder Beginner Contest 056 C] - 文系プログラマーのプログラミング備忘録

①数直線上の0の地点にカンガルーがいる。
②カンガルーは時刻iのとき、負もしくは正の方向へiだけ移動できる。
③カンガルーが座標xに到着する時刻の最小値を求めよ。

x=16のときを考えてみます。

カンガルーは時刻5以内にxに到着することができません。なぜなら、仮に毎時刻移動したとしても、1+2+3+4+5=15となり、座標15の地点までしか進めないからです。一方、カンガルーは時刻6以内に、必ずxに到着することができます。時刻1に1進み、時刻2,3のときは休憩、時刻4,5,6のときにそれぞれ進むことで、1+4+5+6=16となり、時刻6で座標16に到着することが可能です。

このことを一般化すれば、「カンガルーがxに到着できる最小の時刻tは、[1,2,3,4,5......t]の等差数列の和が初めてx以上となった時刻である」となります。言い換えれば、等差数列[1,2,3,4,5......t]の総和がx以上なら、必ず、その中からいくつかの数値（部分集合）を足し合わせてxを作り出せる、ということです。このことを証明します。

①数列[1]の総和は1である。[1]からは1を作ることができる。

②数列[1,2]の総和は3である。[1]からは1を作ることができる。2についても、[1]から1の集合を作ることで、残った項の総和が3-1=2となり、作ることができる。3は、全ての項を足すことで作れる。

③数列[1,2,3]の総和は6である。[1,2]からは3以下の数字を全て作れる。4,5についても、[1,2]でそれぞれ2,1の集合を作ることで、残った項の総和が4,5となり、作ることができる。6は、全ての項を足すことで作れる。

④数列[1,2,3,4]の総和は10である。[1,2,3]からは6以下の数字を全て作れる。7以上9以下の数字についても、[1,2,3]でそれぞれ3,2,1の集合を作ることで、残った項の総和が7,8,9となり、作ることができる。10は、全ての項を足すことで作れる。

⑤以上により、総和がxである数列[1,2,3,4,5......t]からは、部分集合を足し合わせることで、x以下の数字を全て作ることができる。

数学の証明をまともにやったことがないので、これで形になっているか不安ですが、おおむね筋は通っていると自負しています。

以下が解答です。

//abc056-c

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int x = sc.nextInt();
		Long temp = 0L;
		for (int i=1; i<=200000; i++) {
			temp += i;
			if (temp >= x) {
				System.out.println(i);
				return;
			}
		}
		
	}
}

1から順に累積和をしていって、総和がx以上になったところで出力して終了です。

ループの回数が200000となっているのは、これだけ回せば総和がx（10億）を超えるだろうと予想して設定しました。実際に200000回累積和したときの値が約200億なので、余裕は充分にあったようです。いま考えると素直にwhileの無限ループを使えばよかったのかもしれませんが、ま、計算回数を考える練習ということで……。