スポンサーサイト

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

Codeforces Beta Round #18 (Div.2)

JST 06/17 00:00~02:00 にweb上で行われたプログラミング競技、Codeforces Beta Round 第18回の参加記録です。

目標は4問正解!! と意気込んで臨んだのですが...

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

Tags : プログラミング Codeforces

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

A. Triangle
2次元平面上の3点の座標(整数値)が与えられるので、3点を結んでできる三角形の性質を答える。
・直角三角形なら、"RIGHT"を出力する。
・ほぼ直角三角形なら、"ALMOST"を出力する。
・どちらでもなければ、"NEITHER"を出力する。
ここで、"ほぼ直角三角形"を、【3頂点のうち、1つを距離1だけ移動すると直角三角形になる三角形】と定義する。ただし、移動後の点も整数座標であるとする。
また、与えられる座標値からは、必ず三角形を作ることができるものとする。(面積0になるようなデータは来ない)

B. Platforms
x軸上にnコの踏み台(長さL)がある。
それぞれの踏み台は、[0,L],[m,m+L],…,[(n-1)m,(n-1)m+L] という位置に置かれている。( m>L )
Bobバッタは、位置0からスタートして、x軸正の方向に、距離dずつジャンプしていく。
Bobが落ちる(踏み台に乗れない)位置を求める。
踏み台の端( 0, L, m, m+L, …, (n-1)m+L )ではBobは落ちないとする。

C. Stripe
nコの整数が与えられる。
この数列をあるところで"区切る"とき、左側にある数の和 と 右側にある数の和 が等しくなるような区切り方は何通りあるか?

D. Seller Bob
BobはUSBメモリを売りたい。Bobは、n 日間のイベント中で、各日ごとに
(a) 容量 2x MBのUSBメモリを手に入れる。
(b) 容量 2x MBのUSBメモリを(持っていれば)客に売り、2x 円を手に入れる。
のどちらか一方を行う。
BobはUSBメモリを一度に1つしか持てず、持ちきれなくなった場合はどちらか好きなほうを残すことにする。
また、容量 2x MBのUSBメモリをほしがる客は、各 x について高々1人しかいないとする。
各日に(a)(b)どちらを行ったかという情報が与えられるので、Bobが得られる最大利益を求める。

E. Flag 2
#16 A. Flag の続編

2次元の文字データとして与えられる"旗"をチェック模様に塗り替えたい。
塗り替えるマスの最小数と、塗り替えた後の"旗"を求める。
ここで、"旗"がチェック模様であるとは
・どの行にもちょうど2色が使われている。
・すべてのマスについて、マスの上下左右にはそのマスと同じ色はない。
を満たすことをいう。
また、塗り替え後の"旗"の模様が一意でない場合はどれを出力してもよい。


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

A.
int main()
{
vector<int> x(3),y(3);
for(int i=0;i<3;i++) cin>>x[i]>>y[i];

vector<int> d(3);
for(int i=0;i<3;i++)
d[i]=(x[(i+1)%3]-x[i%3])*(x[(i+1)%3]-x[i%3])
+(y[(i+1)%3]-y[i%3])*(y[(i+1)%3]-y[i%3]);
sort(d.begin(),d.end());
if(d[0]+d[1]==d[2]){
cout<<"RIGHT";
return 0;
}

int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
for(int i=0;i<3;i++){
for(int j=0;j<4;j++){
vector<int> xx=x,yy=y;
xx[i]+=dx[j]; yy[i]+=dy[j];
for(int i=0;i<3;i++)
d[i]=(xx[(i+1)%3]-xx[i%3])*(xx[(i+1)%3]-xx[i%3])
+(yy[(i+1)%3]-yy[i%3])*(yy[(i+1)%3]-yy[i%3]);
sort(d.begin(),d.end());
if(d[0]==0) continue; // attention
if(d[0]+d[1]==d[2]){
cout<<"ALMOST";
return 0;
}
}
}

cout<<"NEITHER";
return 0;
}

素直に、3頂点すべてについて、1つずらしたときに直角になるかを調べるだけです。
書くだけなので難易度は低いですが、実装が若干めんどうで時間がかかりました。
attentionとコメントした行の処理(点の移動後に三角形がつぶれる場合)を忘れていたので、1WAの後、Accepted.

B.
int main()
{
int n,d,m,l; cin>>n>>d>>m>>l;
int inc=d%m;
long long len=(long long)(n-1)*m+l;

for(int i=0,j=0;;++i){
if(l<j){
cout<<(long long)i*d; break;
}
j=(j+inc)%m;
if(j==0){
cout<<(len-(len%d)+d); break;
}
}

return 0;
}

これは良問。
試合中に書いたときはもっと煩雑なコードだったんですが、いろいろ削っているうちにかなり短くなりました。

1回のジャンプ後のBobの位置が台の左端からずれる長さは inc=d%m と計算できます。
このズレが台の右端(L)を越えるとBobは台から落ちるので、そのときの位置が答えです。
このズレがいつまでたっても右端を越えないとき、つまり、何回目かで ズレ==0 となり、ズレが循環する場合には、バッタは台の隙間で落ちることはなく、最後の台を越えたところ len-(len%d)+d で落ちます。

3WA, 5TLE, 1PEの後に何とかAccepted.をもらいました。ratingが伸びなかったのは主にこの問でのPenaltyが原因です。

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

vector<int> seq(n);
for(int i=0;i<n;i++) cin>>seq[i];
int sum=accumulate(seq.begin(),seq.end(),0);

int cnt=0;
for(int i=0,psum=0;i<n-1;i++){
psum+=seq[i];
if(psum==sum-psum) cnt++;
}

cout<<cnt;
return 0;
}

実は、AよりもBよりも簡単な問題。
まず、総和sumを計算しておいて、左端から足していったときの部分和 psum が sum の半分になる時をカウントするだけです。

D. (時間外)
char pow2[2001][605];

list< pair<char,int> > ev;
stack<int> valid_x;

void determ_x(int x,list< pair<char,int> >::iterator bgn,list< pair<char,int> >::iterator end)
{
if(x<0) return;

list< pair<char,int> >::iterator it;
list< pair<char,int> >::iterator pos=end;
for(it=bgn;it!=end;it++){
if(*it==make_pair('w',x)) pos=it;
if(*it==make_pair('s',x) && pos!=end){
valid_x.push(x);
determ_x(x-1,bgn,pos);
determ_x(x-1,it,end);
return;
}
}

determ_x(x-1,bgn,end);
return;
}


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

for(int i=0;i<n;i++){
int x;
char str[32];
scanf("%s %d",str,&x);
ev.push_back(make_pair(str[0],x));
}

determ_x(2000,ev.begin(),ev.end());

for(int i=0;i<=2000;i++) memset(pow2[i],0,605);
pow2[0][0]=1;
for(int i=1;i<=2000;i++){
for(int j=0;j<604;j++){
pow2[i][j]+=(pow2[i-1][j]<<1);
if(pow2[i][j]>=10){
pow2[i][j]-=10; pow2[i][j+1]++;
}
}
}

// view 2^n
/*for(int n=0;n<=2000;n++){
for(int j=604;j>=0;j--) putchar(pow2[n][j]+'0');
putchar('\n');
}*/


char ans[605];
memset(ans,0,605);
for(int i=0;valid_x.size()!=0;i++){
int dgt=valid_x.top();
valid_x.pop();
for(int j=0;j<604;j++){
ans[j]+=pow2[dgt][j];
if(ans[j]>=10){
ans[j]-=10;
ans[j+1]++;
}
}
}

int p;
for(p=603;p>0;p--) if(ans[p]!=0) break;
for(int i=0;i<=p;i++) ans[i]+='0';
ans[p+1]='\0';
for(int i=0;i<(p+1)/2;i++) swap(ans[i],ans[p-i]);

cout<<ans;

return 0;
}

usbメモリを売ることができるxのうち、最大のもの xmax を優先的に選んでいくとうまくいきます。
というのも、すべての自然数 x について、
2x > 2x-1 + 2x-2 + … + 20
がなりたつので、xmax を選ぶ方が絶対に得になるからです。

関数 determ_x() では、この考えに基づいて売る x を求めています。結果はスタック valid_x に格納されます。
再起関数で実装しましたが、もっと高速な方法もあると思います。
( win x が i日目、sell x が j日目にあったとすると、あとの探索範囲は[0,i-1]と[j+1,n]です。)

main()の後半は多倍長演算用の処理です。といっても、2の累乗と加算だけですが。
ちなみに605という数字は 22000 が603桁の数であることから来ています。

E. (時間外)
int row,col;
char flag[500][500];
char alpha[]="abcdefghijklmnopqrstuvwxyz";
int memo[26][26][500];

int coloring(char a,char b,int r)
{
int cnt=0;
for(int i=0;i<col;i++){
if(i%2==0 && flag[r][i]!=a) cnt++;
else if(i%2==1 && flag[r][i]!=b) cnt++;
}
return cnt;
}


int main()
{
cin>>row>>col;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++) cin>>flag[i][j];
}

// initial conditions
for(int i=0;i<26;i++){
for(int j=0;j<26;j++){
if(i==j) memo[i][j][0]=INT_MAX;
else memo[i][j][0]=coloring(alpha[i],alpha[j],0);
}
}

// main routine (dp)
for(int k=1;k<row;k++){
for(int i=0;i<26;i++){ // color 0
for(int j=0;j<26;j++){ // color 1
if(i==j){
memo[i][j][k]=INT_MAX;
continue;
}
int tmp=INT_MAX;
for(int m=0;m<26;m++){ // color 0
for(int n=0;n<26;n++){ // color 1
if(i==m || j==n) continue;
tmp=min(tmp,memo[m][n][k-1]);
}
}
memo[i][j][k]=tmp+coloring(alpha[i],alpha[j],k);
}
}
}

char anscolor[500][2];
int num=INT_MAX;
for(int i=0;i<26;i++){ // color 0
for(int j=0;j<26;j++){ // color 1
if(num<=memo[i][j][row-1]) continue;
num=memo[i][j][row-1];
anscolor[row-1][0]=alpha[i];
anscolor[row-1][1]=alpha[j];
}
}
for(int k=row-2;k>=0;k--){
int tmp=INT_MAX;
for(int i=0;i<26;i++){ // color 0
for(int j=0;j<26;j++){ // color 1
if(alpha[i]==anscolor[k+1][0]
|| alpha[j]==anscolor[k+1][1]) continue;

if(tmp<=memo[i][j][k]) continue;
tmp=memo[i][j][k];
anscolor[k][0]=alpha[i];
anscolor[k][1]=alpha[j];
}
}
}

cout<<num<<endl;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
putchar(anscolor[i][j%2]);
}
putchar('\n');
}

return 0;
}

旗の各行の色は2色あれば確定できる(縞々になるから)ことに注意して、DP (Dynamic Programming) で解きます。
関数 coloring(a,b,r) は、第r行を色a,bで塗るときの塗り替えるマスの数を計算します。

memo[i][j][0]には、第0行を色iと色jで塗るときの塗り替えるマスの数が格納されます。
memo[i][j][0] = coloring(i, j, 0)
memo[i][j][1]には、第0行を何かの色で塗り、第1行を色iと色jで塗るときの塗り替えるマスの最小数が格納されます。これは、
memo[i][j][1] = min( memo[m][n][0], i≠m, j≠n ) + coloring(i, j, 1)
と計算することができます。
このように順に計算していって、最後に得られる
min( memo[i][j][row-1] )
が求めたかった塗り替えの最小数になります。

プログラムの後半(anscolorの宣言以降)は、先の処理を逆に辿っていって、実際にマス数が最小になるときの色を求めなおしています。うまくすればこの処理は先の処理にまとめられるかもしれません。


今回はA.B.C.の3問が解けて、ratingは14821504と、ギリギリ1500点台に届きました。次回からはまたdiv1に戻ります♪
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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