スポンサーサイト

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

Codeforces Beta Round #36

10/19 19:00~21:00 に行われた Codeforces 第36回の記録です。

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

[ 結果 ]
A. 00:19:14 Wrong answer on test 6 [final tests]
B. 00:52:49 Accepted [final tests]
D. 01:59:24 Wrong answer on pretest 2 [pretests]
Standing 230/613
Rating 15081454

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

A. Extra-terrestrial Intelligence
0 と 1 だけからなる長さnの数列が与えられる。
数列中に 1 が等間隔に含まれているかどうかを判定する。
(数列には少なくとも3つの 1 が含まれていることが保証されている。)

B. Fractal
サイズ n×n の模様に対して、k 回のフラクタル的処理をほどこす。処理後の模様を出力する。
処理の内容は文章で説明しにくいので、原文を見てください。
たとえば、n=3, k=3 で、始めの模様が
..*
...
...

であれば、
..*..****..*..*************
......***......************
......***......************
..*..*..*..*..*..**********
..................*********
..................*********
..*..*..*..*..*..**********
..................*********
..................*********
..*..****..*..****..*..****
......***......***......***
......***......***......***
..*..*..*..*..*..*..*..*..*
...........................
...........................
..*..*..*..*..*..*..*..*..*
...........................
...........................
..*..****..*..****..*..****
......***......***......***
......***......***......***
..*..*..*..*..*..*..*..*..*
...........................
...........................
..*..*..*..*..*..*..*..*..*
...........................
...........................

という模様を出力すればいい。

C. Bowls
「長いほうの辺がない等脚台形」をひっくり返した形状のボウル
\_/ (←こんな形)
を n コ重ねるとき、重ねたボウルの高さの合計を求める。
( 1 ≦ n ≦ 3000 )

各ボウルの上底,下底,高さ(いずれも整数値)が与えられる。

なお、すべてのボウルは中心軸が揃うように重ねるものとする。

D. New Game with a Chess Piece
m×n のチェス盤で2人のプレーヤーがゲームをする。
ゲーム開始時には、盤の左上のマスに駒が1つだけある。
ゲームはターン制で行われる。
各プレーヤーは自分のターンに
(1) 駒を1マス下に動かす
(2) 駒を1マス右に動かす
(3) 駒をkマス右下に動かす (Manhattan距離でいうと 2k マス動く)
のいずれかの操作をする。
先に駒を動かせなくなったプレーヤーの負け。

m, n, k が与えられたとき、先手必勝, 後手必勝のどちらであるかを答える。
( 1 ≦ m, n, k ≦ 109 )

E. Two paths
まだ読めてない。

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

A. (時間外)
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int n; cin>>n;
bool ok=true;
for(int i=0,cnt1=0,pos,len;i<n;i++){
char c; cin>>c;
if(c=='1'){
if(cnt1==1) len=i-pos;
if(cnt1>=2 && len!=i-pos) ok=false;
pos=i;
cnt1++;
}
}
cout<<(ok?"YES":"NO")<<endl;

return 0;
}

問題文を「連続する1のかたまり間の距離が一定」と勘違い。
(つまり、11011011 のようなケースも許容していた。)
原文の successive って単語に惑わされた。最近、読解ミスばっかりだ。
なんでみんな正しく読み取れるんだろう? (→私の英語力が低いだけ)

B.
int n,k;
char fig[4][3],fra[243][244];

void draw(int x,int y,int dep)
{
if(dep==k) return;

int mesh=(int)pow(1.0*n,k-dep-1);
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(fig[i][j]=='*'){
for(int yy=0;yy<mesh;yy++)for(int xx=0;xx<mesh;xx++){
fra[y+i*mesh+yy][x+j*mesh+xx]='*';
}
}
else draw(x+j*mesh,y+i*mesh,dep+1);
}
}

int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

cin>>n>>k;
for(int i=0;i<n;i++) cin>>fig[i];

int npowk=(int)pow(1.0*n,k);
for(int i=0;i<npowk;i++)for(int j=0;j<npowk;j++) fra[i][j]='.';

draw(0,0,0);

for(int i=0;i<npowk;i++) cout<<fra[i]<<endl;

return 0;
}

基本的な再起呼び出しの問題。
添え字が複雑になってデバッグに時間がかかったけど、他は特に問題なく書けた。

C. (時間外)
int h[3000],r[3000],R[3000];

double calcHeight(int a,int b) // Bowl b is on Bowl a
{
if(R[a]<r[b]) return h[a];

double h1,h2,h3,h4;
h1=0; // bottom
h2=1.0*(R[b]-r[a])/(R[a]-r[a])*h[a]-h[b]; // top corner
h3=h[a]-1.0*(R[a]-r[b])/(R[b]-r[b])*h[b]; // side
h4=1.0*(r[b]-r[a])/(R[a]-r[a])*h[a]; // bottom corner

if (r[a]>=r[b] && R[a]>=R[b]) return max(h1,h2);
else if(r[a]>=r[b] && R[a]< R[b]) return max(h1,h3);
else if(r[a]< r[b] && R[a]>=R[b]) return max(h2,h4);
else return max(h3,h4);
}

int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int n; scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d%d%d",h+i,r+i,R+i);

double htop=h[0];
static double hacc[3000];
for(int i=1;i<n;i++){
for(int j=0;j<i;j++)
hacc[i]=max(hacc[i],hacc[j]+calcHeight(j,i));
htop=max(htop,hacc[i]+h[i]);
}

printf("%f\n",htop);

return 0;
}

問題文 右の図みたいなケースがあるから、1つ前のボウルだけを考えてるとうまくいかない。
どうするんだろう? 線分の交差判定とか使うんだろうか。

[ 2010/10/20 追記 ]

もう1度ゆっくり考えてみたら解けた。
ブログ記事としてまとめることがいい思考の整理になってるようだ。

追記前に書いたことから、ボウルを重ねるときは、それより下にあるすべてのボウルを考慮する必要があることに注意。

後述するように、2つのボウルの距離(重ねたときの底面間の距離)の計算は定数時間でできる。
すべてのボウルについて、自分より下のすべてのボウルとの距離を求めて、最大のものを採用していけばいい。
時間計算量 O(n2). n≦3000 だから十分間に合う。

・ 2ボウル間の距離
ボウル a の底面の半径を ra
ボウル a の上面の半径を Ra (実際には面はないが.)
ボウル a の高さを ha
と書くことにすると、
ボウル a にボウル b を重ねるとき、その重ね方は、次の5通りが考えられる。
  1. ボウル b の底面がボウル a の底面に接する

  2. ボウル b の上面(の縁)がボウル a の側面に接する

  3. ボウル b の側面がボウル a の上面(の縁)に接する

  4. ボウル b の底面(の縁)がボウル a の側面に接する

  5. ボウル a の上面(の縁)にボウル b が乗る

5番目のケースは例外っぽいので別途処理することにして、あとの4ケースについては、
raとrb,RaとRbの大小関係によって、起こりうるときと起こりえないときがある。
1つずつ考えると
  • ra<rb かつ Ra<Rb のとき
    ケース 3, 4 が起こりうる

  • ra<rb かつ Ra>Rb のとき
    ケース 2, 4 が起こりうる

  • ra>rb かつ Ra<Rb のとき
    ケース 1, 3 が起こりうる

  • ra>rb かつ Ra>Rb のとき
    ケース 1, 2 が起こりうる

図に描いてみると一目瞭然。
それぞれのケースについて、三角形の相似(なつかしい!!)を使ってがんばって計算すると距離が求められる。

D. (時間外)
char judge(int m,int n,int k)
{
if(k==1) return (m%2==1 && n%2==1)?'-':'+';
else{
int p=min(m,n);
if(p%(k+1)==0) return '+';
return ((m+n)%2==(p/(k+1))%2)?'-':'+';
}
}

int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int t,k,n,m; cin>>t>>k;
while(t--){ cin>>n>>m; cout<<judge(m,n,k)<<endl; }

return 0;
}

Nim Game の一種。
2つの石の組があり、それぞれの組は mコ, nコ の石からなる。
もう少し考えてみる。

[ 2010/10/27 追記 ]

小さいケースについて全探索して列挙してみるとパターンが見えた。
けっこう複雑なパターンだったので、紙とペンだけで見つけるのは無茶だったかもしれない。
こういう問題の場合、とりあえずコンピュータに解かせて規則をみつける戦略のほうがいいんだろうか。

1 ≦ m,n ≦ 20; k = 5 の場合のパターン
横軸に m, 縦軸に n をとっている。
@ : 先手必勝な (m,n)
. : 後手必勝な (m,n)
. @ . @ . @ . @ . @ . @ . @ . @ . @ . @
@ . @ . @ . @ . @ . @ . @ . @ . @ . @ .
. @ . @ . @ . @ . @ . @ . @ . @ . @ . @
@ . @ . @ . @ . @ . @ . @ . @ . @ . @ .
. @ . @ . @ . @ . @ . @ . @ . @ . @ . @
@ . @ . @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @
. @ . @ . @ @ . @ . @ . @ . @ . @ . @ .
@ . @ . @ @ . @ . @ . @ . @ . @ . @ . @
. @ . @ . @ @ . @ . @ . @ . @ . @ . @ .
@ . @ . @ @ . @ . @ . @ . @ . @ . @ . @
. @ . @ . @ @ . @ . @ . @ . @ . @ . @ .
@ . @ . @ @ . @ . @ . @ @ @ @ @ @ @ @ @
. @ . @ . @ @ . @ . @ @ . @ . @ . @ . @
@ . @ . @ @ . @ . @ . @ @ . @ . @ . @ .
. @ . @ . @ @ . @ . @ @ . @ . @ . @ . @
@ . @ . @ @ . @ . @ . @ @ . @ . @ . @ .
. @ . @ . @ @ . @ . @ @ . @ . @ . @ . @
@ . @ . @ @ . @ . @ . @ @ . @ . @ @ @ @
. @ . @ . @ @ . @ . @ @ . @ . @ . @ @ .
@ . @ . @ @ . @ . @ . @ @ . @ . @ @ . @


(m,n) = (k+1,k+1) の点から右方向と下方向に、先手必勝のラインができている。
このラインから右下は、@ と . のパターンが反転している。
(m,n) = (2k+2,2k+2) の点についても同様で、以下繰り返し。

E.


まだ。

解け次第、追記予定です。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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