とりあえずPを素因数分解して、因数ごとのカウントを取る。
なるべくN個の数値に分配してあげることを考えるために、N以上カウントされた因数を抽出、 ２個以上分配できる可能性も考え、Nで割った商を分配する。 ansにはこれらをすべてかけたものを入れてあげる。
また、素因数分解する際には少し高速化をしないと間に合わないので２つ高速化。
一つは因数で検索がヒットした際に、iを最初まで戻さずにもう一度同じ因数をチェックする。
もう一つは因数を調べるときに√Pより検索値が大きくなったらその場で探索を打ち切って、残ったPを因数にする。
from collections import Counter def d(P): c = Counter() i = 2 while (P > 1): if P % i == 0: c.update([i]) P //= i i -= 1 i += 1 if i > P ** 0.5: c.update([P]) break return c def solve(N, P): c = d(P) ans = 1 for k in [k for k, v in c.items() if v >= N]: ans *= k ** (c[k] // N) return ans if __name__ == "__main__": N, X = tuple(map(int, input().split(" "))) print(solve(N, X))
ソースコードはとても短いので思考をもう一度。 1つの木から1つしか取れない石取りゲーム。石取りゲームだったので動的計画法などではなく偶奇で取れると判断。
小さく考える。まず、１本の木に１つのリンゴしかない場合、最後のりんごと取ったほうが勝ちなので"first" １本の木に２つのリンゴがあったら、必ず相手が勝ちとなる状況を作らざるを得ないので"second" 3個のリンゴも同様。assert文にすると以下な感じ。
assert (solve(1, [1]) == "first") assert (solve(1, [2]) == "second") assert (solve(1, [3]) == "first")
次に2本の木にそれぞれ１つのリンゴしかない場合、すべてのりんごを取ればいいので"first" ２個ー１個となってた場合、2個ー０個にして相手に渡すことで、先手が勝てるので"first" ２個ー２個となっていた場合、先手は１個ー１個、２個ー１個の状況、つまり必ず相手が勝ちとなる状況を作らざるを得ないので"second"
assert (solve(2, [1, 1]) == "first") assert (solve(2, [2, 1]) == "first") assert (solve(2, [2, 2]) == "second")
３本の木、４本の木の時も同様に。
assert (solve(3, [1, 1, 1]) == "first") assert (solve(3, [2, 1, 1]) == "first") assert (solve(3, [2, 2, 1]) == "first") assert (solve(3, [2, 2, 2]) == "second") assert (solve(4, [1, 1, 1, 1]) == "first") assert (solve(4, [2, 1, 1, 1]) == "first") assert (solve(4, [2, 2, 1, 1]) == "first") assert (solve(4, [2, 2, 2, 1]) == "first") assert (solve(4, [2, 2, 2, 2]) == "second")
これらから、N本の木として考えたとき、 「すべてが1」の時は"first”が勝て、 「1と2が混在」している場合、1となっている部分をすべて取ってしまえば、「すべてが2」の状況を相手に渡すことができるため、先手が必ず勝てることになる。 「すべてが2」となっていた場合では「すべてが1」か「1と2が混在」を相手に渡さざるを得ず、勝つことができない。
さらにaの値について一般化を考える。 「すべてが２」を相手に渡すためには、「２と３の混在」あるいは「すべてが３」の状況が自分の手番に来ればよい。 さらにこれらどちらかの状況は手番を自分の手番に持ってくるためには「すべてが４」である状況が相手の手番にあればよい。 同様にaが「すべての同じ偶数」について言え、「すべてが同じ偶数」が来たら負ける。
では異なった数の場合はどうなるか。 2本の木に[3, 5]と存在していた場合、先手は[2, 4]とすべてが偶数の状況を後手に渡せばよい。 後手がりんごと取った後は[1, 3], [2, 3], [1, 4]のいずれかの状況となり、いずれの状況においても先手は[0, 2], [2, 2], [0, 4]とすべてが偶数の状況を作って後手に渡すことができる。 これを繰り返していくと、0個となった木を除くことでのいつか「すべてが同じ偶数」となる状況を必ず後手に渡すことができる。ので、先手が勝利する。
逆に最初の状況で[偶数, 偶数]となっていた場合、 後手は先手にすべてが偶数の状況を渡すことができるので後手が勝利する。
ソースコードはかなり簡単になる。pythonのallは便利や。
def solve(N, As):
As = [1 if a % 2 == 1 else 2 for a in As]
if all(a == 2 for a in As):
return "second"
else:
return "first"
if __name__ == "__main__":
N = int(input())
As = [int(input()) for _ in range(N)]
print(solve(N, As))
あとsolve と mainの間にassertは便利ね。 もしassert落ちたらそもそも手のテストができなくなって無駄なテストをすることがない。
初めての二桁順位。Beginner終わったらもうきっと取れないだろうな。。
