企業コンですが実質 ARC です。

## CADDi 2018

問題一覧：

## C - Product and GCD

問題概要：長さ N の正の整数からなる数列 A(i) について、要素の積が P に等しい。数列の最大公約数として可能な最大値を求めよ。

考察：仮に最大の最大公約数が g だとすると、 P は次のようにかけます。

P = (g・A(1)/g)・(g・A(2)/g)・ ... ・(g・A(N)/g) = g^N・X

このから、g は P において重複度が m の素因数 p を (m / N) 個含むような値になります。(「約数75の回」の考察の繰り返しになるので詳細は略。)

筆者の回答[AC]

## D - Harlequin

問題概要：色 c(i) のりんごが a(i) 個ある。以下のルールでゲームを行うとき、先手必勝か後手必勝である。どちらが必勝かを判定せよ。

1. 先手は **各色につき最大1個のりんごを食べる** 。ただし少なくとも1つのりんごを食べる。これによってすべてのりんごを食べたら勝利する。
2. 先手と後手を入れ替えて、同じことを繰り返す。

考察：まず答えをいうと、 a(i) のいずれかが奇数なら先手必勝、そうでなければ後手必勝です。例えば、りんごの個数が 1-0-0-... なら先手の勝ちです。2-2-0 なら後手の勝ちになります。

正当性について考えます。はじめの時点でりんごの個数が奇数である色あったら、先手はその奇数になっている色のりんごをすべて食べることで「りんごの個数がすべて偶数」の状態にできます。後手はどのように食べても、「りんごの個数のいずれかが奇数」である状態でターンを返すしかありません。

そのため **先手は常に「りんごの個数がいずれかが奇数」である状態でりんごを食べる** ので、最後のりんごを食べるのは先手であることが分かります。

逆にはじめから「りんごの個数がすべて偶数」ならちょうど正反対になり、後手必勝です。

どちらかというと上記の解法をいかにして見つけ出すかがポイントです。見た瞬間に閃けばいいんですけど。

ゲーム問題には定石がいくつかあって、たしか「Grundy 数を計算する」とか「ゲーム展開の逆順に考える」とかがありました。今回は前者が助けになります。

「各色のりんごが何個あるか」をゲーム状態と呼ぶことにします。はじめに、ゲーム状態の略記法を定義しておきます。例えば3色のりんごがそれぞれ 2, 1, 0 個あることを 2-1-0 と表すことにします。

状態 S の Grundy 数 G(S) というのを考えます。G(S) は S の「次の状態」としてはありえない最小の自然数です。

状態 S = 0-0-0-... ではりんごを食べられないので、「次の状態」というのはありません。G(S) = 0 です。

状態 S = 1-0-0-... の次の状態は 0-0-0-... だけです。このとき「次の状態の Grundy 数としてはありえない自然数」は 0 以外なので、G(S) = 1 です。

状態 S = 2-1 の次の状態は 2-0, 1-1 の2つです。それぞれ G(2-0) = 0, G(1-1) = 2 になります。次の状態の Grundy 数としてありえるのが 0, 2 なので、ありえない数の最小値は G(2-1) = 1 です。

先手のはじめの状態 S が G(S) ≠ 0 なら先手必勝です。実際、先手は必ず後手に G(S') = 0 の状態 S' でターンを渡せます。しかも、後手は G(S'') ≠ 0 となる状態 S'' で先手にターンを戻すしかないです。そのため、最後のりんごを食べるのは G(S) ≠ 0 の状態でりんごを食べる先手しかありえないといえます。

さて、具体例を樹形図で書き下して、各状態の Grundy 数を計算してみます。Grundy 数が 0 になるところでは 0-0-0 とか 0-2-2 みたいに偶数だけが現れている、という法則性がみつかる……かもしれません。

筆者の提出[AC]

## おわりに

D完でした。