Codeforces Round #399 (Div. 1 + Div. 2, combined)

ここ最近で一番悔しいことをした….つらい

2068->2087(+19).

A. Oath of the Night’s Watch

codeforces.com

問題概要

${n(1 \le n \le 10^5)}$ 人の執事がいて, それぞれの強さは ${a_i(1 \le a_i \le 10^9)}$ である.

各執事について, 支援するしないを以下の ${2}$ つの条件を共に満たすか満たさないかで決定する時, 何人支援することとなるか.

自分より強い執事が ${1}$ 人以上いる.
自分より弱い執事が ${1}$ 人以上いる.

解法

最小値と最大値をもつ執事以外は支援することとなる.

これを数えるだけ.

ソース

#include<bits/stdc++.h>

using namespace std;

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

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

  int big = *max_element(A, A + N);
  int small = *min_element(A, A + N);
  int ret = 0;
  for(int i = 0; i < N; i++) {
    if(A[i] != big && A[i] != small) ++ret;
  }
  cout << ret << endl;
}

B. Code For 1

codeforces.com

問題概要

配列があって, 最初は ${1}$ つの要素 ${n(0 \le n \lt 2^{50})}$ からなる. この配列に対して, ${1}$ より大きい要素 ${x}$ が存在する間, その ${x}$ を取り出して同じ位置に ${3}$ つの要素 ${\lfloor x/2 \rfloor, x\mod 2, \lfloor x/2 \rfloor}$ を挿入する操作を繰り返す.

最終的な数列について, 要素 ${l}$ から ${r(0 \le r - l \le 10^5, l \ge 1, r \ge 1)}$ の範囲に ${1}$ が何個あるか求めよ.

解法

まず, ${0 \le r - l \le 10^5}$ より, その条件を使ってほしそうな気がすることがわかる.

操作で出てくる値は ${O(\log n)}$ 個なので, その値が出てきた時に最終的に要素の個数が何個になるかを前計算で求めておく.

${l \le i \le r}$ を満たす各 ${i}$ について, ${i}$ 番目の要素が何かどうかは, 前計算した値を見ながら木を下る操作をすると ${O(\log n)}$ で求めることができる.

全体で ${O(n \log n)}$ なので間に合う.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

map< int64, int64 > sz;

int64 calc(int64 x)
{
  if(sz.count(x)) return(sz[x]);
  if(x <= 1) return(1);
  return(sz[x] = calc(x / 2) + 1 + calc(x / 2));
}

int main()
{
  int64 n, l, r;
  cin >> n >> l >> r;

  int ret = 0;
  for(int64 i = l; i <= r; i++) {
    int64 now = n;
    int64 pos = i;
    while(now >= 2) {
      int64 sz = calc(now/2);
      if(pos <= sz) now /= 2;
      else if(pos == sz + 1) now = now % 2;
      else now /= 2, pos -= sz + 1;
    }
    ret += now;
  }

  cout << ret << endl;
}

C. Jon Snow and his Favourite Number

codeforces.com

問題概要

長さ ${n(1 \le n \le 10^5)}$ の数列 ${a_i(0 \le a_i \le 10^3)}$ がある. この数列に対して以下の操作を ${k(0 \le k \le 10^5)}$ 回行った時, 最終的な数列の最大値と最小値を求めよ.

数列を昇順にソートする
奇数番目の要素 ${a_j}$ すべてに対して ${a_j}$ と値 ${x(0 \le x \le 10^3)}$ を XOR をした要素に更新する.

解法

操作の中で出てくる要素の値の範囲は ${0}$ 以上 ${1023}$ 以下.

これを考えると ${k \times 1024}$ 回のループを回すシミュレーションが出来る.

最近の計算機は速いので ${10^8}$ くらいはまわる.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int n, k, x;
  int dp[2][1024] = {{}};

  scanf("%d %d %d", &n, &k, &x);
  for(int i = 0; i < n; i++) {
    int t;
    scanf("%d", &t);
    dp[0][t]++;
  }

  for(int i = 0; i < k; i++) {
    int sum = 0;
    for(int j = 0; j < 1024; j++) {
      if(sum & 1) {
        int cost = dp[0][j] >> 1;
        dp[1][j ^ x] += cost;
        dp[1][j] += dp[0][j] - cost;
      } else {
        int cost = (dp[0][j] + 1) >> 1;
        dp[1][j ^ x] += cost;
        dp[1][j] += dp[0][j] - cost;
      }
      sum += dp[0][j];
    }
    for(int j = 0; j < 1024; j++) {
      dp[0][j] = dp[1][j];
      dp[1][j] = 0;
    }
  }

  int small = 114514, big = -114514;
  for(int i = 0; i < 1024; i++) {
    if(dp[0][i] > 0) {
      small = min(i, small);
      big = max(i, big);
    }
  }
  
  printf("%d %d\n", big, small);

}

D. Jon and Orbs

codeforces.com

問題概要

${k(1 \le k \le 1000)}$ 種類のオーブがある.

最初は何も持っていない. 毎日 ${1}$ 個のオーブが出現するが, どの種類かはランダムである.

${q(1 \le q \le 1000)}$ 個の以下のクエリを全て処理せよ.

全種類のオーブが集まっている確率が ${(p_i - \epsilon) / 2000, (\epsilon \lt 10^{-7}, 1 \le p_i \le 1000)}$ 以上になる最短日数を求めよ.

解法

dp[day][sum]:= ${day}$ 日目まででオーブが ${sum}$ 種類集まっている確率とする.

現在 ${sum}$ 種類集まっているとすると, 新しい種類のオーブが出現する確率は ${(k-sum)/k}$ で, 出現しない確率は ${1}$ からそれを引いた値.

これをdpの遷移として, ${x}$ を回す日数とすると計算量は ${O(xk)}$ となる.

ここで気になるのは ${x}$ だが, これはdpの値が ${(1000 - \epsilon) / 2000}$ 以上となるまで回せばよい. 適当に調べてみると ${k = 1000}$ のとき ${8000}$ より小さいということが分かるので, その辺りまで回せば十分で, 計算量もいい感じで間に合う.

ソース

#include<bits/stdc++.h>

using namespace std;

double dp[8001][1002];

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

  fill_n(*dp, 8001 * 1002, 0.0);
  dp[1][1] = 2000.0;
  for(int i = 1; i < 8000; i++) {
    for(int j = 1; j <= K; j++) {
      long double hit = dp[i][j] * (K - j) / K;
      dp[i + 1][j + 1] += hit;
      dp[i + 1][j] += dp[i][j] - hit;
    }
  }

  while(Q--) {
    int P;
    cin >> P;
    for(int i = 0; i <= 8000; i++) {
      if(P <= dp[i][K]) {
        cout << i << endl;
        break;
      }
    }
  }
}

E. Game of Stones

codeforces.com

問題概要

${n(1 \le n \le 10^6)}$ 個の山があって, それぞれの山には石が ${s_i(1 \le s_i \le 60)}$ 個ある.

${2}$ 人で交互に, 好きな山から ${1}$ 個以上の石を取り除く操作を行う. 操作ができなくなった最初のプレイヤーが負けである.

この一般的な nim のルールに以下のルールを加える.

各山について考える. ${x}$ 個の石が取り除かれたとすると, もう一度 ${x}$ 個の石を取り除くことはできない.

どちらのプレイヤーも最適に行動するとき, どちらが勝つか求めよ.

解法

grundy 数を知っていますか? 僕は知っています! という問題.

最初の石の個数について grundy 数が求めることができれば, あとはそれを XOR して 0 かどうか見るだけ.

最初の石の個数の候補は 60 個以下. 見るからに long long で使えない個数を管理しながら求めてね! と言っているようなものなので愚直に試してみると数秒程度で求まる(ちょっとTLEしそう) ことがわかる.

この値を見ると明らかな法則が見えるが, 埋め込みでよいので埋め込めばよい.

ソース

こんな簡単なのを落とすんですかね…. if((bit >> i) & 1) を if((zan >> i) & 1) にしていた, それはシフトしてはいけない.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;


map< int64, int > dp[61];

int f(int64 zan, int64 bit)
{
  if(zan == 0) return (0);
  if(dp[zan].count(bit)) return (dp[zan][bit]);

  set< int > x;
  for(int64 i = 1; i <= zan; i++) {
    if((bit >> i) & 1) continue;
    x.emplace(f(zan - i, bit | (1LL << i)));
  }
  int z = 0;
  while(x.count(z)) z++;
  return (dp[zan][bit] = z);
}

int main()
{
  int v[61] = {0, 1, 1, 2, 2, 2, 3, 3, 3, 3,
               4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
               5, 6, 6, 6, 6, 6, 6, 6, 7, 7,
               7, 7, 7, 7, 7, 7, 8, 8, 8, 8,
               8, 8, 8, 8, 8, 9, 9, 9, 9, 9,
               9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10};

  int N;
  cin >> N;

  int xo = 0;
  for(int i = 0; i < N; i++) {
    int s;
    cin >> s;
    xo ^= v[s];
  }

  if(xo == 0) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

}

ei1333の日記

ぺこい

Codeforces Round #399 (Div. 1 + Div. 2, combined)

A. Oath of the Night’s Watch

問題概要

解法

ソース

B. Code For 1

問題概要

解法

ソース

C. Jon Snow and his Favourite Number

問題概要

解法

ソース

D. Jon and Orbs

問題概要

解法

ソース

E. Game of Stones

問題概要

解法

ソース