Home / Python /

AtCoder Beginner Contest 194をPythonで解く

投稿日：　

Atcoder Python

B!
Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 194を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 194 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - I Scream

条件を書いてif文で分岐させれば問題ないです.

B - Job Assignment

考え方はいくつかあります.

計算にちょっと時間がかかる方法

まずは,

  • 1人でどちらの仕事もやるパターン
  • 2人でどちらの仕事もやるパターン

の全場合を探索し, 最小値を出す方法です. 1人でどちらの仕事もやるパターンを全て調べるのに$O(N)$, 2人でどちらの仕事もやるパターンを全て調べるのに$O(N^2)$かかるので, この方法だと最終的に$O(N^2)$だけかかります.

計算にそこまで時間がかからない方法

2人でどちらの仕事もやるパターンを全探索しないでやることもできますね.

  • 1人でどちらの仕事もやるパターン
  • $A$の仕事に最も時間がかからない人との組み合わせのパターン
  • $B$の仕事に最も時間がかからない人との組み合わせのパターン

の全場合を探索し, 最小値を出す方法です. 上記すべてのパターンを全て調べるのに$O(N)$かかるので, この方法だと最終的に$O(N)$だけかかります.

上で書いたようなものをよりスマートに書き直したようなものが, AtCoderの解説に載っていました.

Editorial - AtCoder Beginner Contest 194

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

C - Squared Error

問題文にあることを律儀に実行すると, $O(N^2)$だけかかり, TLEです.

そこで, 例えば次のように考えます.

\begin{align} \sum_{i=2}^N \sum_{j=1}^{i-1} \left( A_i - A_j \right)^2 &= \sum_{i=2}^N \sum_{j=1}^{i-1} \left( A_i^2 - 2 A_i A_j + A_j^2 \right) \nonumber \\ &= \sum_{i=2}^N \left( i-1 \right) A_i^2 - 2 \sum_{i=2}^N \left( A_i \sum_{j=1}^{i-1} A_j \right) + \sum_{i=2}^N \sum_{j=1}^{i-1} A_j^2 \end{align}

それぞれ累積和や二乗の累積和は$O(N)$で事前に求めておくことができます. よって, このように展開するだけで$O(N)$で解くことができます.

あるいは, 次のようにも考えることができます. $\sum$の上下限は, 差の二乗をとる際に同じ組み合わせが現れないようにしてあります. $A_i - A_i = 0$ですので, $i$も$j$も両方$1$から$N$まで足し上げて$1/2$してもいいんですね.

\begin{align} \sum_{i=2}^N \sum_{j=1}^{i-1} \left( A_i - A_j \right)^2 &= \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^{N} \left( A_i - A_j \right)^2 \nonumber \\ &= \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^{N} \left( A_i^2 - 2 A_i A_j + A_j^2 \right) \nonumber \\ &= \frac{1}{2} \left( N \sum_{i=1}^N A_i^2 - 2 \sum_{i=1}^N \left( A_i \sum_{j=1}^N A_j \right) + N \sum_{j=1}^N A_j^2 \right) \nonumber \\ &= N \sum_{i=1}^N A_i^2 - \left( \sum_{j=1}^N A_j \right)^2 \end{align}

ここまで変形してしまえば, ここまでスマートにコーディングすることができます.

D - Journey

最終的にグラフが連結になるためには, 最初にいる頂点$1$以外の$N - 1$個の頂点を新たに訪れなければなりません. つまり, 「今までに訪れていない頂点に新たに訪れる」ということを$N - 1$回行わなければなりません.

  • $S$：今までに訪れたことのある頂点の集合
  • $|S|$：$S$の要素数

とすると, 新しい頂点に訪れる確率は$\left( N - |S| \right) / N$となります.

ここで, 確率$p$($p \neq 0$)で成功する試行を, 成功するまで行うときの試行回数(最後の成功した回も含む)の期待値は$1/p$であることが知られています*1.

この事実を用いれば, $|S| = 1$のときから$|S| = N - 1$のときまで$N / \left( N - |S| \right)$を足し上げて,

\begin{align} \frac{N}{N - 1} + \frac{N}{N - 2} + \cdots + \frac{N}{1} \end{align}

が, 求める答えになります. これは$O(N)$で求めることが可能です.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

脚注

*1 :これは以下のようにして証明される.

Bernoulli試行(Bernoulli trial)(取り得る結果が「成功」「失敗」の2つのみであり, 各試行において成功の確率が同じであるランダム試行)を繰り返して初めて成功させるまでの試行回数$X$の分布は, 幾何分布(geometric distribution)として知られている. 以下, そのBernoulli試行において, 「成功」する確率を$p$($p > 0$)とする. $X = k$のとき, $k - 1$回「失敗」した後に$1$回「成功」することになるので,

\begin{align} P(X=k) &= p \left( 1 - p \right)^{k-1} \end{align}

となる.

図 「成功」の確率が$p=1/2$, $p=1/3$, $p=1/4$, $p=1/5$の幾何分布.

この幾何分布の期待値を計算すると,

\begin{align} E(X) &= \sum_{k=1}^\infty k P(X=k) \nonumber \\ &= \sum_{k=1}^\infty k p \left( 1 - p \right)^{k-1} \nonumber \\ &= p \sum_{k=1}^\infty k \left( 1 - p \right)^{k-1} \nonumber \\ &= - p \sum_{k=1}^\infty \frac{\mathrm{d}}{\mathrm{d}p} \left( 1 - p \right)^k \nonumber \\ &= - p \frac{\mathrm{d}}{\mathrm{d}p} \sum_{k=1}^\infty \left( 1 - p \right)^k \nonumber \\ &= - p \frac{\mathrm{d}}{\mathrm{d}p} \frac{1 - p}{1 - \left( 1 - p \right)} \nonumber \\ &= \frac{1}{p} \end{align}

となる.

Search

About Me

自分の写真
理系大学生でした. Bloggerを利用して発信を行っています.

Labels

Blog Archives