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

るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 534 Div2

TopCoder

250: EllysDirectoryListing

やるだけ

class EllysDirectoryListing {
public:
  vector <string> getFiles(vector <string> files) {
    int one = 0,two = 0,last = files.size() - 1;
    rep(i,files.size()){
      if(files[i] == ".") one = i;
      else if(files[i] == "..") two = i;
    }
    if((one == last && two == last - 1) || (one == last - 1 && two == last)) return files;
    swap(files[one < two ? one: two],files[last]);
    rep(i,files.size()){
      if(files[i] == ".") one = i;
      else if(files[i] == "..") two = i;
    }
    if((one == last && two == last - 1) || (one == last - 1 && two == last)) return files;
    swap(files[one < two ? one: two],files[last - 1]);

    return files;
  }
};


500: EllysCheckers

先手が勝つか否か。多分Nim和とか使うんだろうけど思いつかなかった。(あまりよく理解していない)

数研部失格

ビットdpでも解けるらしい。

map<int,int>dp;
int N;
class EllysCheckers {
public:
  int dfs(int state){
    state = state & ~1;
    if(state == 0) return 0;
    if(dp.find(state) != dp.end()) return dp[state];
    for(int i = N - 1; i >= 1; i--){
      if((state & (1 << i)) != 0 && (state & (1 << (i - 1))) == 0){
	int res = dfs((state & ~(1 << i)) | (1 << (i - 1)));
	if(res == 0) return dp[state] = 1;
      }
    }
    for(int i = N - 1; i >= 3; i--){
      if((state & (1 << i)) != 0){
	if((state & (1 << (i - 1))) != 0 && (state & (1 << (i - 2))) != 0 && (state & (1 << (i - 3))) == 0){
	  int tmp = dfs((state & ~(1 << i)) | (1 << (i - 3)));
	  if(tmp == 0) return dp[state] = 1;
	}
      }
    }
    return dp[state];
  }
  string getWinner(string board) {
    N = board.size();
    int stage = 0;
    rep(i,board.size())
      if(board[i] == 'o') stage |= (1 << (board.size() - 1 - i));
    return dfs(stage) ? "YES" : "NO";
  }

};