Home / Python /

AtCoder Beginner Contest 214をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

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

AtCoder Beginner Contest 214 - AtCoder

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

A - New Generation ABC

if文を用いて素直に分類すればよいです.

B - How many?

$a + b + c \leq S$を満たす$(a, b, c)$に対して, $a \times b \times c \leq T$を満たすかどうかを調べて数え上げます.

C - Distribution

$i$番目のすぬけ君が$j$番目のすぬけ君に渡された宝石を手にする秒数を全て調査して, $i$番目のすぬけ君が最初に宝石を受け取る時刻をmin()などで取得することが考えられます. しかし, これだと時間計算量が$O(N^2)$となりTLEとなってしまいます.

ここで, $i$番目のすぬけ君は,

  1. 高橋君から$T_i$秒後にもらう
  2. $(i - 1)$番目のすぬけ君がある時刻に受け取り, その$S_{i - 1}$秒後にもらう

のいずれかで最初に宝石を手にすることになります. これにより, 1.と2.の最小値で$T_i$を更新していけばよいことが分かります. 実際には, 最初のすぬけ君に関しては1.と2.のどちらが本当に小さいかは真にはわからないので, ループは少なくとも2回繰り返す必要があります.

と思いきや, $T_i$が最も小さい$i$番目のすぬけ君からスタートすれば, ループは1回でよくなります. $T_i$が最も小さい$i$番目のすぬけ君に与えられた宝石は, 全すぬけ君に与えられた最初の宝石であるからです.

D - Sum of Maximum Weights

$f(u, v) = w_i$となる$(u, v)$の総数を考えます. $(u, v)$が$f(u, v) = w_i$を満たすためには, 以下の2つの条件を満たさなくてはなりません.

  1. 頂点$(u, v)$を結ぶ道に辺$i$が含まれる.
  2. その道に含まれる他の辺の重みが$w_i$より小さい.

そこで, $w_i$が小さい順に道をつなげていくことを考えます. 辺$i$の両端$u_i$, $v_i$について

  • $\mathrm{size} \, (u_i)$：$u_i$とすでに(重みが$w_i$より小さい辺によって)道ができている他の点の数($u_i$を含める)
  • $\mathrm{size} \, (v_i)$：$v_i$とすでに(重みが$w_i$より小さい辺によって)道ができている他の点の数($v_i$を含める)

を調べ, $\mathrm{size} \, (u_i) \times \, \mathrm{size} \, (v_i) \times w_i$を調べていくのです. 実際, この道をつなげる操作によって, $u_i$が属するグループの点と$v_i$が属するグループの点は, 初めてつながることになります. そして, その2点をつなぐ道に含まれる最も重い辺の重みは$w_i$になります. 与えられるグラフが「木」であり, グラフ中に閉路が存在せず, 頂点$(u, v)$を結ぶ道は唯一であることから, この議論が成り立ちます.

例えば, 簡単に以下のようなグラフが与えられたと考えます.

図1 与えられるグラフの例. 丸はグラフの頂点(番号付き)を, 点線はこれからつなげていく辺(重み付き)を示す.

今の場合, まずつなげるのは頂点$1$と頂点$2$をつなげる辺です. この操作によって頂点$1$と頂点$2$は初めてつながり, その2点をつなぐ(唯一の)道に含まれる最も重い辺の重みは$1$になります.

図2 図1のグラフにおいて頂点$1$と頂点$2$をつなげた結果.

次につなげるのは頂点$2$と頂点$3$をつなげる辺です. この操作によって頂点$1$と頂点$3$, 頂点$2$と頂点$3$は初めてつながり, それぞれをつなぐ(唯一の)道に含まれる最も重い辺の重みは$2$になります.

図3 図1のグラフにおいて頂点$1$と頂点$2$, 頂点$2$と頂点$3$をつなげた結果.

この後の例は省略しますが, このようにして答えを求めていきます.

このようなデータ構造は, Union Findデータ構造と呼ばれます. 以下のコードでは, それから最低限を取り出して記述しています.

あるいは, Union Findデータ構造を使用するということになったら, クラスとしてまとまっているものを使用してしまうのも手です. 以下は, nkmk様のWebページ(https://note.nkmk.me/python-union-find/)にあるUnion Findデータ構造のクラスへのリンクです.

python-snippets/union_find.py at c12512379e6160792cb1f53b31ecbbfae4c998aa · nkmk/python-snippets

Contribute to nkmk/python-snippets development by creating an account on GitHub.

クラスに関しては, 「AtCoder APG4bをPythonで解く(6)」EX24 - 時計の実装においても取り上げています.

AtCoder APG4bをPythonで解く(6)

こんにちは, Shinoryoです. 今回は C++入門 AtCoder Programming Guide for beginners(APG4b) を, Pythonで無理やり解いてみた結果を書き連ねていこうと思います. C++入門 AtCoder Program...

E以降

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

参考にしたサイト等