AtCoder Beginner Contest 194参加記（～F問題）

Fがむずすぎる
青パフォ
f:id:mmnkblog:20210306225900p:plain

A - I Scream

読解力が試される。問題文の太字で書かれたところはすべて入力で与えられる $A, B$ に置き換えられる。if文で処理する。

計算量は、 $O(1)$ 。

B - Job Assignment

問題文を読んだ時点で、計算量が $O(N)$ でも解けることを確信したので制約を見ていなかった。実は $O(N^2)$ でも通るらしい。こういうところで実装をサボらないとなんだか損した気分になる。

コンテスト中は場合分けして $O(N)$ で解いた。

1. 仕事 A と仕事 B をそれぞれ別の従業員に割り当てる場合
$A_i$ の最小値を $A_{\min}$ 、 $B_j$ の最小値を $B_{\min}$ とする。
$A_{\min}$ 分で仕事ができる従業員と、 $B_{\min}$ 分で仕事ができる従業員がそれぞれ別になるように割り当てられるか調べる。具体的には、
・ $A_i = A_{\min}$ となるような $i$ が2個以上ある場合
・ $B_j = B_{\min}$ となるような $j$ が2個以上ある場合
・ $A_i = A_{\min}$ となるような $i$ が1個のみ　かつ　 $B_j = B_{\min}$ となるような $j$ が1個のみ　かつ　 $i \neq j$
のどれかの場合、答えは $\max (A_{\min}, B_{\min})$ となる。上記に当てはまらない場合、 $A_i = A_{\min}$ を満たす従業員 $i$ が仕事Aか仕事Bを行うのは確定しているので、従業員 $i$ を除いた $N-1$ 人の中で一番早く仕事Aもしくは仕事Bをこなすことができる従業員をkを探す。よって答えは $\min(A_k, B_k)$ となる。

2. 仕事 A と仕事 B をどちらも同じ従業員に割り当てる場合
答えは $A_i + B_i$ の最小値である。

これらの答えの最小値が最終的な答えである。

計算量 $O(N^2)$ で解くなら、従業員のペアを全探索してシミュレーションし、その最小値を求めればよい。

C - Squared Error

式が正しいかどうか自信が無いがとりあえず書いておく（間違ってたらごめんなさい）。
式変形すると、
$\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2$
$= \displaystyle \sum_{i=2}^N \sum_{j=1}^{i-1} (A_i^2 + A_j^2 - 2 A_i A_j)$
$= \displaystyle \sum_{i=2}^N \sum_{j=1}^{i-1} A_i^2 + \sum_{i=2}^N \sum_{j=1}^{i-1} A_j^2 -2 \sum_{i=2}^N \sum_{j=1}^{i-1} (A_i \times A_j)$
となる。

ここで、
$\displaystyle \sum_{i=2}^N \sum_{j=1}^{i-1} A_i^2 + \sum_{i=2}^N \sum_{j=1}^{i-1} A_j^2 = \sum_{i=1}^N (N-1)\times A_i^2$
であり、
$\displaystyle \sum_{i=2}^N \sum_{j=1}^{i-1} (A_i \times A_j) = \sum_{i=2}^N (i \times \sum_{j=1}^{i-1} A_j)$
である。これは累積和を用いることで $O(N)$ で求められる。（参考：過去問に下位互換となる問題が出題済み。C - Sum of product of pairs）

よって全体でも計算量 $O(N)$ で答えを求めることができる。

D - Journey

わかってないけどAC。
まだ選ばれていない頂点が選ばれると、「すでに選ばれた頂点の集合（連結）」と連結になる。つまり、最初に高橋君がいる頂点1以外の $N-1$ 頂点をすべて選ぶまでの回数の期待値は？という問題になる。これはたしかガチャコンプ問題とかいう名前（俗称）がついていて、結構頻繁に出題されている（のに、未だに理解できていない）。

期待値の求め方がわからないので「期待値　回数　計算」でググると高校数学の美しい物語さんがヒットする。
mathtrain.jp

ここにそのまま答えが書いてある。どうやら期待値は漸化式を使って表現できるらしい。 $k$ 種類すでに引いている場合の期待値を考えると上手くいく？
とりあえず漸化式が立てばそれを更新していくだけなので、計算量は $O(N)$ である。

期待値の問題が苦手ということがわかったのでどこかで特訓したい（しない）

E - Mex Min

数列 $A$ のなかで、連続する $M$ 個の $\mathrm{mex}$ の最小値は？という問題。

$\mathrm{mex}$ 関数の定義より、 $M$ 個ある整数の中に、とある整数 $K$ が含まれていなければ、 $\mathrm{mex}$ 関数の返す値は少なくとも $K$ 以下となることがわかる。なので、 $0$ から $N-1$ までの整数 $K$ それぞれに対して、 $K$ が含まれない区間の長さの最大値が求められれば良い。これは、数列を前から舐めていって、各整数の直前の出現位置をメモしておけば解くことができる。

あとは $0$ から小さい順に、整数 $K$ が含まれない区間の長さの最大値は $M$ 以上かを判定してやればよい。

計算量は、 $O(N)$ 。

F - Digits Paradise in Hexadecimal

桁DPっぽさがある。
dp[i桁目まで確定][N未満フラグ][Leading Zeroを抜けたかフラグ][iビット目：iをすでに含んでいるか？を保持するフラグ(16bit)] := 総数
とすると解けそうだが、計算量が(dはd進数であることを示す、本門ではd=16) $O((Nの桁数)\times d 2^d)$ 程度になり、これは $10^{10}$ 回程度の計算が必要になるので間に合わない。

どうやら桁DPをしなくても解けるらしい。わかりません。

感想

Bがむずすぎる

3匹の猫

みみねこの競プロ精進メモ