マトリョーシカ的日常

ワクワクばらまく明日のブログ。

アリさんの立方体(topcoder SRM507 div2 250pt)

プログラムを組むより、問題を説明する方が頭を使ったりする。

 cube sugars - 無料写真検索fotoq
photo by maaco

 TopCoder Statistics - Problem Statement

 今年に入ってから、毎日プログラミングをするようになった。それがプラスに働くかはこれからの未来に期待しよう。夏頃にはマイコンをつかって簡単なロボットを作りたい。

 問題。立方体の各頂点に0から7まで番号を降る。複数匹のアリさんは頂点にランダムに配置されている。ここで0番に角砂糖を置く。各頂点にいたアリは瞬時に気づき、立方体の辺を伝って同時に最短距離で角砂糖に向かう。一辺を動くのに1ターンを消費し、同じ頂点にアリがいても彼らには影響はない。配置されている場所が与えられているとき、全てのアリが角砂糖に近づくまでのターン数を返せ。
 番号は0番を立方体の上左手前に置くと、反時計回りに0,1,2,3。下の四角形は4,5,6,7となっている。
 例:
 int[ ]={0} :0番にアリが一匹居る。ターン数は0。
 int[ ]={0,1} :0番、1番に各一匹。ターン数は1。
 int[ ]={6,1,6} :6番に二匹、1番に一匹。ターン数は3。
 int[ ]={7,7,3,3,7,7,3,3} :ターン数は2。


 以下、コード。

#include 
#include 
#include 
#include 
using namespace std;
 class CubeAnts{
	public:
	int getMinimumSteps (vector  pos){
        int A[7]={6,2,5,7,1,3,4};
        for(int j=0;j<7;j++){
            vector ::iterator it=find(pos.begin(),pos.end(),A[j]);
            if (it != pos.end()){
                if(A[j]==6) return 3;
                if(A[j]==2 ||A[j]==5 ||A[j]==7) {printf("2");return 2;}
                if(A[j]==1 ||A[j]==3 ||A[j]==4) {printf("1");return 1;}
            }
        }
        printf("0");
        return 0;
    }
};

int main(){
    CubeAnts ob1;
    int n=10;
    int posA[50]={0,1};
    vector  pos(&posA[0],&posA[n]);
    ob1.getMinimumSteps(pos);
    return 0;
}
  • vector ::iterator it=find(pos.begin( ),pos.end( ),A[j]);で、vector型のposにA[j]があるかどうか調べる。あれば it != pos.end( )。
  • どうでもいいけど、macbookのキーボードにはホーム、エンドキーがない。Command+矢印キーで代用できる。

かっこいいアルゴリズムを書くよりも、正攻法でやった方が早い例だと思う。