AtCoder Beginner Contest 194 C,D,E,F問題メモ
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
問題
解法
高橋君が移動することにたいした意味は無く、ちょっとしたミスディレクションと思われる。
頂点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を、式変形する。
$DP[0]=0$ であり、$DP[N-1]$ が求める答えである。
遷移は、たとえば $N=5,i=3$ のとき、1回操作すると
が合わさったものなので、以下のようになる。
両辺を整理すると、こうなる。
一般化すると、
となり、幾何分布を使ったときと同様の計算をすれば求められることがわかる。
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を求め、その中の最小値を求めよ
$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
問題
解法
桁DPと呼ばれる。
巨大な $N$ が与えられ、「$N$ 以下で、○○の条件を満たすものを数えろ」とかそんな感じの問題。
まぁ問題設定として隠しづらいので、見ただけで桁DPの問題だとわかりやすい。
条件によってDPがどう遷移するかは問題毎に考える必要があるのだが、およそ共通するパターンとして、
大まかな方針は上記のようになるが、遷移は問題依存であり、実装まではパターン化しにくいイメージがある。
今回の場合、DPには $i$ の他には既に使用した数字の種類 $j=1～K$ の情報さえあれば問題ない。
あとはほぼ公式解説の通りなので省略。
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$ の桁数に満たないものは別に包除原理で数えるとか、変なことしてしまった。