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

SRM 426 Div2Easy KnockoutTourney

問題概要
トーナメント戦で自分とライバルが当たるのは何ラウンド目か求めよ。ライバルと当たるまでの試合は互いに全て勝つものとする。

解法
自分とライバルの位置だけtrueにしたvectorを用意し、vectorの隣同士で比較し、論理和を取りながらtrue同士が衝突するまで実行する全探索。

解答コード

class KnockoutTourney {
public:
  int meetRival(int N, int you, int rival) {
    
    vector<bool> now(N, false);
    you --, rival --;
    now[you] = now[rival] = true;
    
    int ans = 1;
    while(now.size() > 1) {
      vector<bool> next;
      for(int i=0; i<now.size(); i+=2) {
	if(i+1 < now.size() && now[i] && now[i+1]) {
	  goto EXIT;
	}
	else if(i+1 < now.size()) {
	  next.PB(now[i] | now[i+1]);
	}
	else {
	  next.PB(now[i]);
	}
      }
      now = next;
      ans ++;
    }
    
  EXIT:;
    return ans;
  }
};