CADDi 2018

C - Product and GCD

問題

  • $N$ 個の 正整数 $a_1,a_2,\ldots,a_N$ がある
  • 各値は不明だが、$a_1 \times a_2 \times \ldots \times a_N=P$ がわかっている
  • $a_1,a_2,\ldots,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 \ldots$ とすると、答えは $p_1^{\frac{a}{N}} p_2^{\frac{b}{N}} p_3^{\frac{c}{N}} \ldots$ となる(剰余切り捨て)

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,\ldots,a_N$ がある
  • 以下の操作を繰り返し行って、(広義)単調増加にしたい
    • 数を1つ選んで、「-2」をかける
  • 必要な最小操作回数を求めよ

解法

FIXME



このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2018/1222_caddi2018.txt · 最終更新: 2018/12/25 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0