絶滅

どうでもいい

CodeChef - July Challenge 2018 Division 2

CodeChef Algorithm C++

記事を書きながら解けば思考が纏まるかもしれないという試み

コンテストページはここ




Strike or Spare - PINS

概要

数字 $N \ (\le 10^{5})$ 桁からなるパスワード全体を考えた時，回文となるような確率はいくつか？
既約分数で $P / Q$ と表されるとき，$P$ と $Q$ をスペース区切りで一行に出力せよ．

解法

左から $ \lfloor (N + 1) / 2 \rfloor $ 桁を決定すると対応する回文が一意に定まる．

例 :
1234xxx -> 1234321
9483xxxx -> 94833849

よって，全体 $10^{N} $ 通りのパスワード候補に対して回文となるものは $ 10^{\lfloor (N + 1) / 2 \rfloor} $ 通りあるから，求める答えは $P = 1, \ Q = 10^{N - \lfloor (N + 1) / 2 \rfloor}$．



Magic Set - MGCSET

概要

数列 $a_{1}, a_{2}, ..., a_{n}$ と整数 $ m $ が与えられる．
数列 $ a $ の空でない部分列(連続である必要はない)で，要素の総和が $ m $ で割り切れるものの総数を求めよ．

制約
  • $1 \le T \le 1,000 \quad$ (テストケース数)
  • $1 \le n \le 30$
  • $1 \le m \le 1,000$
  • $1 \le a_{i} \le 1,000 \quad \text{for each valid} \ i$
解法

数列 $ a $ の要素のうち $ m $ の倍数であるものの個数を $ k $ とすると，
各要素を含めるか含めないか決定することで条件を満たす部分列を構成できる．
そのような部分列は $2^{k}$ 個存在し，空の部分列を除いた

$2^{k} - 1$

が答えとなる．



No String Attached - NSA

概要

長さ $ N $ の文字列 $ S $ が与えられる．
$ S $ の一文字 $ S[i] $ を文字 $ c $ にコスト $X = |S[i] - c|$ で変更できる(変更しなくてもよい)．
元のまたは変更後の文字列に対して，スコア $ Y $ を以下で定める：

$Y = $ (添字の組 $(i, j)$ で，$1 \le i < j \le N$ かつ $ S[i] < S[j] $ を満たすものの総数)

$X + Y$ を最小化せよ．

制約
  • $1 \le T \le 20$ (テストケース数)
  • $1 \le N \le 10^{5}$
  • $ S $ の各要素は英小文字
解法

二次元累積和を使えば解けることはわかるんだけど何故か答えが合わない．厳しい



No Minimum No Maximum - NMNMX

概要

相異なる $ N $ 個の正整数からなる数列 $ a_{1}, a_{2}, ..., a_{N} $ と整数 $ K $ が与えられる．
数列 $ \{a_i\} $ の部分列で長さ $ K $ であるもの全てを集めた集合を $ S $ とする．
$ S $ の要素 $ e $ について，その最小要素と最大要素を除いた $ K - 2 $ 個の要素の積を $ P(e) $ としたとき，

$ \prod_{e \in S} P(e) \quad \mathrm{mod} \ 1000000007 $

を求めよ．

制約
  • $1 \le T \le 10$ (テストケース数)
  • $3 \le N \le 5,000$
  • $3 \le K \le N$
  • $1 \le a_{i} \le 10,000 \quad \text{for each valid } i$
  • the numbers $a_{1}, a_{2}, ..., a_{N}$ are pairwise distinct
解法

まず愚直解法
最大値・最小値を固定して，その間にある K-2 個の要素を列挙すると漏れ・ダブリなく部分列を調べることができる．
ソートして区間を決めるとその両端が最小・最大となるのでこれを利用する．

  • 数列 {ai} を昇順にソート
  • ans = 1
  • for ( j - i ≧ K - 1 なる全ての組 (i, j) ) :
    • S' = {ai+1, ai+2, ..., aj-2, aj-1}
    • prod = 1
    • for ( S' の 長さ K-2 の部分列 U ) :
      • prod *= (U の要素全ての積)
    • ans *= prod
  • print( ans )

内側のループが二項係数のオーダーになるのでこのままでは TLE する．


計算量を落とせないか考える．例として

a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
K = 5

のケースを考える．

外側のループにおいて i = 0, j = 6 である状況を考える．

a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

赤字で示した連続部分列が S' であり，ここから K - 2 = 3 個の要素を拾う組み合わせを考えると以下のようになる．

f:id:my316g:20180710103551p:plain

よって i = 0, j = 6 の時の prod は

prod = 26 * 36 * 46 * 56 * 66

となる．ここで 6 という数字は j-i-2CK-3 に等しいことが簡単な計算でわかる．

以上の考察より計算量を落としたアルゴリズムが以下．

vector<ll> a(N);
sort(all(a));

vector<ll> e(N + 1, 0); // 各 a[i] の指数

for (ll i = 0; i <= N - K; i++) {
    for (ll j = i + K - 1; j < N; j++) {
        // combination(j-i-2, K-3) % (1000000007 - 1)
        ll c = comb[j - i - 2][K - 3]; 
        // imos
        e[i + 1] += c;
        e[j] -= c;
    }
}
for (ll i = 0; i < N; i++)
    e[i + 1] += e[i];
for (ll i = 0; i < N; i++)
    e[i] %= MODM; // MODM = 1000000007 - 1
        
ll ans = 1;
for (ll i = 0; i < N; i++) {
    ans = ans * modpow(a[i], e[i], MOD) % MOD;
}

cout << ans << endl;

だるいので C++ で書いた．
区間 (i, j) に対する加算は imos 法を使う．
各要素の肩にかかる指数はフェルマーの小定理

ap-1 ≡ 1 (mod p)

より 1000000007 - 1 で割った余りが分かればいい．
combination については N * N の配列に pascal の三角形を用いて予め計算する．
累乗は繰り返し二乗法(ダブリング)で計算．

ここまでやると計算量が O(N2) まで落ちるので AC．

色々な要素があって面白い問題だった．

Reach Equilibrium - EQUILIBR

概要

二次元平面上の $ n $ 本のベクトル $ v_{0}, v_{1}, ..., v_{n-1} $を考える．
各ベクトルの大きさ $ k_{i} = |v_{i}| $ が，$ \sum_{i = 0}^{n-1} k_i = k $ となるよう uniformly randomly に与えられる．
適切な方向を定めることによってベクトル和を $ \sum_{i = 0}^{n-1} v_i = 0 $ とできる確率が知りたい．

そのような確率は $ P/Q $ と表されることが知られているので，答えを

$ P \cdot Q^{-1} \quad \mod \ 1000000007 $

の形で出力せよ．

制約
  • $1 \le k \le 100$
  • $2 \le n \le 3 \cdot 10^{5}$
解法

AtCoder も真っ青な数学問題っぽかったけどシミュレーションして解析解をエスパーして殴った．
幾何学的確率*1の問題にカテゴライズされるのかな？
「Buffon の針」とか「線分分割による三角形の作成可能確率」みたいな．


シミュレーション

重要なのは各ベクトルの大きさの比率なので k = 1 として問題ない．

まず uniformly randomly にベクトルの大きさ ki を取ってくる．
[0, 1] の範囲で一様乱数を n-1 回発生させてソートしたものを x1, ..., xn-1 とする．x0 = 0, xn = 1 として，ki = xi+1 - xi とすればよい．

次にベクトル和を 0 にできるか判定する必要があるが，

mindp[i] : i 番目までのベクトル和の大きさ |v0 + ... + vi| の最小値
maxdp[i] : i 番目までのベクトル和の大きさ |v0 + ... + vi| の最大値

とすると，

vector<double> mindp(n), maxdp(n);
mindp[0] = k[0], maxdp[0] = k[0];
for (int i = 1; i < n; i++) {
    maxdp[i] = maxdp[i - 1] + k[i];
    if (mindp[i - 1] <= k[i] && k[i] <= maxdp[i - 1])
        mindp[i] = 0.0;
    else
        mindp[i] = min(abs(k[i] - mindp[i - 1]), abs(k[i] - maxdp[i - 1]));
}

こんな感じで更新できる．
mindp[n - 1] == 0.0 になっていたらベクトル和を 0 にすることが可能．

このシミュレーションをぶん回してそれっぽい分数値を求めてやると，

  • n = 2m のとき $ \displaystyle \frac{ P }{ Q } = 1 - \frac{ m }{ 4^{m - 1} } $
  • n = 2m + 1 のとき $ \displaystyle \frac{ P }{ Q } = 1 - \frac{ 2m - 1 }{ 4^{m} } $

らしいことがわかるので，ダブリングとかフェルマーの小定理とか使ってえいして終わり．

(これは邪道なのでみなさんは数学をしましょう)


// -------8<--------------------------------------------8<-------


ここで TCOMMR3 が始まったのと飽きたので終わり

レートが地味に 1800 を超えてしまったので次回 Div.1 で死ぬ

*1:参考 : http://izumi-math.jp/W_Takakura/k_kakuritu/k_kakuritu.pdf