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」をかける
- 必要な最小操作回数を求めよ
解法
