CADDi 2018

C - Product and GCD

問題

$N$ 個の正整数 $a_1,a_2,...,a_N$ がある
各値は不明だが、 $a_1 \times a_2 \times ... \times a_N=P$ がわかっている
$a_1,a_2,...,a_N$ の最大公約数として考えられるものの最大値を求めよ

例

$N = 3, P = 120$ の場合、2, 6, 10 などで「2」が最大公約数となる

解法

ある数 $k$ が $N$ 個の数の最大公約数なら、 $P$ は $k$ が $N$ 回掛け合わされているので、 $k^N$ の倍数でないといけない。

逆に考えると、 $P$ を素因数分解したときに $N$ 以上の指数がある素因数は、各 $a_i$ に均等に分配した方がよい。

$P=p_1^a p_2^b p_3^c ...$ とすると、答えは $p_1^{\frac{a}{N}} p_2^{\frac{b}{N}} p_3^{\frac{c}{N}} ...$ となる（剰余切り捨て）

        
              from collections import defaultdict
 
def solve(n, p):
    if n == 1:
        return p
    i = 2
    ps = defaultdict(lambda: 0)
    while i * i <= p:
        while p % i == 0:
            p //= i
            ps[i] += 1
        i += 1
    ans = 1
    for p, c in ps.items():
        ans *= p ** (c // n)
    return ans
 
n, p = map(int, input().split())
print(solve(n, p))

D - Harlequin

問題

$N$ 色のりんごがあり、 $N$ 種類の色には1から $N$ までの番号が振られている
$i$ 番の色のりんごは $a_i$ 個ある
以下のゲームを、交互に行う
- 木から1個以上のりんごを選んで食べる
- 一度に選ぶりんごは全て異なる色でなければならない
- 木から最後のりんごを食べた者を勝者とする
勝つのは先手、後手どちらか
$1 \le N \le 10^5$
$1 \le a_i \le 10^9$

解法

「横向きNim」として解いたが、何か間違ってる予感……。

石取りゲーム(Nim) は、複数の石山があり、互いに石を1個以上ずつ取っていって、最後に取った方が勝ちというゲーム。一度に1つの石山からしか取ることができない。

結論だけ言うと、初期状態で、各山の石の個数のXORが0なら後手必勝、それ以外なら先手必勝となる。

それを横向きにすると、今回の問題とよく似ているように見える。

Nim            この問題
○             色1 ○
○  ○         色2 ○ ○
○  ○         色3 ○ ○
○  ○  ○     色4 ○ ○ ○
山1 山2 山3

どちらも、一度に縦方向にしか取ることはできない

なので、1～ $max(a_i)$ のそれぞれで、「 $k$ 個以上ある色はいくつあるか」を求めれば、それを各山の石の個数と見做すことで、Nimにできる。

ただ、 $a_i \le 10^9$ なので愚直にやるとTLE。

ここで、石の個数が同じ2つの山＝XORで互いに打ち消し合うことを考えれば、リンゴの個数が少ない順にソートして、1つ前の個数との差分が偶数なら全て打ち消しあい、奇数の時のみ余った1つ分を考慮すれば良い。

色1 ○○....○○
色2 ○○....○○○○....○○
色3 ○○....○○○○....○○○○○
    `--------'  `----------'`--'
        偶数個＝打ち消し合う
    ↓
色1           ○
色2           ○
色3           ○                ○

ただ、解説の解法は「全ての色で個数が偶数個なら後手、それ以外は先手必勝」となっていて、たしかに解説の証明の通りなので、上の解法はどこかおかしい。

        
          
          
              
              import sys
from collections import Counter
 
n = int(input())
aaa = [int(line) for line in sys.stdin.readlines()]
cnt = Counter(aaa)
nim = 0
mnt = 0
prev_i = 0
for i, c in sorted(cnt.items()):
    di = i - prev_i
    mnt += c
    if di % 2 == 1:
        nim ^= mnt
    prev_i = i
print('first' if nim > 0 else 'second')

            

        
      

E - Negative Doubling

問題

$N$ 個の正整数列 $a_1,a_2,...,a_N$ がある
以下の操作を繰り返し行って、(広義)単調増加にしたい
- 数を1つ選んで、「-2」をかける
必要な最小操作回数を求めよ

解法

1