スポンサーサイト

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

Codeforces Beta Round #17

日本時間で 06/11 00:00~02:00 に開催された、Codeforces Beta Round #17 の参加記録です。

競技のルールは初参加のときの記事を参照。

問題と解答(の一部)は [続きを読む] から。

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

今回は2回目の参加です。
前回のチャレンジでdiv1に上がったので、問題が一気に難しくなりました。

[ 問題 ]
今回の問題セットはこんな感じでした。

A. Noldbach problem
ゴールドバッハならぬ、ノールドバッハ問題。

Nickは素数が好きだ。Nickは次の問題を思いついた。

[ NoldBach Problem ]
2~nの範囲にある素数のうち、少なくともk個は、
k = (隣接する2素数の和) + 1
と書けるか?

n,k(2≦n≦1000, 0≦k≦1000)が与えられるので、yes or no を返す。

B. Hierarchy
Nickの会社にはn人の雇用者がいる。
「上司aiが部下biを賃金ciで雇用する」
というapplication(どう訳す??)がm件与えられるので、合計賃金が最小になるような木構造を求める。
合計賃金を返す。
(ただし、そのような木が作れない場合は-1を返す。)

C. Balance
Nickは文字列を並べ替えるのが大好きだ。Nickは次の問題を思いついた。

a,b,cだけからなる文字列に次の操作
・i番目の文字をi-1番目の文字に上書きする
・i番目の文字をi+1番目の文字に上書きする
を行う。(何度行ってもいい。)
このとき、balanceしている文字列は何通りできるか? (答えは51123987で割った余りとする)

ここで、文字列がbalanceしているとは、各文字の出現数が高々1しか違わないことをいう。

D. Notepad
Nickは10進数が好きではない。そこでNickは別の進数を研究することにした。
n桁のb進数をノートに書いていく。
1ページあたりc個ずつ書いていくと、最後のページには何個の数が書かれているか?
ただし、Nickにはゼロ割りという苦い経験があるので、0は書かない。
(2≦b≦10106, 1≦n≦10106, 1≦c≦109)

E. Palisection
時間なくて問題読んでないよ...


[ 解答 ]
言語は C++。例によって、include文とusing文は省略。

A.
int main()
{
int n,k;
cin>>n>>k;

vector<int> prime;

for(int i=2;i<=n;i++){
bool flag=true;
for(int j=2;j<i;j++){
if(i%j==0) flag=false;
}
if(flag) prime.push_back(i);
}

int noldcnt=0;
for(int i=0;i<prime.size();i++){
for(int j=0;j<prime.size()-1;j++){
if(prime[i]==prime[j]+prime[j+1]+1) noldcnt++;
}
}
if(noldcnt>=k) cout<<"YES";
else cout<<"NO";

return 0;
}

書くだけ。エラトステネスの篩。

B. (時間外)
int rel[1000][1000];

int main()
{
int n; cin>>n;

vector<int> q(n);
for(int i=0;i<n;i++) cin>>q[i];

int m; cin>>m;

int a,b,c;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)rel[i][j]=INT_MAX;
for(int i=0;i<m;i++){
cin>>a>>b>>c;
rel[a-1][b-1]=min(rel[a-1][b-1],c);
}

int leader=max_element(q.begin(),q.end())-q.begin();

int cost=0;
for(int i=0;i<n;i++){
if(i==leader) continue;

int opt=INT_MAX;
for(int j=0;j<n;j++){
if(q[i]>=q[j]) continue;
opt=min(opt,rel[j][i]);
}
if(opt==INT_MAX){ cout<<-1; return 0; }
else cost+=opt;
}

cout<<cost;

return 0;
}

問題読解に時間がかかり、競技中には間に合わず...
問題の意味さえわかればこっちのもので、自分よりqualificationが上の人からのapplicationのうち、コスト最小のものを選んでいくだけ。上の人からのapplicationがなければ木構造が作れないので return -1;

C.以降は解けず。またの機会に考えよう。

C. (時間外)
const int L=51123987;
int memo[150][51][51][51]; // [used string position][count a][count b][count c]

int main()
{
int n;
char s[151];
scanf("%d%s",&n,s);

int trans[150][3]; // destination index table
for(int i=0;i<n;i++){
trans[i][0]=trans[i][1]=trans[i][2]=777;
for(int j=i;j<n;j++) trans[i][s[j]-'a']=min(trans[i][s[j]-'a'],j);
}

int abcmax=(n+2)/3;
memo[0][0][0][0]=1;
for(int i=0;i<n;i++){
for(int a=0;a<=abcmax;a++)for(int b=0;b<=abcmax;b++)for(int c=0;c<=abcmax;c++){
for(int j=0;j<3;j++){
if(trans[i][j]==777) continue;
int nexta=a+(j==0),nextb=b+(j==1),nextc=c+(j==2);
if(nexta<=abcmax && nextb<=abcmax && nextc<=abcmax)
memo[trans[i][j]][nexta][nextb][nextc]
=(memo[trans[i][j]][nexta][nextb][nextc]+memo[i][a][b][c])%L;
}
}
}

int cnt=0,a=n/3;
for(int i=0;i<n;i++){
if(n%3==0) cnt=(cnt+memo[i][a][a][a])%L;
if(n%3==1) cnt=(cnt+memo[i][a+1][a][a]+memo[i][a][a+1][a]+memo[i][a][a][a+1])%L;
if(n%3==2) cnt=(cnt+memo[i][a+1][a+1][a]+memo[i][a][a+1][a+1]+memo[i][a+1][a][a+1])%L;
}
printf("%d\n",cnt);

return 0;
}

[2010/10/16 追記]
Codeforce #33 Cを解いたことで、やっと解答の方針が見えてきたので改めて考えてみました。

入力された長さ n の文字列 s の i 文字目を si と書くと、これは
正規表現 : s0*s1*...*sn-1*
にマッチする長さ n の文字列の中でバランスしているものの数を数える問題。

バランスしているかどうかの判定には、文字列そのものではなく文字'a','b','c'の出現回数さえわかっていれば十分であることがポイント。

memo[i][a][b][c] は、正規表現をsiまで進めたときにできる部分文字列、即ち
s0*s1*...*si-1*si+
にマッチする文字列の中で、文字'a'が a 個、文字'b'が b 個、文字'c'が c 個、使われているものの総数。
この情報を使って、i=0,1,...,n-1 のときのmemo[i][a][b][c]を順次決定していくことができる。

より詳しくは、pes_magic氏のブログ
徒然とコード書き 2010/06/14の記事
に書かれています。私も参考にさせてもらいました。


D.については、計算すべき式が
(b-1)・bn-1 mod c
だということはすぐに判ったけど、多倍長計算のコードが書けず。

一応、上式を導出しておくと、
n桁までのb進数が bn 個、n-1桁までのb進数が bn-1 個あるので、
ちょうどn桁のb進数は、これらの差をとって (b-1)bn-1 個。
cで割った余りが答え。



結局、1問しか解けず、ratingは15681482に下がりました。div2に降格です
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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