MujinProgrammingChallenge2017A問題:eiya解

MUJIN2017のA問題の僕の解法です。

問題はこれ:A: Robot Racing - Mujin Programming Challenge 2017 | AtCoder

考察

1番目のやつよりも2番目のやつの方が先にゴールするには、1番目のやつを2番目のやつが跨ぐ必要がある。

同様に、i<jのときi番目のやつよりもj番目のやつの方が先にゴールするには、i番目のやつをj番目のやつが跨ぐ必要がある。

また、ロボットは一度に1又は2しか移動できないので、跨ぐには下の図のような状況になる必要がある。

f:id:eiya5498513:20170226105539p:plain

図を見れば分かるように、跨がれる側(i)と跨ぐ側(j)の座標の偶奇が違っていれば跨ぐことが可能。

これは跨がれる側が複数あっても同じで、跨がれる側の偶奇が全て同じなら、跨ぐ側は常にその全てを跨ぐことが可能。(跨ぐ側は1動くことで偶奇を調整できる)

よって全てのロボットの偶奇が同じ状態を作り出せば、任意のロボットを任意の順番にゴールさせることが可能なので、通り数は<ロボットの数>!になる。

f:id:eiya5498513:20170226113502p:plain

(通り数3! = 6通り)

ここからは偶奇が同じ状態を作る方法を考える。

まず偶数と奇数とどちらにそろえるかを決めるが、

・全て奇数に揃えた場合は、1を偶数の位置にずらすことは出来ないので、全てを偶数に揃えなおすことは出来ないかもしれない。

・全て偶数に揃えた場合、全て一つずつ前にずらすことで、常に全てを奇数に揃えられる。

ので、奇数に揃えれば良いことが分かる。

というわけで、前から1,3,5...という風に詰めていけばよい。

もし詰められなかった場合は、その段階で一つ数を減らす(ゴールさせる)必要がある。

ここでゴールさせるロボットの選び方は<今考えているロボットの数>通りある。

実装

左から順番に、数直線の奇数座標上にロボットを並べていく。

ここで、既に数直線上においてあるロボットの個数をnum_ONとする。

座標X以下の奇数の個数は(X+1)/2なので、ロボットがおける場所の個数は(X+1)/2。

i番目のロボットを置くとき、

・num_ON+1 <= (X[i]+1)/2ならばそのまま置ける

・num_ON+1 > (X[i]+1)/2ならば一つ数を減らす(ゴールさせる)必要がある。

全てのロボットを置き終わった後、残りをゴールさせる通り数はnum_ON!である。

コード

Submission #1134037 - Mujin Programming Challenge 2017 | AtCoder

#include <iostream>

#define in std::cin
#define out std::cout

constexpr uint64_t MOD = 1'000'000'007;
int32_t N;
int32_t X[100000];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	//入力
	in >> N;
	for (int32_t i = 0; i < N; ++i)
	{
		in >> X[i];
	}

	uint64_t result = 1;//答えの通り数
	int32_t num_ON = 0;//既に数直線上においてあるロボットの個数
	//全てを奇数座標に
	for (int32_t i = 0; i < N; ++i)
	{
		++num_ON;
		auto standable = (X[i] + 1) / 2;//数直線上の奇数座標の数
		if (standable < num_ON) {
			//埋まっている=>どれかをゴールさせる
			result *= num_ON;
			result %= MOD;
			--num_ON;
		}
	}
	//残りを好きな順番でゴールさせる
	do{
		result *= num_ON;
		result %= MOD;
	}while (--num_ON);
	out << result << std::endl;

	return 0;
}