Codeforces Round #405 (Div. 1)

1完. 2061->2013(-48). 重症. けわしい.

なんか, 頭が良ければキレイに書けるみたいな問題が多かったみたいな印象.

A. Bear and Different Names

問題概要

${n(2 \le n \le 50)}$ 人の兵士が ${1}$ 列に並んでいる.

任意の連続する ${k(2 \le k \le 50)}$ 人について, そのグループ内の兵士の名前がそれぞれ異なるかどうかが分かっている. ${1 \le i \le n - k + 1}$ 番目の ${s_i}$ は ${i}$ から ${i + k - 1}$ までの区間の情報である.

このときに考えられるそれぞれの兵士の名前の一例を出力せよ.

解法

名前だと面倒なので, 値として考える. この値に対応付けた名前を適当に割り当てれば良い.

左から ${1, 2, \dots, n}$ の値をふる.

“YES” は明らかにそのままでよい.
“NO” があった場合は, その区間の右端の値を左端の値に合わせればよい(こうすることで ${1}$ 個区間がずれたときに他に影響しなくなるので(伝わって)).

${O(n)}$ .

ソース

これはすんなり.

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, K;
  cin >> N >> K;

  vector< int > poyo(N);
  int num = 0;
  for(int i = 0; i < K - 1; i++) {
    poyo[i] = num++;
  }
  for(int i = K - 1; i < N; i++) {
    string S;
    cin >> S;
    if(S == "NO") poyo[i] = poyo[i - K + 1];
    else poyo[i] = num++;
  }

  for(int i = 0; i < N; i++) {
    cout << (char)('A' + poyo[i] / 26) << (char)(poyo[i] % 26 + 'a') << " ";
  }
  cout << endl;
}

B. Bear and Tree Jumps

codeforces.com

問題概要

${n(2 \le n \le 200\ 000)}$ 頂点の木が与えられる.

Limak は最大長さ ${k(1 \le k \le 5)}$ をジャンプして他の頂点に移動できる.

${f(s, t)}$ を頂点 ${s, t}$ 間を Limark が移動する際の最小移動回数と定義する.

すべての頂点対 ${(s, t) (s \lt t)}$ を考える. このときの ${f(s, t)}$ の総和を求めよ.

解法

木DP.

任意のパスには物理的(?) に LCA が存在する. 方針としては, すべての頂点を LCA としたときに考えられるパスの移動回数の総和を求めて, それを足し合わせる.

ソースを見たほうが分かりやすいと思うんだけど, 頑張って書くね…

適当な頂点(ここでは頂点 ${1}$ ) をした根付き木として考える.

任意の頂点 ${idx}$ について ${sum(idx, p) := idx}$ の部分木のすべての頂点のうち, ${idx}$ への (距離 ${\mod k}$ ) が ${p}$ となる頂点の個数を求めるのはかんたん.

また, 任意の頂点 ${idx}$ について ${sum(idx, p)}$ に当てはまるすべての頂点から頂点 ${idx}$ へのパスを考える. この全てのパスの移動回数の総和 ${que(idx, p)}$ を求めるのは, ( ${k}$ 周期でこの値が増加することを利用して) ${sum(idx, p)}$ の値を利用しながら気合いをするとできる.

で, 任意の頂点 ${idx}$ を LCA にしたときの移動回数の総和を, 子の頂点 ${c_i}$ とマージしながら求める.

${sum(c_i, j)}$ が利用される回数は, 頂点 ${idx}$ の部分木で ${c_i}$ の部分木の頂点を取り除いた頂点の個数. また, LCA でつなぎ合わせる際に mod の値に応じて微妙に増えるので, 適宜 ${sum(c_i, j) \times }$ 頂点 ${idx}$ の部分木で ${c_i}$ の部分木の頂点を取り除いた頂点の個数を足したりしながらなんとかする.

ソース

なんか考察が甘くて無限にバグをして, ごにょごにょしていたら知らない間にコンテストが終了していた. 冷静になればそれはそうという気がする. 大体方針は合っていたんだけど, 悲しいね.

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int N, K;
vector< int > g[200000];
int64 sum[200000][5];
int64 que[200000][5];

int64 dfs(int idx, int par = -1)
{
  int64 ret = 0;
  sum[idx][0]++;
  for(auto &to : g[idx]) {
    if(par == to) continue;
    ret += dfs(to, idx);
    for(int j = 0; j < K; j++) {
      for(int k = 0; k < K; k++) {
        ret += que[to][j] * sum[idx][k];
        ret += sum[to][j] * que[idx][k];
        if(j + k >= K) ret += sum[idx][k] * sum[to][j];
        ret += sum[idx][k] * sum[to][j];
      }
    }
    for(int j = 0; j < K; j++) {
      sum[idx][(j + 1) % K] += sum[to][j];
      que[idx][(j + 1) % K] += que[to][j] + (j == K - 1 ? sum[to][j] : 0);
    }
  }
  return (ret);
}

int main()
{
  cin >> N >> K;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    g[--a].push_back(--b);
    g[b].push_back(a);
  }
  cout << dfs(0) << endl;
}

C. Bear and Company

codeforces.com

問題概要

長さ ${n(1 \le n \le 75)}$ の文字列 ${s}$ が与えられる.

何回か swap することにより部分文字列に “VK” が現れないようにしたい.

swap の最小回数を求めよ.

解法

“V”, “K”, それ以外の文字に分類できるのはそう. またそれぞれの文字について, 同じ文字との間では swap を変えても意味がないことがわかるので, 順番で使っていけば良さそうだなぁという方針がたつ.

よって, “V” から “K” への遷移を防ぐためのフラグ, それぞれの文字で使った文字数を持ってDPができる.

最後に問題となるのが遷移時のコストである. 以下の文字列を考える.

VVKXXVKVV

ここで ‘V’ を 4 文字 ‘K’ を 1 文字その他を 1 文字使ったとする. すると以下のような感じになる.

####X##K#V (使った文字を '#' で表す)

ここで例えば次に ‘K’ を使うこととする.

このとき ‘X’ を右側に持ってくる必要があるので追加で ${1}$ 回の swap が必要である.

要するに自分の文字より左側でまだ使っていない文字の個数分が追加の swap の回数となる.

これをそれぞれの遷移時に数え上げればいいので, 全体で ${O(n^4)}$ となる.

ソース

頭がいいDPだなぁ.

#include <bits/stdc++.h>

using namespace std;

void chmin(int &a, int b)
{
  a = min(a, b);
}

const int INF = 1 << 30;
string S;
int dp[78][78][78][2];

int main()
{
  int N;
  cin >> N;
  cin >> S;

  vector< int > a, b, c;
  for(int i = 0; i < N; i++) {
    if(S[i] == 'V') a.push_back(i);
    else if(S[i] == 'K') b.push_back(i);
    else c.push_back(i);
  }


  fill_n(***dp, 78 * 78 * 78 * 2, INF);
  dp[0][0][0][0] = 0;
  for(int i = 0; i <= a.size(); i++) {
    for(int j = 0; j <= b.size(); j++) {
      for(int k = 0; k <= c.size(); k++) {
        for(int l = 0; l < 2; l++) {
          if(dp[i][j][k][l] == INF) continue;

          auto f = [&](int x)
          {
            int latte = 0;
            for(int p = i; p < a.size(); p++) if(a[p] < x) ++latte;
            for(int p = j; p < b.size(); p++) if(b[p] < x) ++latte;
            for(int p = k; p < c.size(); p++) if(c[p] < x) ++latte;
            return (latte);
          };

          if(i < a.size()) chmin(dp[i + 1][j][k][1], dp[i][j][k][l] + f(a[i]));
          if(j < b.size() && l == 0) chmin(dp[i][j + 1][k][0], dp[i][j][k][l] + f(b[j]));
          if(k < c.size()) chmin(dp[i][j][k + 1][0], dp[i][j][k][l] + f(c[k]));
        }
      }
    }
  }
  cout << min(dp[a.size()][b.size()][c.size()][0], dp[a.size()][b.size()][c.size()][1]) << endl;
}

ei1333の日記

ぺこい

Codeforces Round #405 (Div. 1)

A. Bear and Different Names

問題概要

解法

ソース

B. Bear and Tree Jumps

問題概要

解法

ソース

C. Bear and Company

問題概要

解法

ソース