Single Round Match 436 (Div2/250pt)

友達関係のグラフを渡すので、「2ホップ以内の友達の数」が最も多い人の友達の数を返しなさいという問題。

    vector<string> twof(friends); // copy

これでコピーを取れるのか(同一の文字列オブジェクトへの参照を持っているみたいな状態にならないか)不安で確認してしまうというLL脳。

「コピーを作ってから、2ホップでつながっているところを1ホップに書き換えて、位数の最大値をとる」というアルゴリズムで解いた。

class FriendScore {
public:
  int highestScore(vector <string> friends) {
    size_t N = friends.size();
    vector<string> twof(friends); // copy

    for(size_t i=0; i<N; i++){
      for(size_t j=i+1; j<N; j++){
        for(size_t k=j+1; k<N; k++){
	  if(friends[i][j] == 'Y'){
	    if(friends[j][k] == 'Y'){
	      twof[i][k] = 'Y';
	      twof[k][i] = 'Y';
	    }
	    if(friends[i][k] == 'Y'){
	      twof[j][k] = 'Y';
	      twof[k][j] = 'Y';
	    }
	  }
	  if(friends[i][k] == 'Y' && friends[j][k] == 'Y'){
	    twof[i][j] = 'Y';
	    twof[j][i] = 'Y';
	  }
	}
      }
    }
    int result = 0;
    for(size_t i=0; i<N; i++){
      int score = count(twof[i].begin(), twof[i].end(), 'Y');
      if(score > result) result = score;
    }
    return result;
  }
}

ああ、なんだかYの群れがいる。Yの群れがイエティに見える病気。