Codeforces Round #369 (Div. 2)

4完. 135位(Div2). 1891 -> 1935(+44).

A. Bus to Udayland

問題概要

${n(1 \le n \le 1000)}$ 行 ${4}$ 列に座席がある. 座席は通路で ${2}$ つにわけられている. 座席の一部は既に誰かが座っている.

このとき, ${2}$ 人が同じ行で同じ組の座席に座れることができるのならそれを出力せよ.

解法

上から愚直に座れるかどうか見ていけば良い.

${O(n)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  string S[1000];

  cin >> N;

  bool regist = false;
  for(int i = 0; i < N; i++) {
    cin >> S[i];
    if(!regist) {
      if(S[i][0] == 'O' && S[i][1] == 'O') {
        S[i][0] = S[i][1] = '+';
        regist = true;
      } else if(S[i][3] == 'O' && S[i][4] == 'O') {
        S[i][3] = S[i][4] = '+';
        regist = true;
      }
    }
  }
  if(!regist) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
    for(int i = 0; i < N; i++) {
      cout << S[i] << endl;
    }
  }
}

B. Chris and Magic Square

問題概要

${n \times n(1 \le n \le 500)}$ の魔方陣がある. ${1}$ つのセルだけ値が空なので, このセルに値 ${x}$ を入れたい.

魔法陣を完成させるもののうち, ${1 \le x \le 10^{18}}$ を満たす整数 ${x}$ が存在するならそれを出力せよ.

解法

${n = 1}$ のとき, ${1 \le x \le 10^{18}}$ を満たす任意の値を出力すれば良い.

${n \ge 2}$ のとき, すべて埋まっている列が少なくとも ${1}$ つ存在するので, この列の和によって各ラインで必要な値が一意に定まることがわかる. 空のセルにその値を入れた後魔法陣の条件を満たせるか調べれば良い.

ソース

やたら長くなって時間を溶かした....

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int64 N, X[500][500];
  int x, y;

  cin >> N;

  if(N == 1) {
    cout << 1 << endl;
    return (0);
  }

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cin >> X[i][j];
      if(X[i][j] == 0) {
        x = j, y = i;
      }
    }
  }

  int64 val, sum;
  bool zero;

  for(int i = 0; i < N; i++) {
    zero = false;
    sum = 0;
    for(int j = 0; j < N; j++) {
      sum += X[i][j];
      zero |= X[i][j] == 0;
    }
    if(!zero) val = sum;
  }

  int64 curr = 0;
  for(int i = 0; i < N; i++) {
    curr += X[y][i];
  }

  if(val - curr <= 0) {
    cout << -1 << endl;
    return(0);
  }

  X[y][x] = val - curr;

  for(int i = 0; i < N; i++) {
    sum = 0;
    for(int j = 0; j < N; j++) {
      sum += X[i][j];
    }
    if(sum != val) {
      cout << -1 << endl;
      return(0);
    }
  }

  for(int i = 0; i < N; i++) {
    sum = 0;
    for(int j = 0; j < N; j++) {
      sum += X[j][i];
    }
    if(sum != val) {
      cout << -1 << endl;
      return(0);
    }
  }

  sum = 0;
  for(int i = 0; i < N; i++) {
    sum += X[i][i];
  }
  if(sum != val) {
    cout << -1 << endl;
    return(0);
  }

  sum = 0;
  for(int i = 0; i < N; i++) {
    sum += X[i][N - i - 1];
  }
  if(sum != val) {
    cout << -1 << endl;
    return(0);
  }
  cout << X[y][x] << endl;
}

C. Coloring Trees

問題概要

${1}$ から ${n}$ までの ${n(1 \le n \le 100)}$ 個の木が一列に並んでいる.

${m(1 \le m \le 100)}$ 個の異なる色がある.

木 ${i}$ は色 ${c_i(0 \le c_i \le m)}$ である. ${c_i = 0}$ のとき木 ${i}$ が無着色であることを表し, ${1 \le c_i \le m}$ のとき木 ${i}$ がその色で着色されていることを表す.

無着色の木すべてを着色することを決めた. 木 ${i}$ を色 ${j}$ で着色するとき塗料が ${p_{i,j}}$ 必要である.

木の色の美しさを, 隣接していて同じ色の木をグループとして見るとき, 分かれるグループの個数と定義する.

木の色の美しさを ${k(1 \le k \le 100)}$ にしたいとき, 可能ならその時必要な塗料の量の最小値を求めよ.

解法

動的計画法.

${dp_{i,j,k} :=}$ ${i}$ 番目の木まですべて着色して, その木までで ${j}$ 個のグループに分かれていて, ${i}$ 番目の木を色 ${k}$ で着色したときの最小の塗料の量

と定義する. この時問題の解は ${dp_{n,k,?}}$ のうちの最小値となる.

配るDPを考える. 状態 ${(i,j,k)}$ で, ${i+1}$ 番目の木を ${l}$ で着色する時, ${k \ne l}$ ならグループが ${1}$ つ増えて ${j+1}$ になり, ${k = l}$ ならグループの個数はそのままの ${j}$ .

木 ${i+1}$ が無着色のとき ${l}$ は任意で追加で塗料が ${p_{i+1,l}}$ かかる. 最初から着色されているとき ${l}$ は ${c_{i+1}}$ で塗料は不要.

これで解くことができて計算量はすべて無着色のとき最大となって, ${O(nkm^2)}$ .

ソース

最初, 遷移式を ${1}$ 文字変数を間違えて WA.

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 58;

int64 N, M, K, C[105], P[105][105];
int64 dp[105][105][105];

inline void chmin(int64& x, int64 y)
{
  x = min(x, y);
}

int main()
{
  cin >> N >> M >> K;
  for(int i = 0; i < N; i++) {
    cin >> C[i];
    --C[i];
  }
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {
      cin >> P[i][j];
    }
  }
  fill_n(**dp, 105 * 105 * 105, INF);
  if(C[0] == -1) {
    for(int i = 0; i < M; i++) {
      dp[0][1][i] = P[0][i];
    }
  } else {
    dp[0][1][C[0]] = 0;
  }
  for(int i = 1; i < N; i++) {
    for(int j = K; j >= 0; j--) {
      for(int k = 0; k < M; k++) {
        if(dp[i - 1][j][k] < INF) {
          if(C[i] == -1) {
            for(int l = 0; l < M; l++) {
              if(k == l) chmin(dp[i][j][l], dp[i - 1][j][k] + P[i][l]);
              else chmin(dp[i][j + 1][l], dp[i - 1][j][k] + P[i][l]);
            }
          } else {
            if(C[i] == k) chmin(dp[i][j][C[i]], dp[i - 1][j][k]);
            else chmin(dp[i][j + 1][C[i]], dp[i - 1][j][k]);
          }
        }
      }
    }
  }

  int64 ret = INF;
  for(int i = M - 1; i >= 0; i--) {
    ret = min(ret, dp[N - 1][K][i]);
  }

  if(ret >= INF) cout << -1 << endl;
  else cout << ret << endl;
}

D. Directed Roads

問題概要

頂点数が ${n(2 \le n \le 2 \times 10^5)}$ で各頂点の出次数が ${1}$ の有向グラフがある.

任意の個数の辺を選び, その辺の向きを入れ替えて閉路が含まないグラフ(DAG) にしたい. このような辺の選び方を ${10^9 + 7}$ で割った余りで求めよ.

解法

無向グラフとして考える.

このとき連結成分ごとに選び方は独立なので, 連結成分ごとに分けて考える.

各頂点の出次数は必ず ${1}$ なので, グラフには必ず ${1}$ 個のみの閉路を含む. 辺の向きを入れ替えた時, この閉路が閉路にならなければよい. このような選び方は閉路をなす辺の数(閉路の長さ)を ${k}$ とすると, ${2^k - 2}$ 通りである(時計回りか反時計回りのときが閉路なので ${2}$ だけ引く).

閉路以外の辺はどのような選び方をしてもよいのでこのような辺の個数を ${x}$ とするとき ${2^x}$ 通りである.

これらをすべて掛けあわせたものが答えである.

ソース

最初連結成分は必ず ${1}$ つだと錯覚して WA. あと閉路の長さを求めるやつ毎回ちょっと面倒なのでライブラリ化したい...

#include <bits/stdc++.h>

using namespace std;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x != y) {
      if(data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};


const int MOD = 1000000007;

typedef long long int64;

int64 pow_mod(int64 x, int64 n, int64 mod)
{
  int64 ret = 1LL;
  while(n > 0) {
    if(n & 1) (ret *= x) %= mod;
    (x *= x) %= mod;
    n >>= 1;
  }
  return ret;
}

int N;
vector< pair< int, int > > g[200000];
int v[200000];

int roop(int idx, int rev)
{
  for(int i = 0; i < g[idx].size(); i++) {
    if(g[idx][i].second == rev) {
      continue;
    } else if(v[g[idx][i].first] == -1) {
      v[g[idx][i].first] = v[idx] + 1;
      int val = roop(g[idx][i].first, g[idx][i].second);
      if(val >= 0) return (val);
    } else {
      return (v[idx] - v[g[idx][i].first] + 1);
    }
  }
  return (-1);
}

int main()
{
  memset(v, -1, sizeof(v));

  cin >> N;

  UnionFind uf(N);

  for(int i = 0; i < N; i++) {
    int a;
    cin >> a;
    --a;
    g[a].emplace_back(i, i);
    g[i].emplace_back(a, i);
    uf.unite(a, i);
  }


  int64 ret = 1;

  for(int i = 0; i < N; i++) {
    if(uf.find(i) == i) {
      v[i] = 0;
      int Size = roop(i, -1);
      (ret *= pow_mod(2, uf.size(i) - Size, MOD)) %= MOD;
      (ret *= (pow_mod(2, Size, MOD) - 2 + MOD)) %= MOD;
    }
  }
  cout << ret << endl;
}

ei1333の日記

ぺこい

Codeforces Round #369 (Div. 2)

A. Bus to Udayland

問題概要

解法

ソース

B. Chris and Magic Square

問題概要

解法

ソース

C. Coloring Trees

問題概要

解法

ソース

D. Directed Roads

問題概要

解法

ソース