ABC478 E - lt and le
- サイト
- AtCoder
- コンテスト
- ABC478
- 問題
- E - lt and le
- 難易度
- 1376
以上 以下の整数からなる長さ の列 で、 個の条件「」または「」をすべて満たすものがあるかを判定し、あれば 1 つ出力する問題です()。
条件 、 のどちらも、頂点 から への辺だと思ってグラフを作り、強連結成分(SCC)分解します。
- 同じ SCC の中の頂点は、辺をたどって一周できるので、 となり、すべて同じ値でなければなりません。したがって、 の辺の両端が同じ SCC にあれば No です。
- そうでなければ、SCC をトポロジカル順に並べたときの番号( 始まり)をそのまま にすれば条件をすべて満たします。異なる SCC 間の辺は必ず番号が増える向きなので も も満たし、同じ SCC 内の辺はすべて なので等しい値で満たします。番号は 以下です。
ACL の scc_graph::scc() は成分をトポロジカル順に返すので、その添字をそのまま使えます。計算量は です。
本番の解答は嘘解法だった
Section titled “本番の解答は嘘解法だった”本番では次の方針で提出し、AC しました。
- の辺だけで SCC 分解し、同じ成分を「等しい値になるグループ」として DSU でまとめる
- すべての辺で SCC 分解し、異なるグループが同じ SCC に入ったら No
- そうでなければ SCC の番号を出力する
ところが、同じグループ(等しくなることが決まった頂点どうし)の間に の辺がある場合を見落としていました。 の辺で弾いていたのは のときだけです。たとえば
2 30 1 20 2 11 1 2は が必要なのに も要求されているので答えは No ですが、本番のコードは Yes と 1 1 を出力してしまいます。テストケースにこの形がなかったため通ってしまったようです。
上の解法のように、 の辺の両端が同じ SCC にあるかを最後に確かめれば、この場合も正しく No になります(修正版で AC を確認しました)。そもそも DSU も 2 回目の SCC も要らず、SCC 1 回で十分でした。
C++(修正版・AC)
#include "atcoder/scc"#include "sh-library/base/all"
void solve() { LL(N, Q); VAL(TUV, Q, 3); atcoder::scc_graph g(N); for (auto &[t, u, v] : TUV) { u--, v--; g.add_edge(u, v); } auto scc = g.scc(); vl ans(N); rep(i, scc.size()) { for (ll x : scc[i]) ans[x] = i + 1; } for (auto [t, u, v] : TUV) { if (t == 1 and ans[u] == ans[v]) { No; } } print("Yes"); print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}使用ライブラリ:cpp_include@6c2f83f
C++(本番の提出・嘘解法)
#include "atcoder/dsu"#include "atcoder/scc"#include "sh-library/base/all"
void solve() { LL(N, Q); VAL(TUV, Q, 3); atcoder::dsu h(N); { atcoder::scc_graph g0(N); for (auto &[t, u, v] : TUV) { u--, v--; if (t == 0) { g0.add_edge(u, v); } else { if (u == v) { print("No"); return; } } } auto tmp = g0.scc(); for (auto &x : tmp) { rep(i, 1, x.size()) { h.merge(x[0], x[i]); } } } { atcoder::scc_graph g(N); for (auto &[t, u, v] : TUV) { if (t == 0 && h.same(u, v)) { g.add_edge(v, u); } g.add_edge(u, v); } auto tmp = g.scc(); for (auto &x : tmp) { rep(i, 1, x.size()) { if (h.same(x[0], x[i])) continue; print("No"); return; } } vl ans(N); rep(i, tmp.size()) { for (ll a : tmp[i]) { ans[a] = i + 1; } } print("Yes"); print(ans); }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}使用ライブラリ:cpp_include@6c2f83f