AtCoder が提供しているABC(AtCoder Beginner Contest)016 C問題をC++で解いてみました。ABC016は、2014年12月6日21:05に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 友達の友達(Difficulty : 830(参考値))
問題の詳細は、リンク先をご覧ください。
グラフのすべての頂点間の距離を求める典型問題です。AtCoder Problems による Difficulty は 830(参考値)でした。
解答案
C++ プログラム例(ABC016C)
友人関係をグラフと考えて、頂点間の距離が2である組み合わせの数を求めます。頂点間の距離は、ワーシャル・フロイド法を使い求めました。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> dist(n, vector<int>(n, INF));
for (int i = 0; i < n; ++i) {
dist[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
--a;
--b;
dist[a][b] = 1;
dist[b][a] = 1;
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if ((dist[i][k] < INF) && (dist[k][j] < INF)) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
for (int i = 0; i < n; ++i) {
int result = 0;
for (int j = 0; j < n; ++j) {
if (dist[i][j] == 2) {
++result;
}
}
cout << result << endl;
}
return 0;
}
AC(Accepted=正しいプログラム)と判定されました。
最後に
この時期には、グラフの頂点間の距離を求める典型問題が何回か出題されていました。
引き続き ABC の問題を紹介していきます。