アルゴリズム実技検定のE問題で初歩的なミスをしたので、今後同じようなミスをしないようにメモをしておきます。内容はタイトル通りです。
目次
1.問題
グラフ問題です。ただし、3種類の操作があるので、それぞれをちゃんと実装しなければなりません。
2.やらかした点
次のようなコードを提出しました。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| int n; | |
| cin >> n; | |
| bool follow[n][n] = {}; | |
| int q; | |
| cin >> q; | |
| rep(i, q) { | |
| int a; | |
| cin >> a; | |
| int user, followed_user; | |
| if (a == 1) { | |
| cin >> user >> followed_user; | |
| user--, followed_user--; | |
| follow[user][followed_user] = true; | |
| } else if (a == 2) { | |
| cin >> user; | |
| user--; | |
| rep(i, n) follow[user][i] = follow[i][user]; | |
| } else { | |
| cin >> user; | |
| user--; | |
| // debug | |
| rep(i, n) { | |
| rep(j, n) { | |
| if (follow[i][j]) | |
| cout << 'Y'; | |
| else | |
| cout << 'N'; | |
| } | |
| cout << endl; | |
| } | |
| cout << "--------" << endl; | |
| rep(i, n) { | |
| cout << "(user,i)=(" << user << "," << i << ")," << follow[user][i] | |
| << endl; | |
| } | |
| rep(i, n) { | |
| if (follow[user][i]) { | |
| rep(j, n) { | |
| if (follow[i][j]) { | |
| cout << "i=" << i << ",j=" << j << endl; | |
| follow[user][j] = true; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| rep(i, n) { | |
| rep(j, n) { | |
| if (follow[i][j]) | |
| cout << 'Y'; | |
| else | |
| cout << 'N'; | |
| } | |
| cout << endl; | |
| } | |
| return 0; | |
| } |
by 問題となったのは次の部分。
rep(i, n) {
if (follow[user][i]) {
rep(j, n) {
if (follow[i][j]) {
cout << "i=" << i << ",j=" << j << endl;
follow[user][j] = true;
}
}
}
}
これは、操作のフォローフォローを実装しようとしたものです。”ある人がフォローしている人"がフォローしている人をフォローするという、友達の友達は友達と言った操作です。
さて、この実装で動かすと良さそうに見えます。しかし、正常には2と5(二次元配列では1と4)の場合のみif文が実行されるはずなのに、3(二次元配列では2)も通るようになります。
3.なにが駄目だったか
上の実装では、誰かがフォローしている人をフォローするたびに二次元配列の要素を書き換えています。このため、2(2次元配列では1)は3(二次元配列では2)をフォローしているので、2がフォローしている人をフォローした時、二次元配列が次のように書き換えられます。
follow[0][2] = false -> follow[0][2] = true
すると、外側のループでiがインクリメントされた時、次は1が3をフォローしているかという判定がされ、先程フォローしたことになったので、if文内の処理に移ります。
毎回要素を書き換えてしまうので、操作前はフォローしてなかった人も操作の途中でフォローしてしまい、本来処理しない人の分まで処理してしまっています。
4.ACしたコード
結局次のように実装するとACできました。該当部分だけでなく、フォロー返しの部分も実装を変更しています。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| int n; | |
| cin >> n; | |
| bool follow[n][n] = {}; | |
| int q; | |
| cin >> q; | |
| rep(i, q) { | |
| int a; | |
| cin >> a; | |
| int user, followed_user; | |
| if (a == 1) { | |
| cin >> user >> followed_user; | |
| user--, followed_user--; | |
| follow[user][followed_user] = true; | |
| } else if (a == 2) { | |
| cin >> user; | |
| user--; | |
| rep(i, n) if (follow[i][user]) follow[user][i] = true; | |
| } else { | |
| cin >> user; | |
| user--; | |
| vector<int> user_follower; | |
| rep(i, n) if (follow[user][i]) user_follower.push_back(i); | |
| for (int num : user_follower) { | |
| rep(i, n) { | |
| if (follow[num][i]) follow[user][i] = true; | |
| } | |
| } | |
| } | |
| } | |
| rep(i, n) follow[i][i] = false; | |
| rep(i, n) { | |
| rep(j, n) { | |
| if (follow[i][j]) | |
| cout << 'Y'; | |
| else | |
| cout << 'N'; | |
| } | |
| cout << endl; | |
| } | |
| return 0; | |
| } |
操作前に、該当ユーザがフォローしている人を予め抽出しておき、その抽出したユーザに対してのみ処理を行うようにしています。
5.結論
処理の途中で安直に配列内の要素を書き換えてはいけない。