「AOJ171～180」の編集履歴（バックアップ）一覧はこちら
AOJ171～180 - (2011/08/27 (土) 11:58:52) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
----
*0171 Dice Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171
サイコロを８個組み合わせて、2*2*2の大きなさいころを作るという問題。
サイコロの面にはアルファベットが書かれており、面同士を合わせる時サイの目に描かれている文字が同じアルファベット大文字と小文字である必要があります。
yとYやaとＡのような組み合わせのみ面を組み合わせることができます。
与えられたサイの情報から大きなさいころを組み立てられるか判別してください。
解法
良い解法思いつきませんでした。
さいを回転する関数を作り、さいころを回しては大きなさいころにサイを追加し深さ優先探索で全探索します。
探索中check関数で今まで組み立てた部分が条件を満たすか調べて枝がりをします。
もっと賢い解法もあると思うので調べてみるとよいでしょう。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int ok=abs('A'-'a');
char xais[8][7];
char permXais[8][7];
bool allOK;
bool addOKs[8];
bool check(int deep){
int sa1,sa2,sa3;
if(allOK==true) return false;
if(deep==1){
return abs(permXais[0][2]-permXais[1][3])==ok;
}else if(deep==2){
return abs(permXais[0][4]-permXais[2][1])==ok;
}else if(deep==3){
sa1=abs(permXais[1][4]-permXais[3][1]);
sa2=abs(permXais[2][2]-permXais[3][3]);
return (sa1==ok && sa2==ok);
}else if(deep==4){
return abs(permXais[4][5]-permXais[0][0])==ok;
}else if(deep==5){
sa1=abs(permXais[5][5]-permXais[1][0]);
sa2=abs(permXais[5][3]-permXais[4][2]);
return (sa1==ok && sa2==ok);
}else if(deep==6){
sa1=abs(permXais[6][5]-permXais[2][0]);
sa2=abs(permXais[6][1]-permXais[4][4]);
return (sa1==ok && sa2==ok);
}else if(deep==7){
sa1=abs(permXais[7][5]-permXais[3][0]);
sa2=abs(permXais[7][1]-permXais[5][4]);
sa3=abs(permXais[7][3]-permXais[6][2]);
return (sa1==ok && sa2==ok && sa3==ok);
}
return true;
}
bool flatRound(char* xai,int deep){
char t=xai[2];
xai[2]=xai[1];
xai[1]=xai[3];
xai[3]=xai[4];
xai[4]=t;
return check(deep);
}
bool northRound(char* xai,int deep){
char t=xai[0];
xai[0]=xai[1];
xai[1]=xai[5];
xai[5]=xai[4];
xai[4]=t;
return check(deep);
}
bool eastRound(char* xai,int deep){
char t=xai[0];
xai[0]=xai[3];
xai[3]=xai[5];
xai[5]=xai[2];
xai[2]=t;
return check(deep);
}
void saiki(int deep){
if(deep==8){
allOK=true;
return;
}
char temp[7];
for(int k=0;k<8;k++){
if(addOKs[k]==true){
addOKs[k]=false;
memcpy(&permXais[deep],&xais[k],7);
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(flatRound(permXais[deep],deep))saiki(deep+1);
if(allOK==true) return;
}
northRound(permXais[deep],deep);
}
eastRound(permXais[deep],deep);
for(int i=0;i<4;i++){
if(flatRound(permXais[deep],deep))saiki(deep+1);
if(allOK==true) return;
}
for(int i=0;i<2;i++){
northRound(permXais[deep],deep);
}
for(int i=0;i<4;i++){
if(flatRound(permXais[deep],deep))saiki(deep+1);
if(allOK==true) return;
}
addOKs[k]=true;
}
}
}
bool setData(){
scanf("%s",&xais[0]);
if(xais[0][0]=='0') return false;
memset(addOKs,true,8);
for(int i=1;i<8;i++){
scanf("%s",&xais[i]);
}
allOK=false;
saiki(0);
printf("%s\n",allOK?"YES":"NO");
return true;
}
int main(){
while(setData()==true){
}
}
----
*0173 Haunted House
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0173
午前と午後のお化け屋敷の入場者数から総入場者数と売り上げを出力せよという問題。
解法
簡単な問題なのでただ書くだけです。
午前と午後の違いに注意するくらいです。
#include<stdio.h>
int main(){
char name[16];
int m,n;
while(scanf("%s %d %d",name,&m,&n)!=EOF){
printf("%s %d %d\n",name,n+m,n*300+m*200);
}
}
----
*0174 Badminton
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0174
バトミントンのサーブ記録から試合の得点を求めよという問題です。
解法
データの条件を試合終了時必ず2点差ついていると読みかえますと、最後まで計算した時得点の多い方に一点足せば最後の一点の計算ができます。
それが分かれば後はサーブ記録から互いに１点ずつ計算するだけです。
#include<stdio.h>
bool calc(){
char serve[101];
int score[2],p;
for(int i=0;i<3;i++){
scanf("%s",serve);
if(serve[0]=='0') return false;
p=1;
score[0]=score[1]=0;
while(serve[p]!='\0'){
score[serve[p]-'A']++;
p++;
}
score[score[0]>score[1]?0:1]++;
printf("%d %d\n",score[0],score[1]);
}
return true;
}
int main(){
while(calc()){
}
}
----
*0175 A King in Hawaii
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0175
１０進数を４進数に変換せよという問題。
解法
m進数を表現する時はｍの余りを取りｍで割ってそれを文字列として保存して逆順に出力すれば何進数への変換であっても普遍的に計算できます。
#include<stdio.h>
int main(){
int n,p;
char ans[20];
while(1){
scanf("%d",&n);
if(n==-1) break;
p=0;
if(n==0){
ans[0]='0';
p++;
}
while(n>0){
ans[p]=n%4+'0';
n/=4;
p++;
}
for(int i=p-1;i>=0;i--){
printf("%c",ans[i]);
}
printf("\n");
}
}
----
*0176 What Color?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0176
カラー表が与えられます。
色データがＲＧＢで与えられるので、カラー表の中でその色に最も近い色返すという問題。
解法
書いてある通りに上から実装します。
問題分の指定ではｓｑｒｔを使っていますが重要なのは色の距離だけなので、距離を２乗のまま扱うと計算が楽になります。
#include<stdio.h>
struct color{
int r,g,b;
};
double colorLen2(color c1,color c2){
return (c1.r-c2.r)*(c1.r-c2.r)+(c1.g-c2.g)*(c1.g-c2.g)+(c1.b-c2.b)*(c1.b-c2.b);
}
int main(){
color colors[8]={ {0,0,0},{0,0,255},{0,255,0},{0,255,255}
,{255,0,0}, {255,0,255},{255,255,0},{255,255,255}};
char colorNames[8][8]={"black","blue","lime","aqua", "red","fuchsia","yellow","white"};
color c;
char top;
int ans,len,tempLen;
while(1){
scanf("%c",&top);
if(top=='0') break;
scanf("%2x%2x%2x%c",&c.r,&c.g,&c.b,&top);
ans=0;
len=colorLen2(c,colors[0]);
for(int i=1;i<8;i++){
tempLen=colorLen2(c,colors[i]);
if(len>tempLen){
len=tempLen;
ans=i;
}
}
printf("%s\n",colorNames[ans]);
}
}
----
地球上の２地点の緯度経度が与えられるのでその距離を求めよという問題。
解法
はじめはベクトルと回転行列とcosの逆関数を使って求めました。
これでも十分な解法でしたが。
http://d.hatena.ne.jp/eha_s/20101007/1286464116
↑こちらのページに球面幾何の概念を使った解法が掲載されていました。
ベクトルを使うものより洗練された方法ですので、これを参考にコードを書き直しました。
#include<stdio.h>
#include<math.h>
int main(){
double a,b,c,d;
double cosC,ans;
while(1){
scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
if(a==-1 && b==-1 && c==-1 && d==-1) break;
a=(90.0-a)/180.0*M_PI;
c=(90.0-c)/180.0*M_PI;
cosC =cos((d-b)/180.0*M_PI);
ans=acos(cos(a)*cos(c)+sin(a)*sin(c)*cosC);
printf("%d\n",(int)(ans*6378.1+0.5));
}
}
----
*0179 Mysterious Worm
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0179
一定のルールの下時間とともに体の各部分の体色を変化させていく虫がいます。
この虫が体色を変化させていく時同じ色に落ち着くまでのターン数を答えるという問題です。
解法
シミュレートして、虫の体色変化を幅優先探索で追いかけるだけで簡単に解決できます。
この問題を正答した人たちのデータを見ると、コードの実行速度やコードサイズ、メモリ使用量が人によって違うので色々な解法があるのかもしれません。
調べてみるとよいでしょう。
#include<stdio.h>
#include<queue>
#include<string.h>
#include<set>
struct Worm{
char body[11];
int turn;
bool operator<(const Worm w)const{
for(int i=0;i<10;i++){
if(body[i]!=w.body[i]) return body[i]<w.body[i];
}
return false;
}
};
bool allOK(char body[11]){
char color=body[0];
int p=1;
while(body[p]!='\0'){
if(color!=body[p]) return false;
p++;
}
return true;
}
char changeColor(char t1,char t2){
char ans[3][4]={".bg","b.r","gr."};
int x,y;
if(t1=='r')x=0;
if(t1=='g')x=1;
if(t1=='b')x=2;
if(t2=='r')y=0;
if(t2=='g')y=1;
if(t2=='b')y=2;
return ans[y][x];
}
void calc(char wormBody[11]){
std::queue<Worm> worms;
std::set<Worm> memo;
Worm w,nextW;
memcpy(w.body,wormBody,11);
w.turn=0;
worms.push(w);
memo.insert(w);
int wormSize=strlen(wormBody);
char color;
while(!worms.empty()){
w=worms.front();
nextW=worms.front();
if(allOK(w.body)){
printf("%d\n",w.turn);
return;
}
nextW.turn++;
worms.pop();
for(int i=0;i<wormSize-1;i++){
if(w.body[i]!=w.body[i+1]){
color=changeColor(w.body[i],w.body[i+1]);
nextW.body[i]=nextW.body[i+1]=color;
if(memo.find(nextW)==memo.end()){
memo.insert(nextW);
worms.push(nextW);
}
nextW.body[i]=w.body[i];
nextW.body[i+1]=w.body[i+1];
}
}
}
printf("NA\n");
}
int main(){
char wormBody[11];
while(1){
scanf("%s",wormBody);
if(wormBody[0]=='0') break;
calc(wormBody);
}
}
----
0179の少し賢い解法。
少し賢い方法として、色のそろった状態から初めて逆算して到達できる色のバラケタ状態を全て求めてターン数をメモ化しておきます。
全部生成できたら後はメモを参照するだけです。
このコードでも、これより早いコードを書いている方がいらっしゃるのでもっと賢い方法があるようです。
より賢い方法の予測
r,g,bを2bitで符号化します。
体は１０部位に分かれているので20bit必要です。
int型で虫の体を管理しＢｉｔ演算で虫の体色変化を計算するとよいでしょう。
アルゴリズムそのものを考え直すのが一番ですが、Ｂｉｔ演算で十分高速化できると考えます。
小手先の高速化テクニックですがＢｉｔ演算は有効です。
最も賢い方法の予測
体色から何回の色変更で色がそろうか、探索することなく計算だけで求める関数のようなものを用意できれば最高ですが、この問題はＮＰ困難な可能性が高いのでそのような式は立てれないのではと考えます。
あるルールに従えば自動的に最短手順で色をそろえられる。
そんなルールを探す方が賢そうです。
以下少し賢い方法のコード。
#include<stdio.h>
#include<queue>
#include<string.h>
#include<map>
struct Worm{
char body[11];
int turn;
bool operator<(const Worm& w)const{
return strcmp(w.body,body)>0?true:false;
}
};
void createWorm(char* body,char color,int size){
for(int i=0;i<11;i++){
body[i]=i>=size?'\0':color;
}
}
std::map<Worm,int> memo;
void setWorm(){
std::queue<Worm> worms;
Worm w;
char *colors="rgb";
char color,c1,c2;
for(int wormSize=10;wormSize>1;wormSize--){
w.turn=0;
for(int i=0;i<3;i++){
createWorm(w.body,colors[i],wormSize);
memo[w]=0;
worms.push(w);
}
while(!worms.empty()){
w=worms.front();
worms.pop();
w.turn++;
for(int i=0;i<wormSize-1;i++){
if(w.body[i]==w.body[i+1]){
color=w.body[i];
if(color=='r'){
c1='g';
c2='b';
}else if(color=='g'){
c1='r';
c2='b';
}else{
c1='r';
c2='g';
}
w.body[i]=c1;
w.body[i+1]=c2;
if(memo.find(w)==memo.end()){
worms.push(w);
memo[w]=w.turn;
}
w.body[i]=c2;
w.body[i+1]=c1;
if(memo.find(w)==memo.end()){
worms.push(w);
memo[w]=w.turn;
}
w.body[i]=w.body[i+1]=color;
}
}
}
}
}
int main(){
setWorm();
Worm w;
while(1){
scanf("%s",w.body);
if(w.body[0]=='0') break;
if(memo.find(w)==memo.end()){
printf("NA\n");
}else{
printf("%d\n",memo[w]);
}
}
}
----
*0171 Dice Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171
サイコロを８個組み合わせて、2*2*2の大きなさいころを作るという問題。
サイコロの面にはアルファベットが書かれており、面同士を合わせる時サイの目に描かれている文字が同じアルファベット大文字と小文字である必要があります。
yとYやaとＡのような組み合わせのみ面を組み合わせることができます。
与えられたサイの情報から大きなさいころを組み立てられるか判別してください。
解法
良い解法思いつきませんでした。
さいを回転する関数を作り、さいころを回しては大きなさいころにサイを追加し深さ優先探索で全探索します。
探索中check関数で今まで組み立てた部分が条件を満たすか調べて枝がりをします。
もっと賢い解法もあると思うので調べてみるとよいでしょう。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int ok=abs('A'-'a');
char xais[8][7];
char permXais[8][7];
bool allOK;
bool addOKs[8];
bool check(int deep){
int sa1,sa2,sa3;
if(allOK==true) return false;
if(deep==1){
return abs(permXais[0][2]-permXais[1][3])==ok;
}else if(deep==2){
return abs(permXais[0][4]-permXais[2][1])==ok;
}else if(deep==3){
sa1=abs(permXais[1][4]-permXais[3][1]);
sa2=abs(permXais[2][2]-permXais[3][3]);
return (sa1==ok && sa2==ok);
}else if(deep==4){
return abs(permXais[4][5]-permXais[0][0])==ok;
}else if(deep==5){
sa1=abs(permXais[5][5]-permXais[1][0]);
sa2=abs(permXais[5][3]-permXais[4][2]);
return (sa1==ok && sa2==ok);
}else if(deep==6){
sa1=abs(permXais[6][5]-permXais[2][0]);
sa2=abs(permXais[6][1]-permXais[4][4]);
return (sa1==ok && sa2==ok);
}else if(deep==7){
sa1=abs(permXais[7][5]-permXais[3][0]);
sa2=abs(permXais[7][1]-permXais[5][4]);
sa3=abs(permXais[7][3]-permXais[6][2]);
return (sa1==ok && sa2==ok && sa3==ok);
}
return true;
}
bool flatRound(char* xai,int deep){
char t=xai[2];
xai[2]=xai[1];
xai[1]=xai[3];
xai[3]=xai[4];
xai[4]=t;
return check(deep);
}
bool northRound(char* xai,int deep){
char t=xai[0];
xai[0]=xai[1];
xai[1]=xai[5];
xai[5]=xai[4];
xai[4]=t;
return check(deep);
}
bool eastRound(char* xai,int deep){
char t=xai[0];
xai[0]=xai[3];
xai[3]=xai[5];
xai[5]=xai[2];
xai[2]=t;
return check(deep);
}
void saiki(int deep){
if(deep==8){
allOK=true;
return;
}
char temp[7];
for(int k=0;k<8;k++){
if(addOKs[k]==true){
addOKs[k]=false;
memcpy(&permXais[deep],&xais[k],7);
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(flatRound(permXais[deep],deep))saiki(deep+1);
if(allOK==true) return;
}
northRound(permXais[deep],deep);
}
eastRound(permXais[deep],deep);
for(int i=0;i<4;i++){
if(flatRound(permXais[deep],deep))saiki(deep+1);
if(allOK==true) return;
}
for(int i=0;i<2;i++){
northRound(permXais[deep],deep);
}
for(int i=0;i<4;i++){
if(flatRound(permXais[deep],deep))saiki(deep+1);
if(allOK==true) return;
}
addOKs[k]=true;
}
}
}
bool setData(){
scanf("%s",&xais[0]);
if(xais[0][0]=='0') return false;
memset(addOKs,true,8);
for(int i=1;i<8;i++){
scanf("%s",&xais[i]);
}
allOK=false;
saiki(0);
printf("%s\n",allOK?"YES":"NO");
return true;
}
int main(){
while(setData()==true){
}
}
----
*0173 Haunted House
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0173
午前と午後のお化け屋敷の入場者数から総入場者数と売り上げを出力せよという問題。
解法
簡単な問題なのでただ書くだけです。
午前と午後の違いに注意するくらいです。
#include<stdio.h>
int main(){
char name[16];
int m,n;
while(scanf("%s %d %d",name,&m,&n)!=EOF){
printf("%s %d %d\n",name,n+m,n*300+m*200);
}
}
----
*0174 Badminton
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0174
バトミントンのサーブ記録から試合の得点を求めよという問題です。
解法
データの条件を試合終了時必ず2点差ついていると読みかえますと、最後まで計算した時得点の多い方に一点足せば最後の一点の計算ができます。
それが分かれば後はサーブ記録から互いに１点ずつ計算するだけです。
#include<stdio.h>
bool calc(){
char serve[101];
int score[2],p;
for(int i=0;i<3;i++){
scanf("%s",serve);
if(serve[0]=='0') return false;
p=1;
score[0]=score[1]=0;
while(serve[p]!='\0'){
score[serve[p]-'A']++;
p++;
}
score[score[0]>score[1]?0:1]++;
printf("%d %d\n",score[0],score[1]);
}
return true;
}
int main(){
while(calc()){
}
}
----
*0175 A King in Hawaii
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0175
１０進数を４進数に変換せよという問題。
解法
m進数を表現する時はｍの余りを取りｍで割ってそれを文字列として保存して逆順に出力すれば何進数への変換であっても普遍的に計算できます。
#include<stdio.h>
int main(){
int n,p;
char ans[20];
while(1){
scanf("%d",&n);
if(n==-1) break;
p=0;
if(n==0){
ans[0]='0';
p++;
}
while(n>0){
ans[p]=n%4+'0';
n/=4;
p++;
}
for(int i=p-1;i>=0;i--){
printf("%c",ans[i]);
}
printf("\n");
}
}
----
*0176 What Color?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0176
カラー表が与えられます。
色データがＲＧＢで与えられるので、カラー表の中でその色に最も近い色返すという問題。
解法
書いてある通りに上から実装します。
問題分の指定ではｓｑｒｔを使っていますが重要なのは色の距離だけなので、距離を２乗のまま扱うと計算が楽になります。
#include<stdio.h>
struct color{
int r,g,b;
};
double colorLen2(color c1,color c2){
return (c1.r-c2.r)*(c1.r-c2.r)+(c1.g-c2.g)*(c1.g-c2.g)+(c1.b-c2.b)*(c1.b-c2.b);
}
int main(){
color colors[8]={ {0,0,0},{0,0,255},{0,255,0},{0,255,255}
,{255,0,0}, {255,0,255},{255,255,0},{255,255,255}};
char colorNames[8][8]={"black","blue","lime","aqua", "red","fuchsia","yellow","white"};
color c;
char top;
int ans,len,tempLen;
while(1){
scanf("%c",&top);
if(top=='0') break;
scanf("%2x%2x%2x%c",&c.r,&c.g,&c.b,&top);
ans=0;
len=colorLen2(c,colors[0]);
for(int i=1;i<8;i++){
tempLen=colorLen2(c,colors[i]);
if(len>tempLen){
len=tempLen;
ans=i;
}
}
printf("%s\n",colorNames[ans]);
}
}
----
*0177 Distance Between Two Cities
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0177
地球上の２地点の緯度経度が与えられるのでその距離を求めよという問題。
解法
はじめはベクトルと回転行列とcosの逆関数を使って求めました。
これでも十分な解法でしたが。
http://d.hatena.ne.jp/eha_s/20101007/1286464116
↑こちらのページに球面幾何の概念を使った解法が掲載されていました。
ベクトルを使うものより洗練された方法ですので、これを参考にコードを書き直しました。
#include<stdio.h>
#include<math.h>
int main(){
double a,b,c,d;
double cosC,ans;
while(1){
scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
if(a==-1 && b==-1 && c==-1 && d==-1) break;
a=(90.0-a)/180.0*M_PI;
c=(90.0-c)/180.0*M_PI;
cosC =cos((d-b)/180.0*M_PI);
ans=acos(cos(a)*cos(c)+sin(a)*sin(c)*cosC);
printf("%d\n",(int)(ans*6378.1+0.5));
}
}
----
*0179 Mysterious Worm
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0179
一定のルールの下時間とともに体の各部分の体色を変化させていく虫がいます。
この虫が体色を変化させていく時同じ色に落ち着くまでのターン数を答えるという問題です。
解法
シミュレートして、虫の体色変化を幅優先探索で追いかけるだけで簡単に解決できます。
この問題を正答した人たちのデータを見ると、コードの実行速度やコードサイズ、メモリ使用量が人によって違うので色々な解法があるのかもしれません。
調べてみるとよいでしょう。
#include<stdio.h>
#include<queue>
#include<string.h>
#include<set>
struct Worm{
char body[11];
int turn;
bool operator<(const Worm w)const{
for(int i=0;i<10;i++){
if(body[i]!=w.body[i]) return body[i]<w.body[i];
}
return false;
}
};
bool allOK(char body[11]){
char color=body[0];
int p=1;
while(body[p]!='\0'){
if(color!=body[p]) return false;
p++;
}
return true;
}
char changeColor(char t1,char t2){
char ans[3][4]={".bg","b.r","gr."};
int x,y;
if(t1=='r')x=0;
if(t1=='g')x=1;
if(t1=='b')x=2;
if(t2=='r')y=0;
if(t2=='g')y=1;
if(t2=='b')y=2;
return ans[y][x];
}
void calc(char wormBody[11]){
std::queue<Worm> worms;
std::set<Worm> memo;
Worm w,nextW;
memcpy(w.body,wormBody,11);
w.turn=0;
worms.push(w);
memo.insert(w);
int wormSize=strlen(wormBody);
char color;
while(!worms.empty()){
w=worms.front();
nextW=worms.front();
if(allOK(w.body)){
printf("%d\n",w.turn);
return;
}
nextW.turn++;
worms.pop();
for(int i=0;i<wormSize-1;i++){
if(w.body[i]!=w.body[i+1]){
color=changeColor(w.body[i],w.body[i+1]);
nextW.body[i]=nextW.body[i+1]=color;
if(memo.find(nextW)==memo.end()){
memo.insert(nextW);
worms.push(nextW);
}
nextW.body[i]=w.body[i];
nextW.body[i+1]=w.body[i+1];
}
}
}
printf("NA\n");
}
int main(){
char wormBody[11];
while(1){
scanf("%s",wormBody);
if(wormBody[0]=='0') break;
calc(wormBody);
}
}
----
0179の少し賢い解法。
少し賢い方法として、色のそろった状態から初めて逆算して到達できる色のバラケタ状態を全て求めてターン数をメモ化しておきます。
全部生成できたら後はメモを参照するだけです。
このコードでも、これより早いコードを書いている方がいらっしゃるのでもっと賢い方法があるようです。
より賢い方法の予測
r,g,bを2bitで符号化します。
体は１０部位に分かれているので20bit必要です。
int型で虫の体を管理しＢｉｔ演算で虫の体色変化を計算するとよいでしょう。
アルゴリズムそのものを考え直すのが一番ですが、Ｂｉｔ演算で十分高速化できると考えます。
小手先の高速化テクニックですがＢｉｔ演算は有効です。
最も賢い方法の予測
体色から何回の色変更で色がそろうか、探索することなく計算だけで求める関数のようなものを用意できれば最高ですが、この問題はＮＰ困難な可能性が高いのでそのような式は立てれないのではと考えます。
あるルールに従えば自動的に最短手順で色をそろえられる。
そんなルールを探す方が賢そうです。
以下少し賢い方法のコード。
#include<stdio.h>
#include<queue>
#include<string.h>
#include<map>
struct Worm{
char body[11];
int turn;
bool operator<(const Worm& w)const{
return strcmp(w.body,body)>0?true:false;
}
};
void createWorm(char* body,char color,int size){
for(int i=0;i<11;i++){
body[i]=i>=size?'\0':color;
}
}
std::map<Worm,int> memo;
void setWorm(){
std::queue<Worm> worms;
Worm w;
char *colors="rgb";
char color,c1,c2;
for(int wormSize=10;wormSize>1;wormSize--){
w.turn=0;
for(int i=0;i<3;i++){
createWorm(w.body,colors[i],wormSize);
memo[w]=0;
worms.push(w);
}
while(!worms.empty()){
w=worms.front();
worms.pop();
w.turn++;
for(int i=0;i<wormSize-1;i++){
if(w.body[i]==w.body[i+1]){
color=w.body[i];
if(color=='r'){
c1='g';
c2='b';
}else if(color=='g'){
c1='r';
c2='b';
}else{
c1='r';
c2='g';
}
w.body[i]=c1;
w.body[i+1]=c2;
if(memo.find(w)==memo.end()){
worms.push(w);
memo[w]=w.turn;
}
w.body[i]=c2;
w.body[i+1]=c1;
if(memo.find(w)==memo.end()){
worms.push(w);
memo[w]=w.turn;
}
w.body[i]=w.body[i+1]=color;
}
}
}
}
}
int main(){
setWorm();
Worm w;
while(1){
scanf("%s",w.body);
if(w.body[0]=='0') break;
if(memo.find(w)==memo.end()){
printf("NA\n");
}else{
printf("%d\n",memo[w]);
}
}
}
