Codeforces Round #438 (Div. 1 + Div. 2 combined)

goodbye orange><

ABCD 出して BD 落ちたねかなしいね

強い意志を持って復習するぞ

A. Bark to Unlock

codeforces.com

問題概要

携帯のパスワードを示す ${2}$ 文字からなる文字列が与えられる.

また ${n}$ 個の ${2}$ 文字からなる文字列が与えられる. これらの文字列を組み合わせて, パスワードが部分文字列に含ませることができるか判定せよ.

解法

問題を読む.

実装によってはバグを埋まるので, 安全な実装をこころがける.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  string S, T[100];

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

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      string Q = T[i] + T[j];
      if(Q.find(S) != string::npos) {
        cout << "YES" << endl;
        return (0);
      }
    }
  }

  cout << "NO" << endl;
}

B. Race Against Time

codeforces.com

問題概要

アナログ時計があって現在 ${h(1 \le h \le 12)}$ 時 ${m(0 \le m \le 59)}$ 分 ${s(0 \le s \le 59)}$ 秒を指している.

針をまたがずに時計の円周上のみをとおって ${t_1}$ 時の位置から ${t_2(1 \le t_1, t_2 \le 12, t_1 \ne t_2)}$ 時の位置に移動できるか判定せよ.

解法

虚無. 実装によってはバグが埋まるので, 安全な実装をこころがける2. ←おいおいおい落としてるやんけ悲しいね橙コーダじゃなくなるね

時針と分針と秒針, ${t_1}$ , ${t_2}$ の角度を求めて, 適当に 360 を足したり引いたりしながら針をまたがずにいけるかどうか判定する.

ソース

あーーー

#include <bits/stdc++.h>

using namespace std;

int main()
{
  double H, M, S, T1, T2;

  cin >> H >> M >> S >> T1 >> T2;


  T1 *= 30;
  T2 *= 30;
  T1 += 360 * 2;
  T2 += 360 * 2;
  
  vector< double > cut;
  for(int i = 0; i <= 360 * 5; i += 360) {
    cut.push_back((H * 3600 + M * 60 + S) * 360 / 12 / 60 / 60 + i);
    cut.push_back((M * 60 + S) * 360 / 60 / 60 + i);
    cut.push_back(S * 6 + i);
  }
  
  sort(begin(cut), end(cut));
  for(int i = 1; i < cut.size(); i++) {
    if(cut[i - 1] <= T1 && T1 <= cut[i] && cut[i - 1] <= T2 && T2 <= cut[i]) {
      cout << "YES" << endl;
      return (0);
    }
    if(cut[i - 1] <= T1 - 360 && T1 - 360 <= cut[i] && cut[i - 1] <= T2 && T2 <= cut[i]) {
      cout << "YES" << endl;
      return (0);
    }

    if(cut[i - 1] <= T1 + 360 && T1 + 360 <= cut[i] && cut[i - 1] <= T2 && T2 <= cut[i]) {
      cout << "YES" << endl;
      return (0);
    }
  }

  cout << "NO" << endl;
}

C. Qualification Rounds

codeforces.com

問題概要

${n(1 \le n \le 10^5)}$ 個の問題と ${k(1 \le k \le 4)}$ 人がいて, ${i}$ 番目の問題を ${j}$ 番目の人が知っているかどうかの情報が与えられる.

いくつかの問題を取り出して, ${k}$ 人それぞれの人に対して, 知っている問題が半分以下にできるか判定せよ.

解法

C問題なのでどうせ ${1, 2}$ 問取り出すのが最適だろうと推測する.

まず ${1}$ 問だけで済む場合は, すべての人が知らない問題が存在する場合である.

${2}$ 問で済む場合を確かめるためには全探索をする. 同じ知っている問題の組み合わせ同士はまとめられるため ${O((2^k)^2)}$ で確かめることが出来る.

ソース

なんか証明が難しい問題多くないですか? 多いですね(雰囲気で競プロをしている勢としてはけわしい

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, K;
  int bit[1 << 4] = {};

  cin >> N >> K;
  for(int i = 0; i < N; i++) {
    int s = 0;
    for(int j = 0; j < K; j++) {
      int p;
      cin >> p;
      s |= p << j;
    }
    bit[s]++;
  }

  if(bit[0] > 0) {
    cout << "YES" << endl;
    return(0);
  }

  for(int i = 0; i < (1 << K); i++) {
    if(bit[i] == 0) continue;
    bit[i]--;
    for(int j = 0; j < (1 << K); j++) {
      if(bit[j] == 0) continue;
      bit[j]--;

      bool flag = false;
      for(int k = 0; k < 4; k++) {
        if((i >> k) & 1 && (j >> k) & 1) flag = true;
      }

      if(!flag) {
        cout << "YES" << endl;
        return(0);
      }
      bit[j]++;
    }
    bit[i]++;
  }

  cout << "NO" << endl;
}

D. Huge Strings

codeforces.com

問題概要

${n(1 \le n \le 100)}$ 個の '0', '1' からなる文字列 ${s_i}$ が与えられる. ${s_i}$ の長さの和は ${100}$ を超えない.

${m(1 \le m \le 100)}$ 回の操作を行う. ${i}$ 回目の操作は次の通りである.

${s_{a_i}}$ と ${s_{b_i}}$ を連結して, 新たな文字列 ${s_{n + i}}$ を生成する.

それぞれの操作で生成された文字列に対し, 長さ ${k}$ の '0', '1' からなる ${2^k}$ 通りのすべての文字列が部分文字列に含まれているというような, 最大の ${k}$ を求めよ.

解法

${k}$ の上界をエスパー. 計算量を意識して ${k \le 13}$ くらいと仮定する.

連結によって部分文字列の種類が増えるのはそうだが ${k \le 13}$ なので, 新たに作られる部分文字列について長さが ${13}$ 以下のものしか解に影響しない. つまり ${s_{a_i}}$ と ${s_{b_i}}$ の前後 ${12}$ 文字を持っておけば良い.

あとは今までの部分文字列の出現の情報を伝搬しつつ ${k}$ を求めるのを愚直にやるとアになる.

ソース

${k}$ の上界が小さいのは察していたのに何で解けなかったんだろう.

#include <bits/stdc++.h>

using namespace std;

const int lim = 13;

int calc(const string &s, set< pair< int, int > > &vs)
{
  int ans = 0;
  for(int k = lim; k >= 1; k--) {
    int found = true;
    for(int i = 0; i < (1 << k); i++) {
      if(vs.count({k, i})) continue;
      string f;
      for(int j = 0; j < k; j++) f += "01"[(i >> j) & 1];
      if(s.find(f) == string::npos) found = false;
      else vs.emplace(k, i);
    }
    if(!found) ans = k - 1;
  }
  return (ans);
}

int main()
{
  int N, M;
  string S[200];
  int pre[200] = {};
  set< pair< int, int > > found[200];

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> S[i];
  }
  cin >> M;
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    S[i + N] = S[--a] + S[--b];
    for(auto &p : found[a]) found[i + N].emplace(p);
    for(auto &p : found[b]) found[i + N].emplace(p);
    pre[i + N] = max({pre[a], pre[b], calc(S[i + N], found[i + N])});
    cout << pre[i + N] << endl;
    if(S[i + N].size() > 24) {
      S[i + N] = S[i + N].substr(0, 12) + "#" + S[i + N].substr(S[i + N].size() - 12);
    }
  }
}

F. Yet Another Minimization Problem

codeforces.com

問題概要

長さ ${n(2 \le n \le 10^5)}$ の数列 ${a_i(1 \le a_i \le n)}$ が与えられる.

連続部分列のコストを, 数列内で等しい値が書かれた要素のペアの数と定義する.

与えられた数列を互いに素で非空な ${k(2 \le k \le \min(n, 20))}$ 個の連続部分列に分割するとき, 部分列のコストの総和の最小値を求めよ.

解法

なんかこういう問題, 特殊な解き方があったなあってずっと思ってたけどそれが何かわからなかった...

動的計画法を加速するテクのひとつである Divide-and-Conquer-Optimization を使う. コスト ${C[k][j]}$ について, Monge(任意の ${a \lt b \lt c \lt d}$ に対して ${C[a][c] + C[b][d] \le C[a][d] + C[b][c]}$ ) かつ Monotonicity(単調性, 任意の ${a \lt b \lt c \lt d}$ に対して ${C[b][c] \le C[a][d]}$ ) のときに適用できる.

加速する漸化式は以下のように定義される.

$dp[i][j] = \min_{0 \le k \lt j} \{dp[i - 1][k] + C[k][j]\}$

今回の問題は ${dp[i][j] := }$ 区間 ${[0, j)}$ を ${i}$ 個の区間に分割した時のコストの和の最小値, ${C[i][j]\ :=}$ 区間 ${[i, j)}$ に分けたときのコストとすれば, 全く同じ漸化式となる.

コスト ${C[i][j]}$ に対して Monge と Monotonicity を示しておく必要がある. Monotonicity は自明. 実は Monge についても成立する. ${3}$ つの区間 ${X = [a, b)}$ , ${Y = [b, c)}$ , ${Z = [c, d)}$ に分けてみる. コストの寄与を考えると, 前者の式 ${C[a][c] + C[b][d]}$ は ${XX + XY + YY + YY + YZ + ZZ}$ で後者の式 ${C[a][d] + C[b][c]}$ は ${XX + XY + XZ + YY + YZ + ZZ + YY}$ . 後者のほうが ${XZ}$ だけ多いため不等式が成り立つことが分かる.

この漸化式を単純なDPを行って解くと計算量が ${O(m n^2)}$ かかる。しかしながらここで ${A[i][j] := dp[i][j]}$ を最小とする ${k}$ とおくと, 任意の ${p}$ に対し ${A[i][p] \le A[i][p + 1]}$ をみたす(これが本質ですが, 証明がアでそこまで踏み込む必要がなさそうなのでそういうものだと思うこととする). これを利用すると計算量を ${O(mn \log n)}$ に落とすことができる. ${m}$ 通りの ${i}$ に対して ${O(n \log n)}$ を行うイメージ. ある ${i}$ について, 任意の ${j}$ に対して解を求めたいとする。最初に ${O(n)}$ かけて ${dp[i][\frac n 2]}$ を求めると, そのときの ${A[i][\frac n 2]}$ を用いて ${dp[0, \frac n 2), dp[\frac n 2 + 1, n)}$ のそれぞれの区間において, 探索すべき範囲が定まる. これを再帰的に行う. よくある分割統治みたいな感じになっていて, 計算量は ${O(n \log n)}$ である.

あとコストは尺取りで求めるとよい.

ソース

#include <bits/stdc++.h>

using namespace std;

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

int N, K, A[100000];
int64 dp[21][100001];

int L, R;
int64 sum, appear[100000];

inline void add(int idx)
{
  sum += appear[A[idx]]++;
}

inline void del(int idx)
{
  sum -= --appear[A[idx]];
}

inline int64 getcost(int l, int r)
{
  while(L > l) add(--L);
  while(R < r) add(R++);
  while(L < l) del(L++);
  while(R > r) del(--R);
  return (sum);
}

inline void rec(int idx, int left, int right, int latte, int malta)
{
  if(left >= right) return;
  int mid = (left + right) >> 1;
  dp[idx][mid] = INF;
  int best = -1;
  for(int k = latte; k < min(mid, malta); k++) {
    int64 cost = dp[idx - 1][k] + getcost(k, mid); // cost[k, mid)
    if(cost < dp[idx][mid]) {
      dp[idx][mid] = cost;
      best = k;
    }
  }
  rec(idx, left, mid, latte, best + 1);
  rec(idx, mid + 1, right, best, malta);
}

int main()
{
  scanf("%d %d", &N, &K);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    --A[i];
  }
  fill_n(*dp, 21 * 10001, INF);
  dp[0][0] = 0;
  for(int i = 1; i <= K; i++) rec(i, 0, N + 1, 0, N + 1);
  printf("%lld\n", dp[K][N]);
}

ei1333の日記

ぺこい

Codeforces Round #438 (Div. 1 + Div. 2 combined)

A. Bark to Unlock

問題概要

解法

ソース

B. Race Against Time

問題概要

解法

ソース

C. Qualification Rounds

問題概要

解法

ソース

D. Huge Strings

問題概要

解法

ソース

F. Yet Another Minimization Problem

問題概要

解法

ソース