スポンサーサイト

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

Codeforces Beta Round #16 (Div.2)

競技プログラミングってマイナーかと思ってたんですが、けっこうやってる人いるんですね。

今回の記事は、06/03にcodeforcesで行われた、Codeforces Beta Round #16 の参加記録です。

Tags : プログラミング Codeforces

Codeforcesの競技はこの回が初参加でした。

基本的なルールは以下
プログラミングの問題が5問出題される。(問題文はすべて英語)
・競技時間は5問で120min
・制限時間、使用可能メモリ量は問題ごとに指定される。
・テストデータはstdinから与えられて、解答はstdoutに出力する。
・C, C++, Java, C#, Python, Ruby, Delphi, Pascal, Haskell, PHP, F# と、かなり多種類の言語が使える。


[ 問題 ]
#16 の問題セット(Div2)はこんな感じでした。

A. Flag
2次元の数値として与えられる"旗"が、ストライプ模様かどうかを判定する。

B. Burglar and Matches
マッチをできるだけたくさん袋に詰めろ!!
袋の容量、コンテナの数、各コンテナに入っているマッチ箱とマッチの数、が与えられる。
詰められるマッチの最大数を求める。

C. Monitor
縦,横の長さが整数であるモニタの端をカットすることで縦横比を変更したい。
面積最大になるようなカット位置を求める。

D. Logging
システムのログデータから日付情報が消えてしまった!!
ログデータに残っている時刻データから、そのログが何日分あったかを求める。
(ただし、各ログの記録間隔は1日未満であったとする。)

E. Fish
魚でサバイバルゲーム。
魚同士が出遭えば、ある確率(与えられる)でどちらかが食べられる。
最後の1匹になった時に、各魚が生き残っている確率を求める。


[ 解答 ]
言語は C++。また、include文とusing文は省略しています。

A.
int main()
{
int row,col;
char str[110][110];

scanf("%d %d",&row,&col);
for(int i=0;i<row;i++) scanf("%s",str[i]);

char mark[110];
for(int i=0;i<row;i++) mark[i]=str[i][0];
for(int i=1;i<row;i++){
if(mark[i-1]==mark[i]){
printf("NO");
return 0;
}
}

for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(str[i][j]!=mark[i]){
printf("NO");
return 0;
}
}
}

printf("YES");

return 0;
}


B.
int main()
{
int m,n;
int a[25],b[25];

scanf("%d %d",&n,&m);
for(int i=0;i<m;i++) scanf("%d %d",&a[i],&b[i]);

for(int i=0;i<m;i++){
for(int j=i+1;j<m;j++){
if(b[i]<b[j]){
swap(a[i],a[j]);
swap(b[i],b[j]);
}
}
}

long val=0;
int rest=n;
for(int i=0;i<m;i++){
if(rest>=a[i]){
rest-=a[i];
val+=a[i]*b[i];
}
else{
val+=rest*b[i];
break;
}
}

printf("%ld",val);

return 0;
}


C.
int euclid(int a,int b)
{
int c;
while(b!=0){c=a%b;a=b;b=c;}
return a;
}

int main()
{
int a,b,x,y;
scanf("%d%d%d%d",&a,&b,&x,&y);

int gcd=euclid(x,y);
x/=gcd; y/=gcd;

int c=min(a/x,b/y);
printf("%d %d",c*x,c*y);

return 0;
}


D. (競技終了後に書いた)
int main()
{
int n,time[105];

cin>>n; cin.ignore();

for(int i=0;i<n;i++){
int h,m;
char ap,msg[64];
fgets(msg,63,stdin);

h=(msg[1]-'0')*10+(msg[2]-'0');
m=(msg[4]-'0')*10+(msg[5]-'0');
ap=msg[7];
if(h==12) h=0;
if(ap=='p') h+=12;
time[i]=60*h+m;
}

int day=1;
for(int i=1;i<n;i++){
if(time[i-1]>time[i]) day++;
}

for(int i=1,cnt=0;i<n;i++){
if(time[i-1]==time[i]) cnt++;
else cnt=1;
if(cnt>10){ day++; cnt=1; }
}

printf("%d",day);

return 0;
}

データ入力部はここを参考にさせてもらいました。

E. (競技終了後に書いた)
double live[1<<18];

int main()
{
int n;
double a[20][20];

scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%lf",&a[i][j]);
}
}

double coef[20];
for(int i=2;i<=n;i++) coef[i]=2.0/((double)i*(i-1));

live[(1<<n)-1]=1.0; // initial state : all fishes live
for(int st=0;st<(1<<n)-1;st++) live[st]=0.0;

for(int st=(1<<n)-1;st>0;st--){
if(live[st]==0.0) continue; // pruning
for(int i=0;i<n;i++){
if(!(st&(1<<i))) continue; // i-th fish is already dead
for(int j=i+1;j<n;j++){
if(!(st&(1<<j))) continue; // j-th fish is already dead
int c=0; // number of fish
for(int k=0;k<n;k++) if(st&(1<<k)) c++;
live[st&(~(1<<j))]+=live[st]*coef[c]*a[i][j];
live[st&(~(1<<i))]+=live[st]*coef[c]*a[j][i];
}
}
}

for(int i=0;i<n-1;i++) printf("%lf ",live[1<<i]);
printf("%lf",live[1<<(n-1)]);

return 0;
}

自力では解法が思いつかなかったので、DIさんの記事を参考にして組みました。
18匹の魚の生死情報(生なら1,死なら0)を整数の各bitに対応させることで、全魚の状態を1つの整数値で表しています。
live[state] には、状態stateに到達する確率が格納されます。たとえば、live[2n-1] は全てのbitが1の状態(初期状態)なので、その値は常に1になります。
coef[num] は、1/(numC2) のことで、numコの中から2コを選ぶ組み合わせの数の逆数です。
pruning とコメントしてある行は単に無駄な計算を省いているだけで、書かなくても時間内に計算できます。


結果、時間内にはA,B,Cの3問が解けて、ratingは1568でした。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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