AtCoder Beginner Contest 194のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 194に参加し、レートが1727まで上がりました。

A - I Scream (100点)

問題文に書かれている通りに場合分けします。入力で与えられているのが無脂乳固形分 A\,\% と乳脂肪分 B\,\% ですが、条件分岐で必要なのは乳固形分 (A + B)\,\% と乳脂肪分 B\,\% であることに注意が必要です。

公式解説放送でsnukeさんが言及していた通り、この分類は『アイスクリーム類及び氷菓の表示に関する公正競争規約と公正競争規約施行規則』という規則によるものだそうです。

B - Job Assignment (200点)

2 \leq N \leq 1000 であるため、仕事Aと仕事Bに割り当てる人の組を全探索する O(N^2) でも通ります。その他にも O(N \log N) や O(N) の解法もあります。

$ O(N \log N) $ 解

先ず両方の仕事に同じ人を割り当てる時について全探索します。
違う人に割り当てる方法ですが、それぞれ A と B の小さい方から2人ずつまでが候補となるので A と B をソートすればいいです。このとき同じ人かどうかを記憶しておかなければならないのでそれぞれ所要時間とインデックスのpairの配列にしておきます。

$ O(N) $ 解

これは2つほど思いつきます。

決め打ちによる解法

A と B が小さい人をそれぞれ a,\,b とします。a \neq b のときはその二人に仕事を割り当てるのが最適で、\max\{A_a,\,B_b\}となります。
a = b のときは、その人に両方の仕事を割り当てる(A_a + B_a)か、Aを割り当ててBを次に B が小さい人 cに割り当てる (\max\{A_a,\,B_c\}) か、Bを割り当ててAを次に A が小さい人 d に割り当てる (\max\{A_d,\,B_a\}) か、のいずれかが最適です。上の O(N \log N) 解をソートではなくmin_elementや削除で実装することで O(N) で動きます。

それまでの最小値を記憶しておく解法

各 i (1 \leq i \leq N) について従業員 i を仕事に割り当てるとすると

  • 両方とも i に割り当てる: A_i + B_i
  • 仕事Aのみ i に割り当てる: \max\left\{A_i,\, \displaystyle\min_{1 \leq j \lt i} B_j\right\}
  • 仕事Bのみ i に割り当てる: \max\left\{B_i,\, \displaystyle\min_{1 \leq j \lt i} A_j\right\}

が最適の候補となります。よって i を小さい順から見ていくときにそれまでの A と B の最小値を記憶しておくといいです。

C - Squared Error (300点)

$$
\begin{align}
\sum_{i = 2}^{N} \sum_{j = 1}^{i-1} (A_i - A_j)^2 &= \sum_{i = 2}^{N} \sum_{j = 1}^{i-1} ({A_i}^2 + {A_j}^2 - 2A_iA_j) \\
&= \sum_{1 \leq j \lt i \leq N} ({A_i}^2 + {A_j}^2) - 2 \sum_{i = 2}^{N} A_i\sum_{j = 1}^{i-1}A_j \\
&= (N-1) \sum_{i = 1}^{N} {A_i}^2 - 2 \sum_{i = 2}^{N} A_i\sum_{j = 1}^{i-1}A_j
\end{align}
$$ より累積和を用いることで O(N) で求まります。

他にも
$$
\begin{align}
\sum_{i = 2}^{N} \sum_{j = 1}^{i-1} (A_i - A_j)^2 &= \frac{1}{2} \left(\sum_{i = 1}^{N} \sum_{j = 1}^{N} (A_i - A_j)^2 - \sum_{k = 1}^{N} (A_k - A_k)^2 \right)\\
&= \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} (A_i - A_j)^2 = \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} ({A_i}^2 + {A_j}^2 - 2 A_iA_j)\\
&= \frac{1}{2} \left( \sum_{j = 1}^{N} \sum_{i = 1}^{N} {A_i}^2 + \sum_{i = 1}^{N} \sum_{j = 1}^{N} {A_j}^2 \right) - \sum_{i = 1}^{N} A_i \sum_{j = 1}^{N} A_j\\
&= \frac{N}{2} \left(\sum_{i = 1}^{N} {A_i}^2 + \sum_{j = 1}^{N} {A_j}^2 \right) - \sum_{i = 1}^{N} A_i \sum_{j = 1}^{N} A_j \\
&=N \sum_{i = 1}^{N} {A_i}^2 - \left( \sum_{i = 1}^{N} A_i \right)^2
\end{align}
$$ として総和と2乗の総和から計算することもできます。

D - Journey (400点)

期待値の和の利用

確率 p で起こる事象を成功するまで行う時の回数の期待値は \displaystyle \frac{1}{p} です。これは漸化式や級数の計算等から導けます。
集合 S について整数 i (1 \leq i \leq N) をランダムに選び、S \leftarrow S \cup \{i\} とする操作を考えます。S の初期状態を \{1\} とすると問題文の操作と等価になります。
\#S = n の状態から \#S = n + 1 の状態へ1回の操作で遷移する確率は j \notin S である整数 j が選ばれる確率より \displaystyle \frac{N - n}{N} となり、その遷移についての操作回数の期待値は \displaystyle \frac{N}{N - n} です。
求める答えは最終的に \displaystyle S = \bigcup_{k=1}^{N}\, \{k\} \Longleftrightarrow \#S = N になるまでの操作回数の期待値であり、各遷移の期待値の和となるので
$$
\begin{align}
\sum_{n = 1}^{N-1} \frac{N}{N - n} = \sum_{i = 1}^{N-1} \frac{N}{i}
\end{align}
$$
が答えとなります。

期待値DP

この問題は期待値DPでも求めることができます。

$$ {\mathrm{dp}}_i = (\text{\(\#S = i\) の状態から\(\#S = N\) の状態になるまでの操作の回数の期待値}) $$ としたとき $$ {\mathrm{dp}}_N = 0 $$ であり、
各 i について確率 \displaystyle \frac{i}{N} で i が増えず、確率 \displaystyle \frac{N-i}{N} で i が 1 増えるので

\begin{align} &{\mathrm{dp}}_i = \frac{i}{N} ({\mathrm{dp}}_i + 1) + \frac{N-i}{N} ({\mathrm{dp}}_{i+1} + 1)\\ \Longleftrightarrow\ &{\mathrm{dp}}_i = {\mathrm{dp}}_i + 1 + \frac{i}{N-i} \end{align}
という漸化式から i を降順に求めることができ、求める答えは {\mathrm{dp}}_1 です。

E - Mex Min (500点、実行時間制限: 4 sec)

MexはNimなどのゲーム系の問題で用いられるGrundy数で出てきたりします。Minimum Exlusiveの略だそうです。
0 \leq A_i \lt N より答えの候補は 0 以上 N 以下になります。
答え候補を小さい方から見て行って、Mexになりえるものが見つかったら終了とすればいいです。
i がMexとなりえる時は次のいずれかを満たすときです。

  • i が A に登場しない場合
  • i の A 内の最初の登場が M+1 番目以降である場合
  • i の A 内の最後の登場が N - M 番目以前である場合
  • A 内の隣り合う i で、間隔が M 以上であるようなものが存在する場合

各値について登場するインデックスを昇順に保存する配列を用意しておくことでこれらの条件を満たすかを判定することができます。全ての値が 0 番目と N+1 番目に登場することにすると一番下の条件だけで判定することができます*1。

F - Digits Paradise in Hexadecimal (600点): 未提出

桁DPだなと思い必要な状態フラグは何だろうと考えたとき、最初はそれまでにどの数字を用いたかというものを考えましたが、2^{16} \times (2 \times 10^5) \simeq 1.31 \times 10^{10} であるのでもっと小さいものに帰着できないかと考えました。数字そのものよりも何種類出現したかの方だけでよいと思って実装を始めました。しかしleading zeroについての処理がうまく書けず、書き上げることができませんでした。
そのうちちゃんと実装してここについて追記しようと思います。

結果、感想

f:id:Flkanjin:20210307153143p:plain
1700到達しました。ただもうちょっと速く組めるようになりたいなって思います。

*1:2番目や3番目の条件については下の条件に帰着できるのは殆ど自明ですが、1番目の条件については M \leq N であることから帰着できます