スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Round #107

2012/02/18 00:00~02:00 (JST)
Codeforces Round #107 の参加記録

Tags : プログラミング Codeforces 未解決

結果

A. AC (00:47)
B. AC (01:05)
C. -
D. -
E. -
hack : 1 miss
Standing : 224/612
Rating : 20091966


問題

問題セットの原文はここを参照。

A. Win or Freeze

二人でターン制のゲームをする。
最初、正整数 q がある。
各ターン、q を q の自明でない約数 ( 1 と q 以外の約数 ) に置き換える。
操作ができなくなった方が勝ち。

先手必勝か後手必勝か?
先手必勝の場合は最初に打つ手も求めよ。

1 ≦ q ≦ 10^13

B. Quantity of Strings

m 種類以下のアルファベットからなる長さ n の文字列で、長さ k の任意の部分文字列が回文となるようなものは何通りあるか? mod 10^9+7 で求めよ。

1 ≦ n ≦ 2000
1 ≦ m ≦ 2000
1 ≦ k ≦ 2000

解答

言語は C++。テンプレはここを参照。

A.
map<ll,int> prime_factorize(ll a){
map<ll,int> res;
for(ll p=2;p*p<=a;p++) if(a%p==0) {
int cnt=0;
do{ a/=p; cnt++; }while(a%p==0);
res[p]=cnt;
}
if(a>1) res[a]=1;
return res;
}

int main(){
ll a; cin>>a;
map<ll,int> pf=prime_factorize(a);
map<ll,int>::iterator it;

int n=0;
for(it=pf.begin();it!=pf.end();++it) n+=it->second;

if (n<=1) cout<<1<<endl<<0<<endl;
else if(n==2) cout<<2<<endl;
else{
ll ans=1;
n=0;
for(it=pf.begin();it!=pf.end();++it) rep(j,it->second) {
if(n<2){
ans*=it->first;
n++;
}
}
cout<<1<<endl<<ans<<endl;
}

return 0;
}

素因数分解したときの指数を石の数とする Nim かなーと思って考えてたけど、複数の山から一度に取れる形になっていてよくわからない。

でも、よく考えてみたらほとんど自明で、一手で詰みに持っていける。
相手の手番で二つの素数の積が残るようにできたら勝ち。

ありえないくらい時間がかかってしまった。

B.
const ll M=1000000007;

int main(){
int n,m,k; scanf("%d%d%d",&n,&m,&k);
if(n<k || k==1){
ll ans=1;
rep(i,n) ans=ans*m%M;
printf("%d\n",(int)ans);
}
else if(n==k){
ll ans=1;
rep(i,(n+1)/2) ans=ans*m%M;
printf("%d\n",(int)ans);
}
else{
if(k%2==0) printf("%d\n",m);
else printf("%d\n",m*m);
}

return 0;
}

問題を見たときの第一印象として、条件がかなり厳しいなぁと思った。
こんな条件をみたす文字列なんてそうないだろうというところからはじめて、あとは細かい場合わけをしていった。

n < k or k==1 のときは、どんな文字列でも OK。
n==k のときは、文字列自体が回文であればいい。
n > k のときは、k が偶数なら aaaa みたいなののみ OK で、k が奇数なら aaaa と abab が OK。

今回は運良くすべてを網羅できていて正解だったけど、もっと確実な解法を探すべきだった。

Union-Find で等しくならないといけない文字を分類する方法がいい。
Codeforces Beta Round #28 B. pSort が類題。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。