CADDi 2018 - mini notes

C問題 Product and GCD (300)

C - Product and GCD

概要

ある整数 $P$ について、 $N$ 個の整数を用いて $a_{1} * a_{2} * ... * a_{N} = P$ と表したとき、
$a_{1}, ... , a_{N}$ の最大公約数の最大値を求めよ。

方針

$N=1$ なら最大公約数は $P$ となる。
$N>1$ の時は素因数分解する。
なるべく素因数が $a_{i}$ にばらけるように分配する。

感想

素数を配列にいれるとセグフォしたので、mapに入れた。

解答

Submission #3851638 - CADDi 2018

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll n, p;
	cin >> n >> p;
 
	if(n == 1){
		cout << p << endl;
		return 0;
	}
 
	int sqp = (int)sqrt(p) + 1;
	map<int, int> mp;
 
	for(int i = 2; i <= sqp; i++){
		while(p % i == 0){
			auto it = mp.find(i);
			if(it == mp.end()) mp[i] = 0;
			mp[i]++;
			p /= i;
		}
	}
 
	int ans = 1;
	for(auto itr = mp.begin(); itr != mp.end(); ++itr){
		int k = itr->first;
		int v = itr->second;
 
		while(v >= n){
			ans *= k;
			v -= n;
		}
	}
	cout << ans << endl;
}

D問題 Harlequin (500)

D - Harlequin

概要

「 $a_{1}, ... , a_{N}$ の各 $a_{i}$ について、 $a_{i}\geq0$ ならば1を引くかそのままにする」という操作を交互に繰り返すゲームを考える。
すべての $a_{i}$ を0にしたプレイヤーを勝ちとしたとき、与えられた $a_{i}$ について、先手が勝つか後手が勝つかを答える。

方針

結論としては、すべての $a_{i}$ が偶数なら後手が勝ち、それ以外なら先手が勝つ。
理由は、「すべての $a_{i}$ が偶数である」という状態をOとすると、この状態からプレイヤーがどのような操作を行っても、
その後のプレイヤーがその操作をまねることでOという状態を維持できるため。

感想

問題を解いているときは、奇数が入るケースにとらわれすぎた感があった。
「2 2 2」のケースを実際に解き、「あれ、全部偶数なら後手必勝？」のような気付きがあれば解けたかもしれない。

解答

Submission #3852328 - CADDi 2018

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll n;
	cin >> n;
 
	ll a[n];
	rep(i, n) cin >> a[i];
 
	bool ok = true;
	rep(i, n) if(a[i] % 2 == 1) ok = false;
 
	cout << (ok ? "second" : "first") << endl;
}