「2311～2320」の編集履歴（バックアップ）一覧はこちら
「2311～2320」(2013/01/23 (水) 09:20:58) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*2311 Dessert Witch
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311
簡単なＣＰＵ同士のオセロ対戦のシミュレーション問題。
簡単すぎて皆やる気が起きなかったのか私のコードがコードサイズ最小でアセプト。
これくらいの問題なら中学生プログラマでも解けそう。
本気でショートコードしたらどれくらい縮むか気になる問題。
#include<stdio.h>
#include<string.h>
char map [9][9];
char next[9][9];
char tMap[9][9];
int dxs[]={ 1, 1, 0,-1,-1,-1, 0, 1};
int dys[]={ 0, 1, 1, 1, 0,-1,-1,-1};
int nx,ny;
void revers(int x,int y,char type,int& revMax){
memcpy(tMap,map,sizeof(map));
int revCount=0;
if(tMap[y][x]!='.')return ;
tMap[y][x]=type;
for(int i=0;i<8;i++){
int dx=dxs[i];
int dy=dys[i];
int tx=x;
int ty=y;
for(int j=0;j<8;j++){
tx+=dx;
ty+=dy;
if(tx<0||tx>7||ty<0||ty>7||map[ty][tx]=='.') break;
if(type==map[ty][tx]){
for(int k=0;k<j;k++){
tx-=dx;
ty-=dy;
revCount++;
tMap[ty][tx]=type;
}
break;
}
}
}
if(revCount>revMax){
revMax=revCount;
memcpy(next,tMap,sizeof(next));
}
}
void saiki(int passCount,char type){
if(passCount>2){
return ;
}else{
memcpy(next,map,sizeof(map));
int revMax=0;
if(type=='o'){
for(int y=0;y<8;y++){
for(int x=0;x<8;x++){
revers(x,y,type,revMax);
}
}
}else{
for(int y=7;y>=0;y--){
for(int x=7;x>=0;x--){
revers(x,y,type,revMax);
}
}
}
memcpy(map,next,sizeof(next));
if(revMax>0){
saiki(0,type=='o'?'x':'o');
}else{
saiki(passCount+1,type=='o'?'x':'o');
}
}
}
int main(){
for(int y=0;y<8;y++)scanf("%s",&map[y]);
saiki(0,'o');
for(int y=0;y<8;y++)printf("%s\n",map[y]);
}
*2317 Class Representative Witch
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317
区切られた数直線上の線分の長さを求める問題。
簡単な問題だけど計算量を落とすのに苦労した問題。
ある点から数えて偶数番目の点を足せばいいのだけど普通に計算したらタイムリミッドが起こるのが目に見えているので奇数番目と偶数番目の地点をメモ化して計算。
最後は、理屈で決めるのがなんだか難しかったので値をprintfしながら力づくで添え字の値を決定して決めたという。
#include<stdio.h>
#include<map>
int main(){
std::map<int,int> points,splits,lens;
std::map<int,int>::iterator it,it1,it2;
int n,m,s,t,p,minV=2000000000,maxV=0;
scanf("%d %d",&n,&m);
while(n--){
scanf("%d %d",&s,&t);
points[s]=t;
minV=std::min(std::min(minV,s),t);
maxV=std::max(std::max(maxV,s),t);
}
while(m--){
scanf("%d",&p);
if(minV>p||maxV<p) continue;
splits[p]=0;
}
long double ans=0;
int no=0;
splits[0]=0;
for(it=splits.begin();it!=splits.end();it++){
splits[(*it).first]=no;
if(no<2){
lens[no]=(*it).first;
}else{
lens[no]=(*it).first+lens[no-2];
it--;
lens[no]-=(*it).first;
it++;
}
//printf(" %d=%d ",no,lens[no]);
no++;
}
splits[maxV+1]=no;
int no1,no2,p1,p2;
for(it=points.begin();it!=points.end();it++){
s=(*it).first;
t=(*it).second;
it1=splits.upper_bound(s);
it2=splits.upper_bound(t);
it1--;
it2--;
no1=(*it1).second;
no2=(*it2).second;
if(s<t){
if(no1==no2){
ans+=t-s;
}else if(no1%2!=no2%2){
it1++;
//printf("A(%d %d %d %d %d %d) ",(*it1).first,s,no2,no1,lens[no2],lens[no1]);
ans+=(*it1).first-s;
ans+=lens[no2]-lens[no1+1];
}else{
it1++;
//printf("B(%d %d %d %d %d %d) ",(*it1).first,(*it2).first,s,t,lens[no2-1],lens[no1]);
ans+=((*it1).first-s)+(t-(*it2).first);
ans+=lens[no2-1]-lens[no1+1];
}
}else{
if(no1==no2){
ans+=s-t;
}else if(no1%2!=no2%2){
//printf("B(%d %d %d %d %d %d) ",(*it1).first,(*it2).first,s,t,lens[no1-1],lens[no2]);
ans+=(s-(*it1).first);
ans+=lens[no1-1]-lens[no2];
}else{
it2++;
ans+=(s-(*it1).first)+((*it2).first-t);
ans+=lens[no1-1]-lens[no2+1];
}
}
}
printf("%.0Lf\n",ans);
}
*2320 Infinity Maze
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2320
マス目に区切られたマップを東西南北に移動するロボが移動するのでロボの最終位置を答えよという問題。
ロボは東西南北の向きを指定されてスタートし、壁にあたると左に９０度ずつ回りながら進める方向を見つければそちらに向かい指定されたマス進むと停止する。
いきなり壁に囲まれていることはないようである。
解法
素朴にロボの動きをシミュレートします。
マップはせまくロボに同距離が最大１９ケタ近くになるのでロボはどこかで周回軌道に入ります。
そこをショートカットすればこの問題は解決です。
#include<stdio.h>
#include<string.h>
#include<iostream>
int dxs[4]={1,0,-1,0};
int dys[4]={0,1,0,-1};
int h,w;
char map[101][102];
long long int memo[101][102][4];
struct robo{
int muki;
int x,y;
long long int L;
bool move(char map[101][102]){
int nx,ny;
for(int i=0;i<4;i++){
nx=x+dxs[muki];
ny=y+dys[muki];
if(ny<0||h<=ny||nx<0||w<=nx||map[ny][nx]=='#'){
muki=(muki+1)%4;
}else{
break;
}
}
L--;
x=nx;
y=ny;
return true;
}
};
int main(){
while(1){
long long int L;
memset(memo,-1,sizeof(memo));
std::cin>>h>>w>>L;
if(h==0&&w==0&&L==0)break;
robo r;
for(int i=0;i<h;i++){
scanf("%s",map[i]);
for(int j=0;j<w;j++){
char c=map[i][j];
if(c!='.'&&c!='#'){
r.y=i;
r.x=j;
r.L=L;
map[i][j]='.';
if(c=='E')r.muki=0;
if(c=='S')r.muki=1;
if(c=='W')r.muki=2;
if(c=='N')r.muki=3;
memo[i][j][r.muki]=0;
}
}
}
char mukis[10]="ESWN";
bool isLoop=false;
while(1){
//printf("%d %d %c %d\n",r.y,r.x,mukis[r.muki],r.L);
if(r.L<=0||r.move(map)==false||r.L==0){
printf("%d %d %c\n",r.y+1,r.x+1,mukis[r.muki]);
break;
}
if(memo[r.y][r.x][r.muki]==-1){
memo[r.y][r.x][r.muki]=L-r.L;
}else if(memo[r.y][r.x][r.muki]!=-1&&isLoop==false){
r.L=(r.L)%((L-r.L)-memo[r.y][r.x][r.muki]);
isLoop=true;
}
}
}
}
*2311 Dessert Witch
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311
簡単なＣＰＵ同士のオセロ対戦のシミュレーション問題。
簡単すぎて皆やる気が起きなかったのか私のコードがコードサイズ最小でアセプト。
これくらいの問題なら中学生プログラマでも解けそう。
本気でショートコードしたらどれくらい縮むか気になる問題。
#include<stdio.h>
#include<string.h>
char map [9][9];
char next[9][9];
char tMap[9][9];
int dxs[]={ 1, 1, 0,-1,-1,-1, 0, 1};
int dys[]={ 0, 1, 1, 1, 0,-1,-1,-1};
int nx,ny;
void revers(int x,int y,char type,int& revMax){
memcpy(tMap,map,sizeof(map));
int revCount=0;
if(tMap[y][x]!='.')return ;
tMap[y][x]=type;
for(int i=0;i<8;i++){
int dx=dxs[i];
int dy=dys[i];
int tx=x;
int ty=y;
for(int j=0;j<8;j++){
tx+=dx;
ty+=dy;
if(tx<0||tx>7||ty<0||ty>7||map[ty][tx]=='.') break;
if(type==map[ty][tx]){
for(int k=0;k<j;k++){
tx-=dx;
ty-=dy;
revCount++;
tMap[ty][tx]=type;
}
break;
}
}
}
if(revCount>revMax){
revMax=revCount;
memcpy(next,tMap,sizeof(next));
}
}
void saiki(int passCount,char type){
if(passCount>2){
return ;
}else{
memcpy(next,map,sizeof(map));
int revMax=0;
if(type=='o'){
for(int y=0;y<8;y++){
for(int x=0;x<8;x++){
revers(x,y,type,revMax);
}
}
}else{
for(int y=7;y>=0;y--){
for(int x=7;x>=0;x--){
revers(x,y,type,revMax);
}
}
}
memcpy(map,next,sizeof(next));
if(revMax>0){
saiki(0,type=='o'?'x':'o');
}else{
saiki(passCount+1,type=='o'?'x':'o');
}
}
}
int main(){
for(int y=0;y<8;y++)scanf("%s",&map[y]);
saiki(0,'o');
for(int y=0;y<8;y++)printf("%s\n",map[y]);
}
*2317 Class Representative Witch
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317
区切られた数直線上の線分の長さを求める問題。
簡単な問題だけど計算量を落とすのに苦労した問題。
ある点から数えて偶数番目の点を足せばいいのだけど普通に計算したらタイムリミッドが起こるのが目に見えているので奇数番目と偶数番目の地点をメモ化して計算。
最後は、理屈で決めるのがなんだか難しかったので値をprintfしながら力づくで添え字の値を決定して決めたという。
#include<stdio.h>
#include<map>
int main(){
std::map<int,int> points,splits,lens;
std::map<int,int>::iterator it,it1,it2;
int n,m,s,t,p,minV=2000000000,maxV=0;
scanf("%d %d",&n,&m);
while(n--){
scanf("%d %d",&s,&t);
points[s]=t;
minV=std::min(std::min(minV,s),t);
maxV=std::max(std::max(maxV,s),t);
}
while(m--){
scanf("%d",&p);
if(minV>p||maxV<p) continue;
splits[p]=0;
}
long double ans=0;
int no=0;
splits[0]=0;
for(it=splits.begin();it!=splits.end();it++){
splits[(*it).first]=no;
if(no<2){
lens[no]=(*it).first;
}else{
lens[no]=(*it).first+lens[no-2];
it--;
lens[no]-=(*it).first;
it++;
}
//printf(" %d=%d ",no,lens[no]);
no++;
}
splits[maxV+1]=no;
int no1,no2,p1,p2;
for(it=points.begin();it!=points.end();it++){
s=(*it).first;
t=(*it).second;
it1=splits.upper_bound(s);
it2=splits.upper_bound(t);
it1--;
it2--;
no1=(*it1).second;
no2=(*it2).second;
if(s<t){
if(no1==no2){
ans+=t-s;
}else if(no1%2!=no2%2){
it1++;
//printf("A(%d %d %d %d %d %d) ",(*it1).first,s,no2,no1,lens[no2],lens[no1]);
ans+=(*it1).first-s;
ans+=lens[no2]-lens[no1+1];
}else{
it1++;
//printf("B(%d %d %d %d %d %d) ",(*it1).first,(*it2).first,s,t,lens[no2-1],lens[no1]);
ans+=((*it1).first-s)+(t-(*it2).first);
ans+=lens[no2-1]-lens[no1+1];
}
}else{
if(no1==no2){
ans+=s-t;
}else if(no1%2!=no2%2){
//printf("B(%d %d %d %d %d %d) ",(*it1).first,(*it2).first,s,t,lens[no1-1],lens[no2]);
ans+=(s-(*it1).first);
ans+=lens[no1-1]-lens[no2];
}else{
it2++;
ans+=(s-(*it1).first)+((*it2).first-t);
ans+=lens[no1-1]-lens[no2+1];
}
}
}
printf("%.0Lf\n",ans);
}
*2320 Infinity Maze
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2320
マス目に区切られたマップを東西南北に移動するロボが移動するのでロボの最終位置を答えよという問題。
ロボは東西南北の向きを指定されてスタートし、壁にあたると左に９０度ずつ回りながら進める方向を見つければそちらに向かい指定されたマス進むと停止する。
いきなり壁に囲まれていることはないようである。
解法
素朴にロボの動きをシミュレートします。
マップはせまくロボは同距離が最大１９ケタ近くになるのでロボはどこかで周回軌道に入ります。
そこをショートカットすればこの問題は解決です。
#include<stdio.h>
#include<string.h>
#include<iostream>
int dxs[4]={1,0,-1,0};
int dys[4]={0,1,0,-1};
int h,w;
char map[101][102];
long long int memo[101][102][4];
struct robo{
int muki;
int x,y;
long long int L;
bool move(char map[101][102]){
int nx,ny;
for(int i=0;i<4;i++){
nx=x+dxs[muki];
ny=y+dys[muki];
if(ny<0||h<=ny||nx<0||w<=nx||map[ny][nx]=='#'){
muki=(muki+1)%4;
}else{
break;
}
}
L--;
x=nx;
y=ny;
return true;
}
};
int main(){
while(1){
long long int L;
memset(memo,-1,sizeof(memo));
std::cin>>h>>w>>L;
if(h==0&&w==0&&L==0)break;
robo r;
for(int i=0;i<h;i++){
scanf("%s",map[i]);
for(int j=0;j<w;j++){
char c=map[i][j];
if(c!='.'&&c!='#'){
r.y=i;
r.x=j;
r.L=L;
map[i][j]='.';
if(c=='E')r.muki=0;
if(c=='S')r.muki=1;
if(c=='W')r.muki=2;
if(c=='N')r.muki=3;
memo[i][j][r.muki]=0;
}
}
}
char mukis[10]="ESWN";
bool isLoop=false;
while(1){
//printf("%d %d %c %d\n",r.y,r.x,mukis[r.muki],r.L);
if(r.L<=0||r.move(map)==false||r.L==0){
printf("%d %d %c\n",r.y+1,r.x+1,mukis[r.muki]);
break;
}
if(memo[r.y][r.x][r.muki]==-1){
memo[r.y][r.x][r.muki]=L-r.L;
}else if(memo[r.y][r.x][r.muki]!=-1&&isLoop==false){
r.L=(r.L)%((L-r.L)-memo[r.y][r.x][r.muki]);
isLoop=true;
}
}
}
}
