スポンサーサイト

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

Codeforces Beta Round #26

日本時間 8/17(火) 0:00~2:00 に催された、codeforces 第26回 の記録です。

試験期間とかぶったせいで第24,25回目の競技に参加できなかったので、ずいぶん久しぶりのcodeforcesでした。
なお、今回のルールは Codeforces format (SRMっぽいの) です。

問題と解答は [ 続きを読む ] から。

Tags : プログラミング Codeforces

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

A. Almost Prime
2つの異なる素数でのみ割り切れる自然数を「ほぼ素数」ということにする。
3000以下の自然数 n が与えられるので、1以上n以下の「ほぼ素数」の数を求める。

B. Regular Bracket Sequence
「(」と「)」だけからなる106文字以下の文字列が与えられる。
この文字列からいくつかの括弧を取り除いて正しい括弧付けにすることを考える。
このようにして得られた正しい括弧付け文字列のうち、長さ最大のものを求める。出力するのは長さだけ。

C. Parquet
面積 n×m の部屋に次の形状のタイル(寄せ木)を敷き詰めることを考える。
タイルの形状は3通りある。

type1 : 1×2
□□

type2 : 2×1



type3 : 2×2
□□
□□

今、type1のタイルが a 枚、type2のタイルが b 枚、type3のタイルが c 枚ある。
部屋を敷き詰めることができれば、具体的な敷き詰め方†を1通り示す。できなければIMPOSSIBLEと出力する。
なお、使わないタイルがあってもよく、タイルを回転させることはできない。

† 小文字アルファベットのみ使うことができる。同じタイルには同じ文字を用い、隣接するタイルと同じ文字を使ってはいけない。

例) 2×6の部屋
aabcca
aabdda


D. Tickets
Charlieは1枚10ユーロのチケットを売っている。今、Charlieの手元には k 枚の10ユーロ紙幣がある。
n 人の10ユーロ紙幣を持った客と、m 人の20ユーロ紙幣を持った客がランダムな順番でチケットを買おうとしている。Charlieが全ての客をさばける(釣りが切れない)確率を求める。
( 0≦n≦105, 0≦m≦105, 0≦k≦10 )

E. Multithreading
N個のプロセスを使って並列計算する。
i番目のプロセスは
repeat ni times
 yi := y
 y := yi + 1
end repeat

という擬似コードにしたがって動作する。
y は全プロセスで共有する変数、yi は各プロセスのローカル変数である。

すべてのプロセスを1回ずつ実行し、すべてのプロセスの処理が終了したときに y=W となる実行手順があるかどうかを答える。
そのような実行手順がある場合は、その手順も具体的に答える。
ここで、 N, ni, W は与えられる整数で、1≦N≦100, 1≦ni≦1000, -109≦W≦109 をみたす。
※ 擬似コードの2行目と3行目の間に別のプロセスが割り込んでもいい


[ 解答 ]
言語は C++。include文とusing文は省略。

A.
int main()
{
static bool era[3000];
for(int i=2;i<3000;i++) era[i]=true;
for(int i=2;i<100;i++){
if(!era[i]) continue;
for(int j=i+i;j<3000;j+=i) era[j]=false;
}

vector<int> p;
for(int i=0;i<3000;i++) if(era[i]) p.push_back(i);

int n,cnt=0; cin>>n;
for(int i=1;i<=n;i++){
int tmp=0;
for(int j=0;j<p.size();j++){
if(p[j]>i) break;
if(i%p[j]==0) tmp++;
}
if(tmp==2) cnt++;
}
cout<<cnt;

return 0;
}

エラトステネスのふるいにかけて3000までの素数をリストアップしたあとは問題文どおりやるだけ。AC。

B.
int main()
{
static char s[1000001];
scanf("%s",s);
int len=strlen(s);

int dep=0,over=0;
for(int i=0;i<len;i++){
if(s[i]=='(') dep++;
else{
if(dep>0) dep--;
else over++;
}
}
printf("%d",len-dep-over);

return 0;
}

過剰な ( の数が変数depに、過剰な ) の数が変数overに入る。
入力文字列長から余分な括弧の数を差し引いたものが答え。
本当にこれでいいかは証明してないけど、テスト通ったから多分合ってる。AC。

C.
typedef pair<int,int> pii;

vector< vector<int> > flr;

void impossible(void){ cout<<"IMPOSSIBLE"; exit(0); }

void fill_evenxeven(int n,int m,int a,int b,int c)
{
int id=100;
for(int y=0;y<n;y+=2){
for(int x=0;x<m;x+=2){
if(c>0){
flr[y][x]=flr[y][x+1]=flr[y+1][x]=flr[y+1][x+1]=id;
id++;
c--;
}
else if(c==0 && a>0){
flr[y][x]=flr[y][x+1]=id;
id++;
a--;
flr[y+1][x]=flr[y+1][x+1]=id;
id++;
a--;
}
else{
flr[y][x]=flr[y+1][x]=id;
id++;
b--;
flr[y][x+1]=flr[y+1][x+1]=id;
id++;
b--;
}
}
}
}

char determ_alpha(vector<pii> p)
{
char ch='a';
while(1){
bool flag=true;
for(int i=0;i<p.size();i++)
if(ch==flr[p[i].first][p[i].second]) flag=false;
if(!flag) ch='a'+(ch+1)%24;
else return ch;
}
}

int main()
{
int n,m,a,b,c,c_net; cin>>n>>m>>a>>b>>c;
flr=vector< vector<int> >(n,vector<int>(m));

if((n*m)%2==1 || n*m>2*a+2*b+4*c) impossible();

if(n%2==0 && m%2==0){ // n:even, m:even
c_net=a/2+b/2+c;
if(4*c_net<n*m) impossible();
else{
a=a-a%2; b=b-b%2;
fill_evenxeven(n,m,a,b,c);
}
}
else if(n%2==0 && m%2==1){ // n:even, m:odd
if(2*b<n) impossible();

c_net=a/2+(b-n/2)/2+c;
if(4*c_net<n*(m-1)) impossible();
else{
for(int y=0;y<n;y+=2){
flr[y][m-1]=flr[y+1][m-1]='y'+((y/2)%2);
b--;
}
a=a-a%2; b=b-b%2;
fill_evenxeven(n,m-1,a,b,c);
}
}
else{ // n:odd, m:even
if(2*a<m) impossible();

c_net=(a-m/2)/2+b/2+c;
if(4*c_net<(n-1)*m) impossible();
else{
for(int x=0;x<m;x+=2){
flr[n-1][x]=flr[n-1][x+1]='y'+((x/2)%2);
a--;
}
a=a-a%2; b=b-b%2;
fill_evenxeven(n-1,m,a,b,c);
}
}

// translate flr[][] to lower case
for(int y=0;y<n-n%2;y+=2){
for(int x=0;x<m-m%2;x+=2){
vector<pii> pos;
if(flr[y][x]==flr[y ][x+1] // type 2x2
&& flr[y][x]==flr[y+1][x ]
&& flr[y][x]==flr[y+1][x+1]){
if(y>0){
pos.push_back(make_pair(y-1,x));
pos.push_back(make_pair(y-1,x+1));
}
if(x>0){
pos.push_back(make_pair(y,x-1));
pos.push_back(make_pair(y+1,x-1));
}
flr[y][x]=flr[y][x+1]=flr[y+1][x]=flr[y+1][x+1]=determ_alpha(pos);
}
else if(flr[y][x]==flr[y ][x+1] // type 1x2
&& flr[y][x]!=flr[y+1][x ]
&& flr[y+1][x]==flr[y+1][x+1]){
if(y>0){
pos.push_back(make_pair(y-1,x));
pos.push_back(make_pair(y-1,x+1));
}
if(x>0){
pos.push_back(make_pair(y,x-1));
}
flr[y][x]=flr[y][x+1]=determ_alpha(pos);

pos.push_back(make_pair(y,x));
pos.push_back(make_pair(y,x+1));
if(x>0){
pos.push_back(make_pair(y+1,x-1));
}
flr[y+1][x]=flr[y+1][x+1]=determ_alpha(pos);
}
else{ // type 2x1
if(y>0){
pos.push_back(make_pair(y-1,x));
}
if(x>0){
pos.push_back(make_pair(y,x-1));
pos.push_back(make_pair(y+1,x-1));
}
flr[y][x]=flr[y+1][x]=determ_alpha(pos);

if(y>0){
pos.push_back(make_pair(y-1,x+1));
}
pos.push_back(make_pair(y,x));
pos.push_back(make_pair(y+1,x));
flr[y][x+1]=flr[y+1][x+1]=determ_alpha(pos);
}
}
}

for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<(char)flr[i][j];
}
cout<<endl;
}
}

150行くらい。このコードはあとで整形して短くしたバージョンで、競技中に書いたものはさらに冗長で長い。この長さのコードを書いてバグがほとんどなかったことは奇跡だ。凡ミスで2WAした後 AC。

方針としては、n, m の偶奇で場合分けする。
  • n : 奇数, m : 奇数
    部屋の面積が奇数になるので、どうやっても敷き詰められない。impossible.

  • n : 偶数, m : 偶数
    type3のタイルだけで敷き詰められる。
    2枚のtype1は1枚のtype3と等価、2枚のtype2は1枚のtype3と等価だから、すべてtype3に換算してから敷き詰めるのに十分な枚数があるかどうか調べる。

  • n : 偶数, m : 奇数
    右端の1列にtype2を敷き詰めて、あとは↑の場合と同じ。

  • n : 奇数, m : 偶数
    下端の1行にtype1を敷き詰めて、あとは↑↑の場合と同じ。

ソースコードの簡単な説明。
  • 関数 fill_evenxeven
    n×m (n,mは偶数) の部屋を敷き詰める。異なるタイルには異なるidが割り振られる。

  • 関数 determ_alpha
    引数の座標にあるタイルのどれともと違うアルファベットを求める。

  • 変数 c_net
    正味のtype3のタイルの枚数 (type1,type2の分も換算したもの)

  • 右端or下端に敷き詰めるタイル
    これらにはアルファベット y or z を割り当てた。他のタイルには a~x を割り当てた。

  • コメント translate flr[][] to lower case 以降
    idからアルファベットに変換する部分。
    idを経由したのはコーディングを簡単にしたかったからだけど、そんなことしないほうが短く書けたかも。
    左上からシーケンシャルにスキャンしているので、重複しないアルファベットを求めるのは今見ている場所の左と上方向だけを調べればいい。


D. (時間外)
int main()
{
int n,m,k; cin>>n>>m>>k;

if(m>n+k){ cout<<0; return 0; }

double r=1.0;
for(int i=0;i<=k;i++) r*=(m-i)/(n+i+1.0);

cout<<(1-r);

return 0;
}

うーん、解けない。
n×mの表を作る方法だと O(nm) の計算量だから、最悪 O(1010) になって間に合わない。
もう少し考えてみよう。
cf. Catalan数

[ 2010/08/18 追記 ]
解けた。
長くなったので解説は別記事に分けることにしました。
いつの間にか adamax氏作成の tutorial も出てましたが、今回はそれを見ずに解けました。
プログラム中では、
1-\frac{_mC_{k+1}}{_{n+k+1}C_{k+1}}
を変形して計算しやすくした
1-\frac{m\ (m-1)\cdots(m-k)}{(n+k+1)\ (n+k)\cdots(n+1)}
を使っています。
m≦k のときに常に 1 になるというケースは、上式に含まれているので特別場合分けしなくても通りました。

E. (時間外)
int main()
{
int N,w,n[128]; cin>>N>>w;
for(int i=0;i<N;i++) cin>>n[i];

if(w<=0 || accumulate(n,n+N,0)<w){ cout<<"No"; return 0; }

// N==1
if(N==1){
if(n[0]==w){
cout<<"Yes\n";
for(int i=0;i<n[0]-1;i++) cout<<"1 1 ";
cout<<"1 1";
return 0;
}
else{ cout<<"No"; return 0; }
}

// N>=2 and w==1
if(w==1){
for(int i=0;i<N;i++){
if(n[i]==1){
cout<<"Yes\n"<<i+1<<" ";
for(int j=0;j<N;j++){
if(j==i) continue;
for(int k=0;k<n[j];k++) cout<<j+1<<" "<<j+1<<" ";
}
cout<<i+1;
return 0;
}
}
cout<<"No";
return 0;
}

// N>=2 and w>=2
cout<<"Yes\n";
n[0]--; n[1]--;
int cntrib[128]={0};
for(int i=0,cnt=0;i<N;i++){
for(int j=0;j<n[i];j++){
if(cnt==w-2) break;
cntrib[i]++;
cnt++;
}
}

cout<<"1 ";
for(int i=1;i<N;i++) for(int j=cntrib[i];j<n[i];j++) cout<<i+1<<" "<<i+1<<" ";
cout<<"1 ";
for(int i=0;i<N;i++) for(int j=0;j<cntrib[i];j++) cout<<i+1<<" "<<i+1<<" ";
cout<<"2 ";
for(int i=0;i<n[0]-cntrib[0];i++) cout<<"1 1 ";
cout<<"2";

return 0;
}

[ 2010/08/30 追記 ]
adamax氏のすばらしいtutorialを参考にして組んでみました。
方針はtutorialにあるとおりなので、概略だけ書くと、
・N = 1
・N ≧ 2 かつ w = 1
・N ≧ 2 かつ w ≧ 2
の3パターンで場合分け。
前2つはすぐに分かるが、3つめの場合が難しい。
プロセス 1 とプロセス 2 を上手く使うのがポイント。
コード中の cntrib は、実質、y のカウントに寄与する分で、カウントに寄与しない分はプロセス1or2の間に挟んでうまく空回りさせる。
方針が立ってからでもバグが大量発生して、Accepted をもらうまでに結構時間がかかりました。まだまだ実装力が足りないな...


結局、時間内には A, B, C の3問解けて、
Ratingは15331674
まさかの黄色コーダー!! TopCoderではなのに...
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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