1日9時間寝たい

本当は10時間寝たいです

CodeChef March Challenge 2019 - Cheating on Queue

Cheating on Queue (リンク)

問題概要

$A_1, A_2, \dots, A_N$ と $K$ が与えられる。
$i = 1, 2, \dots, N$ に対し $B_i := \lfloor A_i/1 \rfloor + \lfloor A_{i + 1}/2 \rfloor + \dots + \lfloor A_N/(N - i + 1) \rfloor$ としたとき $B_i \le K$ となる最小の $i$ を求めよ。
存在しなければ $N + 1$ を出力する。

  • $1 \le N \le 10^5$
  • $1 \le A_i \le 10^5$
  • $1 \le K \le 10^9$

解法

各 $i$ ごとに $B_i$ を求めるのではなく $A_i$ が $B$ に寄与する量を調べるといいです。
更新はだいたい次のようになります。

$B_1 \gets B_1 + \lfloor A_i/i \rfloor$
$B_2 \gets B_2 + \lfloor A_i/(i - 1) \rfloor$
$\vdots$
$B_{i - 1} \gets B_{i - 1} + \lfloor A_i/2 \rfloor$
$B_i \gets B_i + A_i$

もちろんふつうに計算すると $O(N^2)$ かかるのでダメです。
そこで、たとえば $A_i = 22$ として上の更新式の $+ x$ 部分を見てみます。

Bの添字 i-21 ... ... i-1 i
割る数 22 ... 12 11 10 9 8 7 6 5 4 3 2 1
x (商) 1 ... 1 2 2 2 2 3 3 4 5 7 11 22

この表から

  • 割る数が小さいうちはふつうに $x$ を足す
  • 大きくなると共通の $x$ が現れる範囲にまとめて足す
    • 実際は、範囲の左端に $+x$ して右端に $-x$ しておいてあとで累積和をとります

とすればよさそうと分かります。
割る数を $j$ とおきます。「$j$ の小さいうち」は具体的には $j^2 \le A_i$ 程度にすればいいです。つまり $j \le \lfloor \sqrt{A_i} \rfloor$ です。
また $\lfloor A_i/j \rfloor = x$ となる $j$ の範囲は $(\lfloor A_i / (x + 1) \rfloor, \lfloor A_i / x \rfloor]$ なので添字に変換して $B$ の対応する範囲に $x$ をまとめて足しましょう。
計算量は $O(N \sqrt{\max{A_i}})$ です。

提出

https://www.codechef.com/viewsolution/24247755

参考

https://discuss.codechef.com/t/chonq-editorial/22230

NimK (index-K Nim) の必勝判定・必勝側の具体的な手の選択

  • NimKの必勝判定
  • 必勝側の具体的な手の選択

について書きます。
後者は前者の証明に出てくるのですが念のために?指す手を求めるプログラムを書きました。

必勝判定

NimK または index-K Nim とは通常の $N$ 山 Nim の変形で、各手番では山を $K$ 個まで選択して石をとることができるゲームです。それぞれの山に積まれている石の個数を $A_1, A_2, \dots, A_N$ 個とします。このゲームでは $A_i$ を $2$ 進表示したとき桁ごとにとった和について

  • 和が $K+1$ の倍数でない桁があれば先手必勝
  • すべて $K+1$ の倍数ならば後手必勝

が成り立ちます。
たとえば $N = 5, K = 3$ で石の個数が $(22, 11, 42, 23, 19)$ の局面を考えます。$2$ 進表示して各桁の和を $\mathrm{mod}\ K+1$ で求めると次のようになるためこの局面は先手必勝です。

010110
001011
101010
010111
010011
------
132113

証明: 次を示せばいいです。

  • 先手必勝 → 後手必勝の手が存在する

  • 後手必勝 → 後手必勝の手が存在しない (先手必勝に移る手しかない)

$(A_1, \dots, A_N)$ が先手必勝だとします。また $(A_1, \dots, A_N)$ に対し $2^i$ に対応する桁について $\mathrm{mod}\ K+1$ で和をとったものを $S_i$ と書きます。
$S_i$ が $0$ でない最大の $i$ を $t$ とします。つまり $0 < S_t \le K$ であり $t < t'$ については $S_{t'} = 0$ です。$A_1, \dots, A_N$ のうちで $2^t$ に対応する桁が $1$ になっているものが $S_t$ 個あるので、それらを操作対象の山として選択します。選んだ山すべてから石を $2^t$ 個ずつとります。これは石の個数を $2$ 進表示したときに $2^t$ の桁を $1 \to 0$ とすることに対応しています。
ここまでで $S_t = 0$ にすることができました。さらにそれぞれの石の個数について $2^{t-1}, \dots, 2^0$ の桁を $1$ にします。このとき増える石の個数は最大でも $2^t-1$ なのでこの操作は許されます。
次に $S_{t-1}$ を見ます。$S_{t-1} = 0$ ならば文句なしですが、そうでない場合でも $S_{t-1} \le $ さっき選んだ山の個数 であれば問題ありません。実際、選んだ山に残っている石の個数について $2^{t-1}$ の桁を $1 \to 0$ にすることを $S_{t-1}$ 回行えばいいです。$S_{t-1} > $ さっき選んだ山の個数 であればしかたがないので必要な分だけ操作対象の山を増やすほかありません。新しく操作対象に追加した山について、石の個数を以前のステップと同じように変化させます。つまり $2^{t-1}$ の桁を $1 \to 0$ にしてそれより下位の桁をすべて $1$ にします。
$S_{t - 1} = 0$ にできたので、次は $S_{t - 2}$ を見て...を $S_0$ まで繰り返せばすべての $S_i$ を $0$ にできるため、後手必勝の局面に移れます。
ここで気になるのは $K$ 個より多くの山を操作対象として選んでしまうのではないかという点です。しかしその心配はありません。実際、これまでに $k$ 個の山を選んできていま $2^i$ に対応する桁を見ているとします。$S_i > k$ とすると新しく操作対象に加える山は $S_i - k$ 個で済むため、古いのと合わせて選んだ山の個数は $S_i$ 個になりますが $K + 1$ で割った余りを考えているので $S_i \le K$ です。よって選ぶ山の個数はちゃんと $K$ 個以下に収まっています。

$(A_1, \dots, A_N)$ が後手必勝だとします。簡単のため先頭から $k$ 個の山 $1, \dots, k$ を選んだとして、それぞれの山から $1$ つ以上石をとり $(A_1', \dots, A_k', A_{k+1}, \dots, A_N)$ になったとします。ただし $k \le K$ です。
各 $A_i'$ には $A_i' < A_i$ より $A_i$ では $1$ だった桁が $0$ になった箇所があります。$2^{r_i}$ に対応する桁がそのような桁のうちで最上位だとします。これより上の桁では $0 \to 1$ になった桁も無いことに注意してください。あったとすれば $A_i' < A_i$ に矛盾するからです。
$2^r := \max_{i}(2^{r_i})$ とおくと $2^r$ に対応する桁が $1 \to 0$ となった $A_i$ の個数は $1$ 以上 $k$ 以下です。一方 $0 \to 1$ となった $A_i$ は存在しません。
$(A_1, \dots, A_N)$ に対し $2^r$ の桁について $\mathrm{mod}\ K + 1$ で和をとった値を $S_r$ として、$(A_1', \dots, A_k', A_{k+1}, \dots, A_N)$ に対するそれを $S_r'$ とします。$(A_1, \dots, A_N)$ は後手必勝だったので $S_r = 0$ であり、$S_r - k \le S_r' \le S_r - 1$ より $S_r'$ は $K+1$ で割り切れません。
したがって後手必勝の局面に移れません。

手の選択

先手必勝局面が与えられたとき、そこから移れる後手必勝局面を上の証明で出てきた手続きによって求めるプログラムです。計算量は $O(N(\mathrm{log}_2(\mathrm{max}A_i))^2)$ です。

#include <algorithm>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <vector>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

void print_vector(vector<int> &a) {
  for (auto e : a) {
    cout << setw(2) << e << " " << bitset<8>(e) << endl;
  }
}

int main() {

  int n = 5, k = 3;
  vector<int> a = {22, 11, 42, 23, 19};
  puts("before:");
  print_vector(a);
  vector<int> x;
  rep(i, 31) {
    int s = 0;
    for (auto e : a) {
      s += e >> i & 1;
    }
    x.push_back(s % (k + 1));
  }
  assert(any_of(x.begin(), x.end(), [](const auto &e) { return e > 0; }));

  vector<int> chosen;
  for (int p = 30; p >= 0; p--) {
    for (auto j : chosen) {
      if (x[p] > 0) {
        a[j] ^= 1 << p;
        x[p]--;
      }
    }
    for (int j = 0; j < n and x[p] > 0; j++) {
      if (a[j] >> p & 1) {
        chosen.push_back(j);
        a[j] ^= 1 << p;
        x[p]--;
        for (int q = p - 1; q >= 0; q--) {
          if (!(a[j] >> q & 1)) {
            a[j] ^= 1 << q;
            x[q] = (x[q] + 1) % (k + 1);
          }
        }
      }
    }
  }

  puts("after:");
  print_vector(a);
  assert(chosen.size() <= k);
  rep(i, 31) {
    int s = 0;
    for (auto e : a) {
      s += e >> i & 1;
    }
    assert(s % (k + 1) == 0);
  }

  return 0;
}

実行すると次のような出力が得られます。
山 $2$ から石を $4$ 個とって山 $3$ から石を $21$ 個とったことが分かります。

before:
22 00010110
11 00001011
42 00101010
23 00010111
19 00010011
after:
22 00010110
 7 00000111
21 00010101
23 00010111
19 00010011

まとめ

NimK では $N$ 個の山に積まれている石の個数を $2$ 進表示して各桁ごとに $\pmod{K + 1}$ で和をとった数を $X$ とすると

  • $X$ (の $2$ 進表示) に $0$ でない桁があれば先手必勝
  • すべての桁が $0$ ならば後手必勝

となります。必勝側のプレイヤーは $X$ の上位桁から見ていき各桁が $0 \pmod{K + 1}$ になるように各山の石を減らしていけばいいです。このとき、すべての桁を $0$ にするために触る山は最大でも $K$ 個で済みます。

参考

木の中心が直径上に存在すること・中心を見つけるアルゴリズム

について書きます。

木の中心とは「各頂点への距離の最大値」が最小になる頂点 (の集合) です。
頂点 $v$ から各頂点への距離の最大値を $ E(v) $ と書きます。つまり、

$$ E(v) = \max_u\{\mathrm{dist}(v, u)\} $$

です。
頂点間の距離はそれらの間にある辺の本数です。
そして $E(v) = \min_u\{E(u)\}$ であるとき、頂点 $v$ は木の中心であるといいます。

言葉の感じから、中心は木の直径 (を与える $2$ 頂点を結ぶパス) の真ん中あたりにありそうな気がしてきます。
実際そうです。
$x, y$ を最遠点対とします。つまり、$d = \mathrm{dist}(x, y)$ は直径 $\max_{u}\{E(u)\}$ に等しいとします。
このとき、$x$ から $y$ の方向へ $\lfloor d/2 \rfloor$ 進んだ頂点を $c$ とすると $c$ は中心で $E(c) = \lceil d/2 \rceil = \mathrm{dist}(c, y)$ です。
任意に頂点 $v \neq c$ をとって $E(c) \le E(v)$ を示します。
そのためには、ある一つの $u$ に対して $E(c) \le \mathrm{dist}(v, u)$ が言えれば十分です。右辺は $E(v)$ 以下だからです。
さて、$v-x$ パスおよび $v-y$ パスを考えると、どちらかのパス上に $c$ があります。

f:id:poyopoyoyon:20190420203446p:plain
v-x パス上に c がある場合

  • $v-c-x$ となっている場合、$\mathrm{dist}(v, c) \ge 1$ より $\mathrm{dist}(v, x) \ge 1 + \mathrm{dist}(c, x) = 1 + \lfloor d/2 \rfloor \ge\lceil d/2 \rceil = E(c) $
  • $v-c-y$ となっている場合、$\mathrm{dist}(*, *) \ge 0$ より $\mathrm{dist}(v, y) = \mathrm{dist}(v, c) + \mathrm{dist}(c, y) \ge \mathrm{dist}(c, y) = E(c) $

$E(c) \le E(v)$ が言えたので $c$ は中心です。
また、$d$ が奇数のとき、つまり $\lfloor d/2 \rfloor \ne \lceil d/2 \rceil$ のとき $c$ から $y$ 側に $1$ 進んだ頂点もまた中心です。
証明は上の議論を $x$ と $y$ をひっくり返してコピペすればいいです (たぶん) 。

中心は直径上に存在し、その個数は $1$ つか $2$ つであることが分かりました。
それでは、$3$ つ以上存在しないことを示しましょう。
木の頂点数が $2$ 以下の場合はあきらかなので頂点が $3$ つ以上あるとします。
このとき、葉をぜんぶ取り去ったあとに残る木において、中心はもとの木の中心と一致します。
小さくなった木の任意の頂点 $v$ について $E(v)$ はもとの木でのそれより $1$ 小さいからです。
$E(v) = \max_u\{...\}$ を達成する $u$ は葉じゃないとおかしいですもんね。
残された木がまだ $3$ つ以上の頂点を持っていたら、葉を取り除く操作を繰り返します。
頂点が $2$ つ以下になっていたらそれら ($1$ つ or $2$ つ) が中心です。
ありがたいことに、この証明は具体的に中心の見つけ方を教えてくれています!
半径 $\min_u\{E(u)\}$ が欲しいだけなら、はじめにやったように直径を $2$ で割って切り上げするのが早いと思います。
直径は dfs を $2$ 回するアレで求まります。
この方法なら、終わったあとに直径の両端が手に入っているはずなので、パスをたどって中心を見つけてもいいです。

葉を削除していって中心を求めるアルゴリズムの実装例 (C++) を以下に示します。
直径を求める問題でむりやり使ってみるとこうなります:提出

#include <queue>
#include <vector>

using namespace std;

vector<int> centers(const vector<vector<int>> &g) {
  int n = g.size();
  vector<int> deg(n, 0);
  for (int i = 0; i < n; i++) {
    for (auto j : g[i]) {
      deg[j] += 1;
    }
  }
  queue<int> leaves;
  for (int i = 0; i < n; i++) {
    if (deg[i] == 1) leaves.push(i);
  }
  vector<int> removed(n, false);
  int remaining = n;
  while (remaining > 2) {
    queue<int> nxt;
    while (leaves.size() > 0) {
      auto leaf = leaves.front();
      leaves.pop();
      removed[leaf] = true;
      remaining -= 1;
      for (auto j : g[leaf]) {
        deg[j] -= 1;
        if (deg[j] == 1) nxt.push(j);
      }
    }
    leaves.swap(nxt);
  }
  vector<int> ret;
  for (int i = 0; i < n; i++) {
    if (not removed[i]) ret.push_back(i);
  }
  return ret;
}

最後の仕事です。
上で「葉を取り除く操作を繰り返す」と言いましたが、葉はつねに存在するんですか?という質問に答えないといけません。
頂点数を $n \ge 3 $ とします。

  • 木には葉が $2$ つ以上存在する

    葉の個数を $k$ とおく。辺数は $n - 1$ だから次数の和について

    $$\displaystyle k + \sum_{\mathrm{deg}(v) \ge 2} \mathrm{deg}(v) = 2 (n-1)$$

    が成り立つ。シグマは葉以外の頂点 $n - k$ 個に対して和をとっている。したがって、上の式より $k + 2(n - k) \le 2(n - 1)$ だから $k \ge 2$ である。

参考

Every tree has either one or two center | Tutorials on Mathematics