AtCoder Beginner Contest 218 ABC218 参加記
jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 218での成績：2007位
— naga (@long_ng_cp) September 11, 2021
パフォーマンス：1136相当
レーティング：1428→1402 (-26) :(#AtCoder #ABC218 https://t.co/gykafsug4z
:(
A - Weather Forecast
解説
判定します。
実装
int main() { int N; string S; cin >> N >> S; if(S[N - 1] == 'o') { cout << "Yes" << endl; } else { cout << "No" << endl; } }
B - qwerty
解説
C++ではchar型に数字を足し算をしたあと、さらにchar型にcastできます。
実装
int main() { vector<int> P(26); cin >> P; rep(i,26){ cout << char('a' + P[i] - 1); } cout << endl; }
C - Shapes
解説
実装重すぎるというか、この程度も実装できなかったの？という気持ちに。回して左上からの相対位置で判定。
実装
int main() { int N; cin >> N; vector<string> S(N), T(N); auto find_top_left = [&](const vector<string> &v) -> pair<int, int> { rep(i, N) rep(j, N) { if(v[i][j] == '#') { return {i, j}; } } return {-1, -1}; }; auto rotate = [&](vector<string> &v) -> void { vector<string> tmp = v; rep(i,N){ rep(j,N){ v[i][j] = tmp[j][N-1-i]; } } return; }; cin >> S >> T; rep(_, 4) { auto [sx, sy] = find_top_left(S); auto [tx, ty] = find_top_left(T); vector<pair<int, int>> s, t; rep(i,N){ rep(j,N){ if(S[i][j] == '#'){ s.push_back({i-sx, j-sy}); } if(T[i][j] == '#'){ t.push_back({i-tx, j-ty}); } } } if(s == t){ cout << "Yes" << endl; return 0; } rotate(S); } cout << "No" << endl; }
D - Rectangles
解説
すべての辺がx軸/y軸に平行な長方形は、a < A, b < Bとして(a, b), (a, B), (A, b), (A, B)であるということを使います。最後に2で割ると通ります。理由はわかりません。
実装
int main() { int N; cin >> N; map<pair<int, int>,int> mp; vector<pair<int, int>> xy; rep(i,N){ int x, y; cin >> x >> y; xy.emplace_back(x, y); mp[{x, y}]++; } sort(all(xy)); ll ans = 0; rep(j,N){ rep(i,j){ auto [a, b] = xy[i]; auto [A, B] = xy[j]; if(a == A)continue; if(b == B)continue; if(mp.count({a, B}) && mp.count({A, b})){ ans++; } } } cout << ans/2 << endl; }
E - Destruction
解説
多重辺、自己ループは、価値が最小の1本以外は取るか、捨てるか（無視）していいです。 以降、多重辺、自己ループのなくなったグラフで考えます。
最低でN-1本の辺ですべての頂点を連結にできます（例えば木）。言い方を変えると、それ未満の辺の本数ではグラフを連結にすることはできません。よって、N-1本は必ず使います。
グラフの辺をとっていくのはすごく面倒なのはよく知っているので、逆の操作を考えます。つまり、辺を削除して報酬を得るのではなく、変を追加する操作によって報酬を捨てていくことを考えます。こう考えると、価値の小さい方から捨てていくのが自然になります。頂点(a, b)をつなぐある辺を追加するべき（捨てるべき）か否かは、それらの頂点が既に連結かどうかで判定します。連結なら、もう一度つなぐ必要もないので、繋ぎません。連結でないなら、繋ぎます。
このようなアルゴリズムにより、すべてが連結になるまで、価値の小さい辺から貪欲に追加していくことで、今回の問題を解くことができます。UnionFindを使うことで、実行制限以内に解くことができました。
実装
int main() { int N, M; cin >> N >> M; vector<pair<ll, pair<int, int>>> es; ll ans = 0; UnionFind T(N); rep(i,M){ int a, b; ll c; cin >> a >> b >> c; a--, b--; if(a == b){ ans += max(0LL, c); continue; } if(c <= 0){ T.unite(a, b); continue; } es.push_back({c, {a, b}}); } // 報酬が小さい順に連結していく sort(all(es)); for(auto [c, ab]: es){ auto [a, b] = ab; if(T.same(a, b)){ ans += c; } else{ T.unite(a, b); } } cout << ans << endl; }
F - Blocked Roads
解説
ある辺が使えなくなった時の最短経路を求める問題。 1からNへの最短経路なので、経路で使う辺は高々N-1、というのがポイント。
まず、ある1->Nへの経路を決めます。それに含まれない辺については、あろうがなかろうが経路に変更はありません。その経路に含まれる辺が通れなくなった場合のみ、最短経路を計算し直すことで、計算量はO(N(N+M))となり、十分高速です。
実装
int main() { int N, M; cin >> N >> M; vvec<int> G(N); vector<pair<int, int>> st; vector<int> dist(N, INF); vector<int> pre(N, -1); rep(i, M) { int s, t; cin >> s >> t; s--, t--; st.emplace_back(s, t); G[s].push_back(t); } std::queue<int> q; q.push(0); dist[0] = 0; while(!q.empty()) { int v = q.front(); q.pop(); for(auto n : G[v]) { if(dist[n] != INF) continue; dist[n] = dist[v] + 1; pre[n] = v; q.push(n); } } if(dist[N - 1] == INF) { rep(i, M) { cout << -1 << endl; } return 0; } int v = N - 1; vector<pair<int, int>> tour; map<pair<int, int>, int> mp; while(v != 0) { tour.push_back({pre[v], v}); mp[tour.back()]++; v = pre[v]; } rep(i, M) { auto [s, t] = st[i]; if(mp[{s, t}]) { // 計算し直し vector<int> dist2(N, INF); std::queue<int> q2; q2.push(0); dist2[0] = 0; while(!q2.empty()) { int v = q2.front(); q2.pop(); for(auto n : G[v]) { if(dist2[n] != INF) continue; if(v == s && n == t)continue; dist2[n] = dist2[v] + 1; q2.push(n); } } cout << (dist2[N-1] == INF ? -1: dist2[N-1]) << endl; } else { cout << dist[N - 1] << endl; } } }
