読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

SRM 148 Div2

SRM Topcoder

250:
問題概要
int型の変数numberが与えられる
numberに含まれる数字でnumberを割りきれるものの数をリターンしろ
0はいかなる値も割り切らない

解法
実際にやってみる

コード:

class DivisorDigits {
	public:
  string itos(int d){stringstream ss;ss << d; return ss.str();}
	int howMany(int number) {
	  string sn = itos(number);
	  int cnt = 0;
	  for(int i=0;i<sn.size();i++)
	    {
	      if(sn[i] == '0')
		continue;
	      if(number % (sn[i]-'0') == 0)
		cnt++;
	    }

	    return cnt;
	}
};

600:
問題概要
AからZまでのアルファベットの位置の値を"*:*"の形で指定されたように変更する
"*:*"は左の*と右の*のアルファベットの位置の値をスワップすることを意味する
最初にアルファベットのAからZまで正しい位置にある
例:
A B C D ・・・ Z
A:B -> B A C D ・・・ Z
B:C -> B C A D ・・・ Z

解法
実際にやってみる

コード:

class CeyKaps {
	public:
	string decipher(string typed, vector <string> switches) {
	  char alpha[28];
	  for(int i=0;i<26;i++)
	    alpha[i] = (char)('A'+i);
	  
	  for(int i=0;i<switches.size();i++)
	    swap(alpha[switches[i][0]-'A'],alpha[switches[i][2]-'A']);
	  int index[27];
	  for(int i=0;i<26;i++)
	    index[alpha[i]-'A'] = i;
	  
	  string ret;
	  for(int i=0;i<typed.size();i++)
	    ret += (char)('A'+index[typed[i]-'A']);
	  
	  return ret;	
	}
};

1000:
問題概要
0以上9以下の数字が9個与えられる
そこから作れる3*3のmagic number squareの数をリターンせよ
magic number squareとは各列と各行の和が全て等しいsquareのことである

解法
これまた実際にやってみる

コード:

class MNS {
	public:
  map<vector<int>,bool> memo; 
  long long sum;

  bool check(vector<int>& n)
  {
    int sum = n[0] + n[1] + n[2];
    if(sum == (n[3]+n[4]+n[5]) && sum == (n[6]+n[7]+n[8]) && sum == (n[0]+n[3]+n[6]) && sum == (n[1]+n[4]+n[7]) && sum == (n[2]+n[5]+n[8]) )
       return true;
    return false;
  }

  string vtos(vector<int>& n,int pos)
  {
    stringstream ss;
    for(int i=0;i<pos;i++)
      ss << n[i];
    return ss.str();
  }

  void dfs(vector<int>& x,vector<int>& n,int pos,int used)
  {
    if(pos)
      {
	if(pos >= 9)
	  {	    
	    if(memo[x])
	      return;
	    memo[x] = true;
	    
	    if(check(x))
	      sum++;
	    return ;
	  }
      }
	
    for(int i=0;i<9;i++)
      {
	if((used >> i) & 1)
	  continue;
	x[pos] = n[i];
	dfs(x,n,pos+1,used|(1<<i));
      }

  }  

  int combos(vector <int> numbers) {
    memo.clear();
    sum = 0;
    vector<int> x(9);
    dfs(x,numbers,0,0);
    return sum;
  }
};