2完で微増。CはO(N^2 logN)が重くて落ちてしまった。
1565 -> 1587。
A. Bulbs
問題概要
M 個の, 1〜M の電球はすべて消えている。
N 個のスイッチがある。i 番目のスイッチを押すと、それに接続されている電球 y_i が 点灯する。
いくつかのスイッチを選んで押すことによって、すべての電球を点灯させることができるかどうか判定せよ。
解法
やるだけ。いくつかのスイッチとは書いてあるけど、全部のスイッチを押しても問題はないので、全部押したことにする。
ソース
#include<bits/stdc++.h> using namespace std; int main() { int N, M; bool light[100] = {}; cin >> N >> M; while(N--) { int K; cin >> K; while(K--) { int Y; cin >> Y; light[--Y] = true; } } if(count(light, light + M, true) == M) { cout << "YES" << endl; } else { cout << "NO" << endl; } }
B. Longtail Hedgehog
問題概要
N 頂点 M 辺の自己辺を含まない非連結な無向グラフが与えられる。 N 頂点にはそれぞれ 1 から N の番号が振られている。 このグラフ上にハリネズミを作る。ハリネズミは、以下の条件を満たすものである。
- 1つの 尾 と、いくつかの針から成る。
- 尾は連続的である。すなわち、すべての隣接する尾の頂点は辺が存在する。
- 尾の先頭から最後までの頂点番号は増加列である。
- 針は尾の最後の頂点 Ve にあり、針の数は Ve から出ている頂点数である。
ハリネズミの美しさ = (尾の長さ)×(針の数) を最大化せよ。
解法
ちょっと読解に時間がかかった。もっとスムーズに読みたい・・・
各頂点を尾にしたときのハリネズミの美しさを求め、このうち最大をとることを考える。
任意の頂点が尾の最後となるときに、尾の長さはなるべく長い方が最大になるのは自明。だから、そこに辿り着くまでの増加列の最大の長さが計算できれば良いが、これは、DP で求めることができる。
あと、#define int long long。
ソース
#include<bits/stdc++.h> using namespace std; typedef long long int64; #define int long long int N, M; vector< int > graph[100000], rgraph[100000]; bool used[100000]; vector< int > order; int dp[100000]; signed main() { cin >> N >> M; for(int i = 0; i < M; i++) { int U, V; cin >> U >> V; --U, --V; if(U > V) swap(U, V); graph[U].push_back(V); rgraph[V].push_back(U); } int64 ret = 0; for(int i = 0; i < N; i++) dfs(i); reverse(order.begin(), order.end()); for(int i = 0; i < order.size(); i++) { for(int j = 0; j < rgraph[i].size(); j++) { dp[u] = max(dp[i], dp[rgraph[i][j]] + 1); } ret = max(ret, 1LL * dp[i] * (graph[i].size() + rgraph[i].size())); } cout << ret << endl; }
C. Running Track
問題概要
文字列 S, T が与えられる。S の部分文字列、あるいはそれを反転させた文字列の部分文字列を連結して T を構成したい。最小の部分文字列の部品の数と、その方法を求めよ。
解法
ロリハして二分探索は重いよね。つらい。
Grundyに、そこから取れる最大の部分文字列を取っていけば、部品数は最小になることはちょっと考えればわかる(小さい部分文字列を作っても結局、大きい部分文字列の部分文字列を使って損)。
で、最大の部分文字列は LCP(Longest Common Prefix) そのものなので、 LCPテーブルをDPで事前に構築しておけば、O(N)。
これで、O(N^2) となって間に合う。
ソース
#include<bits/stdc++.h> using namespace std; int LCP1[2200][2200]; int LCP2[2200][2200]; int main() { string S, T, W; cin >> S; T = S; reverse(T.begin(), T.end()); cin >> W; for(int i = S.size() - 1; i >= 0; i--) { for(int j = W.size() - 1; j >= 0; j--) { LCP1[i][j] = S[i] == W[j] ? LCP1[i + 1][j + 1] + 1 : 0; } } for(int i = T.size() - 1; i >= 0; i--) { for(int j = W.size() - 1; j >= 0; j--) { LCP2[i][j] = T[i] == W[j] ? LCP2[i + 1][j + 1] + 1 : 0; } } vector< pair< int, int > > hoge; int ret = 0; for(int i = 0; i < W.size(); ) { pair< int, int > pos(0, INF); for(int j = 0; j < S.size(); j++) pos = max(pos, {LCP1[j][i], j + 1}); for(int j = 0; j < S.size(); j++) pos = max(pos, {LCP2[j][i], j - S.size()}); if(pos.first == 0) { cout << -1 << endl; exit(0); } ++ret; if(pos.second > 0) hoge.push_back({pos.second, pos.first + pos.second - 1}); else hoge.push_back({-pos.second, -pos.second - pos.first + 1}); i = i + pos.first; } cout << ret << endl; for(int i = 0; i < hoge.size(); i++) { cout << hoge[i].first << " " << hoge[i].second << endl; } }