kmjp's blog

競技プログラミング参加記です

Yosupo Wettbewerb : A : Trouble Busters、B : Muscle Yosupo Returns

その他コンテスト

Yosupo Wetterberbに参加。
A,Bは順調に解くもCでTLE連発して苦戦。
Eもミスを繰り返すも途中でテストケースのミスに気づいてE完答。
…とはいえEリジャッジで順位が下がってしまった。
http://kcs.miz-miz.biz/contest/1027/view/A
http://kcs.miz-miz.biz/contest/1027/view/B

A : Trouble Busters

9個の整数P[1]～P[9]が与えられる。
この整数を3つずつ3組にすることを考える。
グループの数の平均値の最小値を最大化せよ。

9個しか整数が無いのでnext_permutationで総当たりしても間に合う。

int P[10];

int ma=0;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,9) cin>>P[i];
	sort(P,P+9);
	do {
		ma=max(ma,min(P[0]+P[1]+P[2],min(P[3]+P[4]+P[5],P[6]+P[7]+P[8])));
		
	}while (next_permutation(P,P+9));
	
	cout<<ma/3<<endl;
}

B : Muscle Yosupo Returns

3整数A,X,Yが与えられる。GCD(A^X-1,A^Y-1)を求めよ。

答えはシンプルでA^GCD(X,Y)-1。
一応補足しておくと、A^X-1とA^Y-1は以下のように因数分解できる。

  • A^X - 1 = (A-1)(A^{X-1} + A^{X-2} + ... + A + 1)
  • A^Y - 1 = (A-1)(A^{Y-1} + A^{Y-2} + ... + A + 1)

右辺の第2項について、Z=GCD(X,Y)とするとどちらも (A^{Z-1} + A^{Z-2} + ... +1)の倍数となる。
よって求める答えは (A-1)(A^{Z-1} + A^{Z-2} + ... +1) = (A-1)\frac{A^Z-1}{A-1} = A^Z-1。

ll A,X,Y;
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>A>>X>>Y;
	_P("%lld\n",(modpow(A,__gcd(X,Y))+mo-1)%mo);
}

まとめ

Bは一瞬考えるけどシンプルな問題で良かった。