SRM550

250 - EasyConversionMachine

■問題
'a'と'b'からなる２つの文字列の片方の文字列中の文字をk回交換したときに2つの文字列を等しくできるかどうかを調べる。

■解法
異なる箇所の数の数えて頑張る。

■ソース

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <cfloat>

#include <map>

#include <utility>

#include <set>

#include <iostream>

#include <memory>

#include <string>

#include <vector>

#include <algorithm>

#include <functional>

#include <sstream>

#include <complex>

#include <stack>

#include <queue>

using namespace std;

static const double EPS = 1e-5;

typedef long long ll;



class EasyConversionMachine {

public:

  string isItPossible(string originalWord, string finalWord, int k) {

    string result;

    for(int i=0;i<originalWord.size();i++){

      if(originalWord[i] != finalWord[i]){

	k--;

      }

    }

    if(k<0 || k%2) return "IMPOSSIBLE";

    else return "POSSIBLE";

  }


};

550 - RotatingBot

■問題
壁に当たると左に向くやつがあります。
それが入力の通りに進むにはどれだけの面積が必要ですか。

■解法
2回進んで左上にいるところから戻るように２歩、進むように残りの歩数進め、通った場所に行っていないか壁で回転しているかを判定しながら頑張る。

■ソース

  int minArea(vector <int> moves) {

    int result=0;

    int m[200][200]={0};

    int dx[]={1,0,-1,0};

    int dy[]={0,-1,0,1};

    int s=moves.size();

    int l[2]={0};

    int x,y;

    for(int i=0;i<s && i < 4;i++){

      if(l[i%2] <= moves[i]){

	l[i%2]=moves[i];

      }

    }

    for(int i=0;i<l[0]+2;i++){

      m[i][0] = 1;

      m[i][l[1]+2] = 1;

    }    

    for(int i=0;i<l[1]+2;i++){

      m[0][i] = 1;

      m[l[0]+2][i] = 1;

    }



    if(s < 2) return (l[0]+1) * (l[1]+1);

    x=l[0]+1;

    y=1;

    m[x][y]=1;

    for(int i=1;i>=0;i--){

      for(int j=0;j<moves[i];j++){

	x+=dx[i%4]*-1;

	y+=dy[i%4]*-1;

	if(m[x][y]){

	  return -1;

	}

	m[x][y]=1;

      }

    }

    x=l[0]+1;

    y=1;

    for(int i=2;i<s;i++){

      for(int j=0;j<moves[i];j++){

	x+=dx[i%4];

	y+=dy[i%4];

	if(m[x][y]){

	  return -1;

	}

	m[x][y]=1;

      }

      if(i != s-1){

	if(!m[x+dx[i%4]][y+dy[i%4]]){

	  return -1;

	}

      }

    }   

    

    result = (l[0]+1) * (l[1]+1);

    return result;

  }