- やるだけ。
- topcoderはグラフは隣接行列の文字列表現で与えられるぽいのでそれの練習的な。
- このコードでは重複の処理を考えたくないので2友達かどうかを示すフラグテーブルを構成しているけど、@chokudai さんのライブコーディングではちゃんと重複が起こらないようにループを回して、直接数を数えていた。この辺の小技が即出てくるのは、さすが。
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
using namespace std;
class FriendScore{
public:
vector<vector<bool> > edge;
int n;
vector<vector<bool> > friends2;
void print(vector<vector<bool> >& x){
for(int i = 0; i < n; i++){
copy(x[i].begin(), x[i].end(), ostream_iterator<bool>(cout, " "));
cout << endl;
}
}
int highestScore(vector <string> friends){
edge.clear();
friends2.clear();
n = friends.size();
edge.resize(n, vector<bool>(n, false));
friends2.resize(n, vector<bool>(n, false));
parse(friends);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(edge[i][j]){
friends2[i][j] = true;
for(int k = 0; k < n; k++){
if(edge[j][k]){
friends2[i][k] = true;
}
}
}
}
}
vector<int> count(n, 0);
for(int i = 0; i < n; i++){
friends2[i][i] = false;
for(int j = 0; j < n; j++){
if(friends2[i][j]){
count[i]++;
}
}
}
return *max_element(count.begin(), count.end());
}
void parse(const vector<string>& f){
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
edge[i][j] = edge[j][i] = (f[i][j] == 'Y');
}
}
}
};