MujinProgrammingChallenge2017A問題:eiya解
MUJIN2017のA問題の僕の解法です。
問題はこれ:A: Robot Racing - Mujin Programming Challenge 2017 | AtCoder
考察
1番目のやつよりも2番目のやつの方が先にゴールするには、1番目のやつを2番目のやつが跨ぐ必要がある。
同様に、i<jのときi番目のやつよりもj番目のやつの方が先にゴールするには、i番目のやつをj番目のやつが跨ぐ必要がある。
また、ロボットは一度に1又は2しか移動できないので、跨ぐには下の図のような状況になる必要がある。
図を見れば分かるように、跨がれる側(i)と跨ぐ側(j)の座標の偶奇が違っていれば跨ぐことが可能。
これは跨がれる側が複数あっても同じで、跨がれる側の偶奇が全て同じなら、跨ぐ側は常にその全てを跨ぐことが可能。(跨ぐ側は1動くことで偶奇を調整できる)
よって全てのロボットの偶奇が同じ状態を作り出せば、任意のロボットを任意の順番にゴールさせることが可能なので、通り数は<ロボットの数>!になる。
(通り数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; }