🔙 Back to Top

Fri Aug 14 03:57:09 JST 2015

Codeforces Round #316 (Div. 2)

Div.1 が開催されてなかったので、強者もこちらに参戦していた. 自分は、ABCの3問が解けて3完. 部屋一位であった. どちらとも初めてなので嬉しい.

1559 -> 1667

A.

正しく数えるだけ.

B.

\([1, m)\) と \((m, n]\) に分けて可能性が大きく残ってる方に賭ける. 可能性が同じときは、インデックスが小さい方 (i.e. \([1,m)\)) を使う. 具体的には、\(m-1\) か \(m+1\) のどちらかを出力すればよい. 簡単なコーナーケースとして、\(n=1\) のときは仕方がないので \(1\) を出力するしかない.

C.

文字列は単に . のゾーンと、そうでないアルファベット a のゾーンとにグルーピングして、その長さだけ管理しておけばよい.

.b..bz....
=> [ (. 1) (a 1) (. 2) (a 2) (. 4) ]

\(f(s)\) の計算は、つまるところ、. のグループだけを見て、 長さ\(-1\) の和を取ればよい.

f([ (. 1) (a 1) (. 2) (a 2) (. 4) ]) = (1 - 1) + (2 - 1) + (4 - 1)

文字の置換 (. または a を . または a へ変更する) は、グループのリストを上手く変更しなければならない. そのようなデータ構造を知らず、また、Div2のC問題なので、簡単にできるだろうと予測した. グループのリストを表現するようなデータ構造はやめる. 考え方としては使うけど、 直接的に扱うデータ構造は、元の文字列そのものとする. std::string は何文字目を変更するっていうのが出来ないはずなので std::vector<char> に変換する. しかも文字は '.' であるかだけを気にすれば良いので std::vector<bool> とした.

のように、文字置換する前の \(f(s)\) から、置換後の \(f(s)\) は計算できる

A

  int n; cin >> n;
  int m; cin >> m;

  vi xs(n, 0);
  rep (i, m) {
    vi ys(n, 0); cin >> ys;
    int mx = *max_element(begin(ys), end(ys));
    rep (j, n) {
      if (ys[j] == mx) {
        xs[j]++;
        break;
      }
    }
  }
  {
    int mx = *max_element(begin(xs), end(xs));
    int ans = -1;
    rep (j, n) {
      if (xs[j] == mx) {
        ans = j;
        break;
      }
    }
    cout << ans+1 << endl;
  }

B

  int n; cin >> n;
  int m; cin >> m;

  if (n == 1) {
    cout << 1 << endl;
  }
  else {

    if (m-1 < n-m) {
      cout << m + 1 << endl;
    }else {
      cout << m - 1 << endl;
    }

  }

C

  int n; cin >> n;
  int m; cin >> m;

  vector<bool> cs; // 文字列の表現
  vector<int> dots; // dot のグループの長さの列
  {
    string s; cin >> s;
    cs.push_back(false);
    for (char c: s) cs.push_back(c == '.');
    cs.push_back(false);
    int i = 0;
    while (i < n) {
      while (i < n and s[i] != '.') ++i;
      int k = 0;
      while (i < n and s[i] == '.') { ++k; ++i; }
      dots.push_back(k);
    }
  }
  // trace(cs);
  // trace(dots);

  // 初めの文字列 s の f(s)
  int ans = 0;
  for (int d: dots) ans += max(0, d-1);

  rep (_, m) {
    int pos; char c; cin >> pos >> c;
    bool b = c == '.';

    if (cs[pos] != b) {
      if (b) { // dot
        if (cs[pos-1] and cs[pos+1]) { // 両辺 dot
          ans += 2;
        }
        else if ((not cs[pos-1]) and (not cs[pos+1])) { // 両辺 a
          ans += 0;
        }
        else { // 片側 dot
          ans += 1;
        }
      }
      else {
        if (cs[pos-1] and cs[pos+1]) {
          ans -= 2;
        }
        else if ((not cs[pos-1]) and (not cs[pos+1])) {
          ans -= 0;
        }
        else {
          ans -= 1;
        }
      }
    }

    cout << ans << endl;
    cs[pos] = b;
  }