読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

数式を $$ で囲んで書いてますが面倒くさいので、いちいち、はてな書式にしたりしません

Codeforces Round #316 (Div. 2)

プロコン

2015年 8月 14日 金曜日 03:57:09 JST

Codeforces Round #316 (Div. 2)

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

1559 -> 1667

A.

正しく数えるだけ.

B.

[1,m) と (m,n] とに分けて可能性が大きく残ってる方に賭ける. 可能性が同じときは、インデックスが小さい方 (i.e. [1,m) ) を使う. 具体的には、m-1m+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> とした.

  • aa へ変更する場合: 文字列は何も変わらない
  • .. へ変更する場合: 文字列は何も変わらない

  • a. へ変更する場合: . のグループが生まれるか伸びるか連結される. いずれになるかは結局、その両隣を見ればよい

    • a(n) a a(m)a(n) . a(m) に変更する場合 (アルファベットが$n$個並んでるものを a(n) と表記した): . のグループは新しく生まれる. ただしその長さは $1$ なので、$f(s)$ は変わらない
    • a(n) a .(m)a(n) . .(m) に変更する場合: 既に存在する. のグループの長さが$1$伸びるだけだから $f(s)$ は$1$ 増える
    • .(n) a a(m).(n) . a(m) に変更する場合: 上と同じ
    • .(n) a .(m).(n) . .(m) に変更する場合: $f(s) = C + (n-1) + (m-1)$ であったのが、 $f(s) = C + (n+1+m - 1)$ になるから、実は $2$ 増えるだけ
  • .a へ変更する場合: 先ほどの逆 (増えるのが減る) になるだけ!

のように、文字置換する前の $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;
  }