Codeforces Round #390 (Div. 2)

BCDを解いて3完. A はおちました！！

1887 -> 2012(+125).

A. Lesha and array splitting

問題概要

長さ ${n(1 \le n \le 100)}$ の配列 ${A_i(-10^3 \le A_i \le 10^3)}$ がある.

この配列を順番を保ちながら, 要素の和が ${0}$ にならないような配列に分割せよ.

解法

まず, ${\sum_{ i = 1 }^{ n } A_i}$ が非 ${0}$ のとき, ${A_i}$ そのもので OK なので ${0}$ のときを考える.

全ての ${A_i}$ が ${0}$ のときは分割できない.

それ以外のときは, 必ず ${2}$ つの配列に分割できることを示せる. 左から見ていって最初に見つけた非 ${0}$ の ${A_r}$ を ${1}$ つ目の配列の右端とすれば, この配列の合計は ${A_r}$ . ${A_{r+1}}$ 　以降を ${2}$ つ目の配列とすれば, ${A_r + \sum_{ i = r + 1 }^{ n } A_i} = 0$ より非 ${0}$ である.

ソース

初心者なので, i と j の添字を間違えて落とした.

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, A[100];

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }

  int sum = accumulate(A, A + N, 0);

  if(sum != 0) {
    cout << "YES" << endl;
    cout << 1 << endl;
    cout << 1 << " " << N << endl;
    return(0);
  }

  for(int i = 1; i < N; i++) {
    int a = 0, b = 0;
    for(int j = 0; j < i; j++) a += A[j];
    for(int j = i; j < N; j++) b += A[j];
    if(a != 0 && b != 0) {
      cout << "YES" << endl;
      cout << 2 << endl;
      cout << 1 << " " << i << endl;
      cout << i + 1 << " " << N << endl;
      return(0);
    }
  }

  cout << "NO" << endl;
}

B. Ilya and tic-tac-toe game

問題概要

${4 \times 4}$ の ${3}$ 目並べの途中盤面が与えられる.

この状態で ${'x'}$ が ${1}$ 手勝ちできるか判定せよ.

解法

${4 \times 4}$ の空のマスそれぞれに ${'x'}$ を置いてみて, 勝てたか見る.

ソース

#include <bits/stdc++.h>

using namespace std;

const int vy[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int vx[] = {-1, 0, 1, 1, 1, 0, -1, -1};

string S[4];


bool is(int x, int y)
{
  if(x < 0 || y < 0 || x >= 4 || y >= 4) return(false);
  return(S[y][x] == 'x');
}

bool isEnd()
{
  for(int i = 0; i < 4; i++) {
    for(int j = 0; j < 4; j++) {
      for(int k = 0; k < 8; k++) {
        if(is(j, i) && is(j + vx[k], i + vy[k]) && is(j + vx[k] + vx[k], i + vy[k] + vy[k])) return(true);
      }
    }
  }
  return(false);
}

int main()
{
  for(int i = 0; i < 4; i++) {
    cin >> S[i];
  }
  for(int i = 0; i < 4; i++) {
    for(int j = 0; j < 4; j++) {
      if(S[i][j] == '.') {
        S[i][j] = 'x';
        if(isEnd()) {
          cout << "YES" << endl;
          return(0);
        }
        S[i][j] = '.';
      }
    }
  }
  cout << "NO" << endl;
}

C. Vladik and chat

問題概要

${n(1 \le n \le 100)}$ 人のチャットのユーザの名前と, ${m(1 \le m \le 100)}$ 行のチャットの会話履歴が与えられる. 会話履歴は "発言者の名前:テキスト" の形式を満たす.

ここで, いくつかの行の発言者の名前がわからなくなってしまったので, 以下の条件を満たす履歴となるように復元せよ.

隣接する行の発言者は異なる.
テキストの単語に, そのテキストの発言者の名前は含まれない.

解法

直前の発言者の名前と現在の行を持っておけば ${O(n^2 m)}$ のDPができる. これを経路復元すればよい.

ソース

なんかかなり無駄な実装になってしまった. split が欲しい.

#include <bits/stdc++.h>

using namespace std;

const string tt = ".,!? ";

bool solve()
{
  int N, M;
  cin >> N;
  vector< string > S(N);
  for(int i = 0; i < N; i++) cin >> S[i];
  cin >> M;
  cin.ignore();

  vector< pair< int, vector< int > > > vc;
  vector< string > kk(M);

  for(int i = 0; i < M; i++) {
    string K;
    getline(cin, K);
    kk[i] = K;

    int idx = 0;
    string name;
    vector< int > word;
    while(idx < K.size() && K[idx] != ':') name += K[idx++];
    ++idx;

    string pico;
    while(idx < K.size()) {
      if(tt.find(K[idx]) != string::npos) {
        idx++;
        if(pico.size()) {
          if(find(begin(S), end(S), pico) != end(S)) {
            word.push_back((int) (find(begin(S), end(S), pico) - begin(S)));
          }
          pico = "";
        }
        continue;
      }
      pico += K[idx++];
    }
    if(pico.size()) {
      if(find(begin(S), end(S), pico) != end(S)) {
        word.push_back((int) (find(begin(S), end(S), pico) - begin(S)));
      }
    }
    if(find(begin(S), end(S), name) == end(S)) {
      if(name != "?") return (false);
    }
    vc.emplace_back((int) (find(begin(S), end(S), name) - begin(S)), word);
  }

  vector< vector< int > > koho;

  for(int i = 0; i < M; i++) {
    int namepos = vc[i].first;
    vector< int > cann;
    if(namepos == N) { // question
      for(int j = 0; j < N; j++) {
        int proc = 0;
        for(int k : vc[i].second) proc += j == k;
        if(proc == 0) cann.push_back(j);
      }
    } else {
      for(int k : vc[i].second) if(namepos == k) return(false);
      cann.push_back(vc[i].first);
    }
    if(cann.empty()) return (false);
    koho.push_back(cann);
  }


  vector< vector< int > > dp(M, vector< int >(N, 0));
  vector< vector< int > > pv(M, vector< int >(N, -1));
  for(auto &k : koho[0]) dp[0][k] = true;
  for(int i = 1; i < M; i++) {
    for(int j : koho[i]) {
      for(int k = 0; k < N; k++) {
        if(j == k) continue;
        if(!dp[i - 1][k]) continue;
        dp[i][j] = true;
        pv[i][j] = k;
        break;
      }
    }
  }

  int cnt = -1;
  for(int j = 0; j < N; j++) if(dp[M - 1][j]) cnt = j;

  if(cnt == -1) return(false);

  vector< string > people;


  people.push_back(S[cnt]);
  for(int j = M - 2; j >= 0; j--) {
    cnt = pv[j + 1][cnt];
    people.push_back(S[cnt]);

  }

  reverse(begin(people), end(people));

  for(int i = 0; i < M; i++) {
    cout << people[i] << ":";
    string K = kk[i];
    int idx = 0;
    vector< int > word;
    while(idx < K.size() && K[idx] != ':') ++idx;
    ++idx;
    cout << K.substr(idx) << endl;
  }
  return (true);
}


int main()
{
  int T;
  cin >> T;
  while(T--) {
    if(!solve()) cout << "Impossible" << endl;
  }
}

D. Fedor and coupons

問題概要

${n(1 \le n \le 3 \times 10^5)}$ 個の区間 ${[l_i, r_i] (-10^9 \le l_i \le r_i \le 10^9)}$ が与えられる.

このうち, ちょうど ${k(k \le n)}$ 個の区間を選ぶ. このとき共通区間の長さが最大となる選び方の一例を出力せよ.

解法

二分探索 + BIT.

共通区間の長さは二分探索できるので, 共通区間の長さが ${x}$ になるような選び方があるか判定できれば良い.

この区間の候補は ${[r_i - x + 1, r_i]}$ のいずれかとしてもよい. よってこの候補を左の方から順番に走査していって, えいってやるとできそう(解説の放棄

BIT を用意しておく. 左から候補を探っていって, 現在候補 ${[x, y]}$ を見ているとする. ${r_i \lt y}$ を満たす候補は尺取りっぽい手法で BIT から除外しておく. ${x}$ 以下の ${l_i}$ の個数を知ればよくて, ここに BIT を使って ${k}$ 個以上か確かめれば良い.

${O(n \log^2 n)}$ . ${n \le 3 \times 10^5}$ で log の 2 乗は結構怖いよ

ソース

こういう問題安心するよねー.

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

struct BinaryIndexedTree
{
  vector< int > data;

  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }

  int sum(int k)
  {
    int ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, int x)
  {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};

int64 N, K, L[300000], R[300000];
vector< int64 > nums;
vector< int64 > curr;
vector< int > rr;


void output(int64 length)
{
  int eix = 0, lbx = -1;
  BinaryIndexedTree bit1(nums.size() + 1);

  for(int i = 0; i < N; i++) bit1.add(L[i], +1);

  for(int64 start : curr) {
    int64 sub = start - length + 1;
    while(eix < rr.size() && R[rr[eix]] < start) {
      bit1.add(L[rr[eix++]], -1);
    }
    while(lbx + 1 < nums.size() && nums[lbx + 1] <= sub)
      lbx++;

    if(bit1.sum(lbx) >= K) {
      for(int i = 0; i < N; i++) {
        if(K > 0 && nums[L[i]] <= sub && start <= R[i]) {
          --K;
          cout << i + 1 << " ";
        }
      }
      cout << endl;
      return;
    }
  }
}

bool calc(int64 length)
{
  int eix = 0, lbx = -1;
  BinaryIndexedTree bit1(nums.size() + 1);
  for(int i = 0; i < N; i++) bit1.add(L[i], +1);
  for(int64 start : curr) {
    int64 sub = start - length + 1;
    while(eix < rr.size() && R[rr[eix]] < start) {
      bit1.add(L[rr[eix++]], -1);
    }
    while(lbx + 1 < nums.size() && nums[lbx + 1] <= sub)
      lbx++;
    if(bit1.sum(lbx) >= K) return(true);
  }
  return (false);
}


int main()
{
  scanf("%lld %lld", &N, &K);
  for(int i = 0; i < N; i++) {
    scanf("%lld %lld", &L[i], &R[i]);
    nums.push_back(L[i]);
    curr.push_back(R[i]);
  }

  sort(begin(nums), end(nums));
  nums.erase(unique(begin(nums), end(nums)), end(nums));

  rr.resize(N);
  iota(begin(rr), end(rr), 0);
  sort(begin(rr), end(rr), [&](int &x, int &y)
  {
    return (R[x] < R[y]);
  });
  for(int i = 0; i < N; i++) {
    L[i] = lower_bound(begin(nums), end(nums), L[i]) - begin(nums);
  }
  
  sort(begin(curr), end(curr));
  curr.erase(unique(begin(curr), end(curr)), end(curr));


  if(!calc(1)) {
    cout << 0 << endl;
    for(int i = 0; i < K; i++) {
      cout << i + 1 << " ";
    }
    cout << endl;
    return(0);
  }


  int64 low = 0, high = 1LL << 33;
  while(high - low > 0) {
    int64 mid = (low + high + 1) >> 1;
    if(calc(mid)) low = mid;
    else high = mid - 1;
  }

  printf("%lld\n", low);
  output(low);

}

ei1333の日記

ぺこい

Codeforces Round #390 (Div. 2)

A. Lesha and array splitting

問題概要

解法

ソース

B. Ilya and tic-tac-toe game

問題概要

解法

ソース

C. Vladik and chat

問題概要

解法

ソース

D. Fedor and coupons

問題概要

解法

ソース