CodeChef July Challenge 2019: LOVEMUFFIN - 日々ｄｒｄｒする人のメモ

CodeChef July Challenge 2019 の問題: LOVEMUFFIN (Code: LVMFFN)
問題ページ: Contest Page | CodeChef

問題概要

1から $N$ まで番号が付いた $N$ 人のメンバーがいる。
このメンバーで $M$ ドルを分配する。

この分配の方法の決め方は $i=1$ から以下のように行う。

番号 $i$ の人が現在いる各メンバーに何ドル分配するか提案する
この提案に(自分含めて) 人が賛成すればその分配方法に決まり、終了する
- $x$ は現在いるメンバーの数( $1 \le x \le N$ )とする
賛成数が足りず、分配方法が決まらなかった場合、番号iの人は屋上から放り出され、その場からいなくなる
- つまり、メンバーの数が1人減る
番号 $i+1$ の人が提案するところから(1)に戻る

各提案について各メンバーは、その提案に決まった場合に自身が得られる分配金に比べ、この案に決まらずその後の案で自分が確実に得られる分配金が同じもしくはそれ以上の場合、その提案に反対する。また、メンバー全員は自分が最大限の分配金を得られるように最適に動くとする。

また、提案に失敗し、屋上から放り出された人は $-10^{100}$ を得るのと同じと考える。

今から番号1の人がメンバーに対し分配方法を提案しようとしている。
同じ $K$ について、 $N, M$ が異なりうる $Q$ 個のシナリオについて、自分が最大いくら得られるか、もしくは確実に屋上から放り出されるかを求めよ。

制約

$2 \le K \le 10^5$
$1 \le Q \le 5 \times 10^5$
$1 \le N \le 10^{18}$
$2 \le M \le 10^{18}$

解法

各人がどのように最適に提案していくのかが分かりづらくて苦労した。
逆にそれが分かればなんとかなる問題だった。

まず、ある人を案に賛成させる場合、この案に決まらなかった場合の後の案で確実に得られる分配金より大きくなければならず、そのような人が(自分含めて) $\lfloor \frac{N}{K} \rfloor + 1$ 人必要となる。(提案する人は自分の提案に決まらなければ投げ出されるので必ず賛成する)

解としては、

人に、この案を決まらなかった場合に確実に得られる分配金 + 1 を配る
- 配る分配金が少ない人から配る
- この後確実に投げ出されてしまう人は0でも賛成するので配らなくてよい
残った分が得られる分配金の最大値、逆に足りなかった場合は投げ出される

となる。

各人が確実に得られる分配金は $N = 1$ の時から順番にシミュレーションしていけば分かる。
この問題で気をつけるべき点は、分配方法の仕方によって分配金が得られたり得られなかったりする時、それは確実に得られる分配金でないという点である。例えば、分配方法によって3もしくは0が得られる場合は、確実に得られる分配金は0であると考える。

以下は $M = 5, K = 2$ の時の分配方法である。(同じ列は同じ人を示している)
0以上は得られる分配金、-1は投げ出される状態、X?は分配方法によってはXもしくは0の分配金が得られることを示している。

N
1	5
2	5	-1
3	0	0	5
4	1	1	0	3
5	2?	2?	1	0	2
6	1	1	0	1	0	2
7	2?	2?	1	2?	1	0	1
8	1	1	0	1	0	1	0	1
9	2?	2?	1	2?	1	2?	1	2?	0
10	1?	1?	0	1?	0	1?	0	1?	1?	0
11	1?	1?	1?	1?	1?	1?	1?	1?	1?	1?	0
12	1?	1?	1?	1?	1?	1?	1?	1?	1?	1?	1?	-1

部分点は、この分配方法を $N = 1$ の時からシミュレーションしていけば取れる。(計算量: $O(N^2 \log N)$ )
ここまで通すのに結構時間かかった。

ここからは、得られる解を $N = 1$ から並べた数列を眺めて考えていく。

例えば、 $M = 5, K = 2$ の場合の $1 \le N \le 30$ の数列を以下に示す。

5,-1,5,3,2,2,1,1,0,0,0,-1,0,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,-1

別の例として、 $M = 5, K = 3$ の場合の $1 \le N \le 30$ の数列を以下に示す。

5,5,4,4,4,3,3,3,2,2,2,1,1,1,0,0,0,-1,0,-1,-1,0,-1,-1,-1,0,-1,-1,-1,-1

数列としては、はじめを除き $K$ 個ごとに1減少し、その後はいくつかの-1ごとに0が出現する並びになっている。
具体的に $K$ 個ごとに1減少していくのは $N \le MK$ の場合である。 $K = 2$ と $K \ge 3$ の場合で初めの並びが異なることに注意する。

次に0か-1が並ぶ $N > MK$ の場合について考えていく。
$N \ge MK$ に出現した各0について直前に0以上の値が何個前に出現したかで数列をつくってみる。

$K = 2$ の時は以下のようになることが分かる。 $2^x$ の形になる。

1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...

$K = 3$ の時は以下のような感じ。パッと見の規則性が分かりづらい。

1, 1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, ...

この数列をOEISで調べると以下の数列が出てくる。
K = 3 の時に出てくる数列: A073941 - OEIS
K = 4 の時に出てくる数列: A072493 - OEIS

$K$ で一般化すると以下の数列になることが分かる。

$a_1 = 1$
$\displaystyle a_i = \left\lceil \frac{\sum_{k=1}^{i-1} a_k}{K-1} \right\rceil$

この $a_i$ の和 $S_i = \sum_{k = 1}^i a_i$ を計算することで、0がいつ出現するかを計算することができる。

おまけに $a_i$ の総和 $S_i$ は以下の数列で計算できる。(今回は $S_i \le 10^{18}$ という制約から使わなかった)

$S_1 = 1$
$\displaystyle S_i = \left\lceil \frac{K}{K-1} S_{i-1} \right\rceil$

K = 3 の時に出てくる数列: A061419 - OEIS
K = 4 の時に出てくる数列: A087192 - OEIS

0になるか-1になるか判定するのには $S_i \le 10^{18}$ となる全ての $S_i$ が必要になるが、これらの値は制約的に計算することができる。
最も多くなるのが $K = 10^5$ の時で、この場合でも $S_i \le 10^{18}$ の個数は約 $3 \times 10^6$ 個になる。

まとめると、以下が解となる。

の場合
- の時
  - $N = 1, 3$ の時 → 解は $M$
  - $N = 2$ の時 → 投げ出される
  - $N > 3$ の時 → 解は $M - \lfloor \frac{N+1}{2} \rfloor$
- $K > 3$ の時 → 解は $M - \lfloor \frac{N}{K} \rfloor$
の場合
- 上記の数列の各総和を計算し、となるが存在するかを判定
  - 存在する時 → 解は 0
  - 存在しない時 → 投げ出される

$N > KM$ の場合については、調べる必要のある値 $N+1-KM$ を列挙しておき、 $S_i \le 10^{18}$ を全列挙しながら判定すればよい。

実装

この問題の制限時間が0.5秒だから、変な実装して無限にTLEしてめっちゃ思考錯誤してた。
(単純に計算方針が悪かっただけだった...)

制約がlong long intギリギリなので、オーバーフローに気をつけながら計算してる。

提出コード(C++14): Solution: 25200754 | CodeChef

// IO高速化
class FastIO {
  static const int rdata_sz = (1 << 25), wdata_sz = (1 << 25);
  char rdata[rdata_sz], wdata[wdata_sz], *rb, *wb;
  char tmp_s[20];

public:
  FastIO() {
    rdata[fread(rdata, 1, rdata_sz, stdin)] = 0;
    rb = rdata; wb = wdata;
  }
  ~FastIO() {
    fwrite(wdata, 1, wb - wdata, stdout);
  }

  template<typename T>
  inline void read_i(T &x) {
    bool neg = false;
    x = 0;
    while((*rb < '0' || *rb > '9') && *rb != '-') ++rb;
    if(*rb == '-') {
      neg = true;
      ++rb;
    }
    while('0' <= *rb && *rb <= '9') {
      x = 10 * x + (*rb - '0');
      ++rb;
    }
    if(neg) x = -x;
  }

#define pc(x) *(wb++) = x
  template<typename T>
  inline void writeln_i(T x) {
    if (x == 0) { pc('0'); pc('\n'); return; }
    if(x < 0) { pc('-'); x = -x; }
    char *t = tmp_s;
    while(x) {
      T y = x / 10;
      *(t++) = (x - y*10) + '0';
      x = y;
    }
    while(t != tmp_s) pc(*(--t));
    pc('\n');
  }
  inline void writeln_s(string s) {
    for(int i=0; i<s.size(); ++i) pc(s[i]);
    pc('\n');
  }
#undef pc
};
FastIO io;

#define Q 500001

int k, q;
ll p0[Q], q0[Q];

unordered_map<ll, bool> nmap;
const string cant = "Thrown off the roof.";

int main() {
  cin.tie(0); ios_base::sync_with_stdio(false);
  io.read_i(k); io.read_i(q);
  const ll inf = 1e18;

  nmap.reserve(8000000);
  if(k == 2) {
    // K = 2 の場合の前処理
    for(int i=0; i<q; ++i) {
      ll n, m;
      io.read_i(n); io.read_i(m);
      p0[i] = n; q0[i] = m;
      if((n+1)/2 > m) {
        nmap[n+1 - 2*m] = 0;
      }
    }
  } else {
    // K > 2 の場合の前処理
    ll limit = (inf+k-1)/k;
    for(int i=0; i<q; ++i) {
      ll n, m;
      io.read_i(n); io.read_i(m);
      p0[i] = n; q0[i] = m;
      if(m < limit && m*k < n) {
        nmap[n+1 - k*m] = 0;
      }
    }
  }

  // 数列とその総和の計算
  ll sum = 0, a = 1;
  while(sum + a >= 0 && sum + a <= inf) {
    sum += a;
    if(nmap.count(sum)) {
      nmap[sum] = 1;
    }
    a = (sum + k-2) / (k-1);
  }

  if(k == 2) {
    // K = 2 の場合: 解を計算
    for(int i=0; i<q; ++i) {
      ll n = p0[i], m = q0[i];
      if((n+1)/2 <= m) {
        if(n == 2) io.writeln_s(cant);
        else if(n <= 3) io.writeln_i(m);
        else {
          io.writeln_i(m-1 - ((n-1)/2));
        }
      } else {
        if(nmap[n+1-2*m]) {
          io.writeln_s("0");
        } else {
          io.writeln_s(cant);
        }
      }
    }
  } else {
    // K > 2 の場合: 解の計算
    ll limit = (inf+k-1)/k;
    for(int i=0; i<q; ++i) {
      ll n = p0[i], m = q0[i];
      if(limit <= m || n <= m*k) {
        io.writeln_i(m - n/k);
      } else {
        if(nmap[n+1-k*m]) {
          io.writeln_s("0");
        } else {
          io.writeln_s(cant);
        }
      }
    }
  }
  return 0;
}