AtCoder Beginner Contest 194 C,D,E,F問題メモ

AtCoder Beginner Contest 194

C - Squared Error

• 長さ $N$ の数列 $A_1,A_2,...$ が与えられる
• 各要素同士の差の二乗和、つまり $\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N} (A_i-A_j)^2$ を求めよ
• $2 \le N \le 3 \times 10^5$
• $|A_i| \le 200$

$A_i$ の範囲が小さく、$N$ が30万もあったとしてもほとんど同じ数字が重複していることがうかがえる。

なので、まず $A_i$ の値ごとに個数をカウントする。

A = [ 1 1 1 2 2 3 5 5 5 ]
↓
C = { 1:3,  2:2,  3:1,  5:3 }

値の種類は最大でも $401$ 通りしかないので、全てのペアの組み合わせを試しても8万通りくらいで十分間に合う。

たとえば $2$ と $5$ の値を使うと、$(2-5)^2 = 9$ で答えが9になるものが $2 \times 3 = 6$ 個あるので、全体に $54$ だけ加算されることになる。

Python3

from collections import Counter

n = int(input())
aaa = list(map(int, input().split()))
count = Counter(aaa)
values = list(count.keys())

ans = 0
for i in range(len(values)):
    a = values[i]
    for j in range(i + 1, len(values)):
        b = values[j]
        ans += (a - b) ** 2 * count[a] * count[b]

print(ans)

D - Journey

• $N$ 頂点のグラフがある。頂点には $1～N$ の番号が付いている。はじめ、辺は無い
• 高橋君ははじめ、頂点1に立っている
• 以下の操作を繰り返す
  • （高橋君がいる頂点も含み）$N$ 頂点から、一様ランダムに1頂点選ぶ
  • 高橋君は今いる頂点と選ばれた頂点間に無向辺を張り、選ばれた頂点に移動する
• 全体が連結になるまでの操作回数の期待値を求めよ
• $2 \le N \le 10^5$

高橋君が移動することにたいした意味は無く、ちょっとしたミスディレクションと思われる。

頂点1が既に選ばれた状態として、他の $N-1$ 頂点が最低1回ずつ選ばれたとき、操作は終了する。
いわゆる、コンプガチャで全部そろえるまでにかかる回数期待値となる。

「確率 $p$ で発生する現象が最初に起きるまで試行を繰り返すとき、回数期待値は $\dfrac{1}{p}$」という法則がある。

• 幾何分布

これを利用するとよい。（使わなくてもDPでも解ける）

1段階ずつ、「まだ選ばれていないどれか1個が選ばれるまでの回数期待値」を求めていく。

たとえば $N=5$ の時、初期状態からまだ選ばれていない頂点が1個選ばれる確率は $\dfrac{4}{5}$ なので、その回数期待値は $\dfrac{5}{4}$。

次、まだ選ばれていない頂点は3個になり、確率は $\dfrac{3}{5}$、期待値は $\dfrac{5}{3}$。

次は期待値 $\dfrac{5}{2}$、さらに次の最後の1個が選ばれるまでの期待値は $\dfrac{5}{1}$。

これで全ての頂点が選ばれたので、これらの合計が答えとなる。

自己ループを含むDPを、式変形する。

• $DP[i]=$ まだ選ばれていない頂点が $i$ 点あるときの、残り回数期待値

$DP[0]=0$ であり、$DP[N-1]$ が求める答えである。

遷移は、たとえば $N=5,i=3$ のとき、1回操作すると

• 確率 $\dfrac{3}{5}$ で新しい頂点を引き、$i=2$ に遷移する
• 確率 $\dfrac{2}{5}$ で新しい頂点が引けず、$i=3$ のまま滞留する

が合わさったものなので、以下のようになる。

• $DP[3]=\dfrac{3}{5}DP[2] + \dfrac{2}{5}DP[3] + 1$

両辺を整理すると、こうなる。

• $DP[3] = DP[2] + \dfrac{5}{3}$

一般化すると、

• $DP[i] = DP[i-1] + \dfrac{N}{i}$

となり、幾何分布を使ったときと同様の計算をすれば求められることがわかる。

Python3

from decimal import Decimal

n = input()
dn = Decimal(n)
n = int(n)
ans = Decimal('0')
for i in range(1, n):
    ans += dn / i

print(ans)

E - Mex Min

• 長さ $N$ の数列 $A_1,A_2,...,A_N$
• 長さ $M$ の（連続した）部分列は $N-M+1$ 個あるが、全てに対してMEXを求め、その中の最小値を求めよ
  • MEXとは、その数列に含まれない最小の非負整数を指す
• $1 \le M \le N \le 1.5 \times 10^6$
• $0 \le Ai \lt N$
• 制限時間 $4$ sec.

部分列の個数が $O(N)$、1個の部分列のMEXを求めるのに $O(M)$ かかるので、愚直な解法は分が悪い。

部分列でなく非負整数 $k$ を固定して、「$k$ が含まれない長さ $M$ の部分列はあるか？」を考える。
あるなら、そのような $k$ の中で最小のものが答えとなる。

そしてこの条件は言い換えると「数列 $A$ のどこかで、$k$ 以外の数字が $M$ 個以上連続している箇所がある」となる。

M = 5
3 1 0 4 1 0 2 4 0 1

k以外の数字が連続している箇所の最大長さ
0: 2
1: 4
2: 6
3: 9
4: 3

この例では、小さい方からみてはじめて $M=5$ 以上となった $2$ が答えとなる。

各数字、直前に出てきたindexを管理しつつ前から見ていけばよい。

$A_i$ が取り得るのは $N-1$ までだが、答えは $N$ になり得る点に注意。

Python3

from collections import defaultdict

n, m = map(int, input().split())
aaa = list(map(int, input().split()))

prev = defaultdict(int)
current_max_dist = [0] * n
for i, a in enumerate(aaa, start=1):
    p = prev[a]
    current_max_dist[a] = max(current_max_dist[a], i - p - 1)
    prev[a] = i

for a in range(n + 1):
    p = prev[a]
    dist = max(current_max_dist[a], n - p)

    if dist >= m:
        print(a)
        break

F - Digits Paradise in Hexadecimal

• 16進数表記で整数 $N$ が与えられる
• $1$ 以上 $N$ 以下の整数の中で、先頭に0が付かない16進数表記にしたとき、使われる数字の種類がちょうど $K$ 個のものの個数を $\mod{10^9+7}$ で求めよ
• $1 \le Nの桁数 \le 2 \times 10^5$
• $1 \le K \le 16$

桁DPと呼ばれる。
巨大な $N$ が与えられ、「$N$ 以下で、○○の条件を満たすものを数えろ」とかそんな感じの問題。
まぁ問題設定として隠しづらいので、見ただけで桁DPの問題だとわかりやすい。

• 桁 DP の思想 〜 K 以下の整数を走査するとはどういうことか 〜 - けんちょんの競プロ精進記録
• 類題解説
  • Educational DP Contest | S - Digit Sum

条件によってDPがどう遷移するかは問題毎に考える必要があるのだが、およそ共通するパターンとして、

• 上位の桁から1つずつ考えていく
  • DPでは $N$ より小さいことが確定したパターンを数えていく
  • ある桁の数字が $N$ より小さくなったら、それ以降の桁はどんな数字が来てもよいので、遷移をまとめやすい
• 毎桁、新規に $N$ より小さいことが確定する数が追加される
  • 上から $i$ 桁目を考慮中として、
    • 上位 $i-1$ 桁までは $N$ と一致するが、$i$ 桁目で初めて $N$ より小さいことが確定する数
    • 上位 $i-1$ 桁までは $0$ が並ぶが、$i$ 桁目で初めて $0$ 以外の数字が現れる数

大まかな方針は上記のようになるが、遷移は問題依存であり、実装まではパターン化しにくいイメージがある。

今回の場合、DPには $i$ の他には既に使用した数字の種類 $j=1～K$ の情報さえあれば問題ない。

• $DP[i][j]=$ 上位から $i$ 桁目までを切り出して考えたときに、$N$ の $i$ 桁目までより真に小さい中で、使われている数字の種類数が $j$ であるような数の個数
  • ただし $j=1$ であっても、全ての桁が '0' であるものは除く（先頭の'0'は消えるので）

あとはほぼ公式解説の通りなので省略。

Python3

n, k = input().split()
k = int(k)
MOD = 10 ** 9 + 7
d = len(n)

c = int(n[0], 16)

just = True
dp = [0] * (k + 1)
dp[1] = c - 1
appeared = {c}

for i in range(1, d):
    c = int(n[i], 16)
    ndp = [0] * (k + 1)
    if just:
        for p in range(c):
            if p in appeared:
                ndp[len(appeared)] += 1
            elif len(appeared) < k:
                ndp[len(appeared) + 1] += 1

        if len(appeared) < k:
            appeared.add(c)
        elif c not in appeared:
            just = False

    ndp[1] += 15

    for i in range(1, k):
        ndp[i] += i * dp[i]
        ndp[i + 1] += (16 - i) * dp[i]
    ndp[k] += k * dp[k]

    for i in range(1, k + 1):
        ndp[i] %= MOD

    dp = ndp

ans = dp[k]
if just and len(appeared) == k:
    ans += 1

print(ans % MOD)

なんか、「上位 $i-1$ 桁までは $0$ が並ぶが、$i$ 桁目で初めて $0$ 以外の数字が現れる数」も上手くやればDP遷移に入れ込めることに気づかず、 $N$ の桁数に満たないものは別に包除原理で数えるとか、変なことしてしまった。