Codeforces Round #338 (Div. 2)

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;
  }
}

ei1333の日記

ぺこい

Codeforces Round #338 (Div. 2)

A. Bulbs

問題概要

解法

ソース

B. Longtail Hedgehog

問題概要

解法

ソース

C. Running Track

問題概要

解法

ソース