スポンサーサイト

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

Codeforces Beta Round #96

2011/12/04 00:00~02:00 (JST)
Codeforces で行われた Codeforces Beta Round #96 (Div.1) の参加記録

いつもに比べたらやさしめの問題セットだったような。

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

結果

A. AC (00:15)
B. AC (01:23)
C. AC (00:49)
D. 2WA, AC (01:49)
E. -
Standing : 34/477
Rating : 18782005


問題

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

A. Turing Tape

配列があって、配列の中身を次の手順で処理することによって文字列を印字する機械がある。
与えられた文字列を印字するには配列の値をどのように設定すればいいか?

B. Piet

二次元のグリッド上に色の塗られた長方形が敷き詰められている。
隣接する長方形は必ず異なる色であり、色 0 の部分は障害物である。
このグリッドを ( Piet の ) プログラムとみなし、そのプログラムカウンタを考える。

プログラムカウンタは counter block pointer (BP), direction pointer (DP), block chooser (CP) の 3 つの値からなる。
BP はどの長方形を指しているかを表す。
DP はプログラムカウンタが次に進む方向を表す。上下左右のいずれかを指す。
CP は DP の補助的な役割をもち、左右どちらかを指している。

最初、
BP は (0, 0) を含む長方形を指している。
DP は右を指している。
CP は左を指している。

ルールに従ってプログラムカウンタを進めていくとき、n 回目の処理が終わったときにプログラムカウンタが指している長方形の色を答えよ。

プログラムを読み進めるルールは、
1. 今いる長方形の、DP が指している方向にある辺に注目する
2. 注目した辺について、CP が指している方向の角にあるピクセルに注目する
3. 注目したピクセルについて、DP の方向に 1 マス進んだ先に別の長方形があれば、そこに進む。このとき BP の値以外は変化しない。
4. 3. で進めなかった場合、CP を反転する。CP を右から左に反転するときは同時に DP を 90 度時計回りに動かす。

グリッドサイズは、縦、横ともに 50 以下
1 ≦ n ≦ 5×107

C. Logo Turtle

一次元のタートルグラフィックス。
命令は、
・ F : 1 マス直進
・ T : 逆を向く
のいずれか。

亀は最初、原点にいる。
与えられた命令列をちょうど n 回変更することで、プログラムが終了したときに亀のいる位置と原点との距離を最大化せよ。
ここで、命令列を 1 回変更するとは、
・ 1 つの命令 F を T に変える
・ 1 つの命令 T を F に変える
のいずれかを指す。
同じ命令を複数回変更してもいい。

1 ≦ 命令長 ≦ 100
1 ≦ n ≦ 50

D. Constants in the language of Shakespeare

106 桁以下の 2 進数が与えられる。

0 に
・ 2x を足す
・ 2x を引く
という操作を何回か施して、与えられた 2 進数に一致させる。
( x は 0 以上の整数 )

最小で何回の操作が必要か?
また、その操作の一例も答えよ。

解答

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

A.
int rev(int a){
int b=0;
rep(i,8) if(a&(1<<i)) b|=1<<(7-i);
return b;
}

int main(){
char s[128]; gets(s);
for(int i=0;s[i];i++){
int pre=(i==0?0:rev(s[i-1]));
printf("%d\n",(pre-rev(s[i])+256)%256);
}
return 0;
}

問題文が読めないので和訳もできない・・・
いろんな解釈を試して、むりやり sample input にあわせた。

B.
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

struct Point{ int x,y; };
struct Rect{ int t,l,b,r,color; };

int main(){
int n,h,w; scanf("%d%d ",&h,&n);
char B[50][51];
rep(i,h) gets(B[i]);
w=strlen(B[0]);

int id[50][50];
vector<Rect> R;
rep(i,h) rep(j,w) if(B[i][j]!='0' && B[i][j]!='*') {
char dgt=B[i][j];
int t=i,l=j,b=i,r=j;
B[i][j]='*';
queue<Point> qu; qu.push((Point){j,i});
while(!qu.empty()){
Point p=qu.front(); qu.pop();

t=min(t,p.y);
l=min(l,p.x);
b=max(b,p.y);
r=max(r,p.x);
id[p.y][p.x]=R.size();

rep(k,4){
int x=p.x+dx[k],y=p.y+dy[k];
if(0<=x && x<w && 0<=y && y<h && B[y][x]==dgt){
B[y][x]='*';
qu.push((Point){x,y});
}
}
}

R.push_back((Rect){t,l,b,r,dgt});
}

int bp=0,dp=0,cp=0;
rep(_,n){
int x,y;
if(dp==0 && cp==0) x=R[bp].r+1, y=R[bp].t;
if(dp==0 && cp==1) x=R[bp].r+1, y=R[bp].b;
if(dp==1 && cp==0) x=R[bp].r, y=R[bp].b+1;
if(dp==1 && cp==1) x=R[bp].l, y=R[bp].b+1;
if(dp==2 && cp==0) x=R[bp].l-1, y=R[bp].b;
if(dp==2 && cp==1) x=R[bp].l-1, y=R[bp].t;
if(dp==3 && cp==0) x=R[bp].l, y=R[bp].t-1;
if(dp==3 && cp==1) x=R[bp].r, y=R[bp].t-1;

if(0<=x && x<w && 0<=y && y<h && B[y][x]!='0'){
bp=id[y][x];
}
else{
if(cp==0) cp=1;
else cp=0, dp=(dp+1)%4;
}
}

printf("%c\n",R[bp].color);

return 0;
}

これも問題文を読むのが大変で、そこで詰まった人が多かったみたい。
制限時間が 2 秒で 5×10^7 回のループなので間に合うだろうと信じて、愚直にシミュレーションした。

ちなみに、効率のいい解法は、周期が見つかったら一気に読み飛ばすというもので、今年の ICPC 模擬地区予選 A と同じ。

C.
int main(){
char cmd[101];
int len,n; scanf("%s%d",cmd,&n);
len=strlen(cmd);

int dp[101][51][4];
// dp[i][j][k] := 命令 i まで終わって、うち j 回編集して、状態 k のときの位置
// k = 0 : 右向きでの x 最大, 1 : 右向きでの x 最小
// k = 2 : 左向きでの x 最大, 3 : 左向きでの x 最小
rep(i,len+1) rep(j,n+1) {
dp[i][j][0]=-INF;
dp[i][j][1]=+INF;
dp[i][j][2]=-INF;
dp[i][j][3]=+INF;
}
dp[0][0][0]=dp[0][0][1]=0;
rep(i,len) rep(j1,n+1) {
rep(j2,n-j1+1){ // 命令 i を j2 回編集する
if((cmd[i]=='F')^(j2%2==1)){ // F
dp[i+1][j1+j2][0]=max(dp[i+1][j1+j2][0],dp[i][j1][0]+1);
dp[i+1][j1+j2][1]=min(dp[i+1][j1+j2][1],dp[i][j1][1]+1);
dp[i+1][j1+j2][2]=max(dp[i+1][j1+j2][2],dp[i][j1][2]-1);
dp[i+1][j1+j2][3]=min(dp[i+1][j1+j2][3],dp[i][j1][3]-1);
}
else{ // T
dp[i+1][j1+j2][0]=max(dp[i+1][j1+j2][0],dp[i][j1][2]);
dp[i+1][j1+j2][1]=min(dp[i+1][j1+j2][1],dp[i][j1][3]);
dp[i+1][j1+j2][2]=max(dp[i+1][j1+j2][2],dp[i][j1][0]);
dp[i+1][j1+j2][3]=min(dp[i+1][j1+j2][3],dp[i][j1][1]);
}
}
}

int ans=0;
ans=max(ans,+dp[len][n][0]);
ans=max(ans,-dp[len][n][1]);
ans=max(ans,+dp[len][n][2]);
ans=max(ans,-dp[len][n][3]);
printf("%d\n",ans);

return 0;
}

コメントに書いたように状態をもって DP した。
典型的な DP の問題。

なかなかぐろいコードを書いてしまった。
もっとスマートにかけるはず。

D.
int main(){
char d[1000002]="0"; gets(d+1);
int n=strlen(d);

vector< pair<int,int> > ans;
rep(i,n-3){
if(d[i]=='1' && d[i+1]=='0' && d[i+2]=='1' && d[i+3]=='1'){
d[i+1]='1';
ans.push_back(make_pair(-2,n-i-2));
}
if(d[i]=='1' && d[i+1]=='1' && d[i+2]=='0' && d[i+3]=='1'){
d[i+2]='1';
ans.push_back(make_pair(-2,n-i-3));
}
}

int pre=0;
rep(i,n) if(d[n-i-1]=='0') {
if(i-pre==1){
ans.push_back(make_pair(+2,pre));
}
else if(i-pre>=2){
ans.push_back(make_pair(+2,i));
ans.push_back(make_pair(-2,pre));
}
pre=i+1;
}

printf("%d\n",ans.size());
rep(i,ans.size()) printf("%+d^%d\n",ans[i].first,ans[i].second);

return 0;
}

Greedy 解法。

連続している 1 を一まとまりとみる。

一番左にある 1 のもうひとつ左の場所で 2^x を足して、一番右にある 1 の場所で 2^x を引く。
たとえば
111000
なら
+2^6
-2^3
となる。
これで、連続している 1 のブロック 1 つあたり 2 回の操作ですむ。

ただし、連続している 1 が 1 つしかないときは、単純に足したほうがいいので、例外処理する。
たとえば
111001
なら
+2^6
-2^3
+2^0
となる。

これでほとんど OK だけど、まだ漏れているケースがある。
それは
1110111
のようなケースで、これを上記の方針で処理すると
+2^7
-2^4
+2^3
-2^0
となり 4 回かかる。
しかし、最適解は
+2^7
-2^0
-2^3
である。

ただし、
101

+2^2
+2^0
が最適であって
+2^3
-2^0
-2^1
は間違いであることに注意。

これらの問題を回避するためには、
"1101" or "1101" というパターンがあれば、"1111" に置き換える。
とすればいい。
詳細はソースコード参照。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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