AtCoder Beginner Contest 194 備忘録

AtCoder Beginner Contest 194 の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 194 - AtCoder

今回はABCD4完でした。

・A問題:I Scream

日本において、アイス製品は以下のように大別される。

・乳固形分が15％以上、乳脂肪分が8％以上含まれるものを「アイスクリーム」とする。
・上に当てはまらず、乳固形分が10％以上、乳脂肪分が3％以上含まれるものを「アイスミルク」とする。
・上のいずれにも当てはまらず、乳固形分が3％以上含まれるものを「ラクトアイス」とする。
・上のいずれにも当てはまららないものを「氷菓」とする。

ここで、乳固形分は無脂乳固形分と乳脂肪分の2つから成る。
ある製品には、無脂乳固形分は A ％、乳脂肪分は B ％含まれている。
上の分類を適用したとすると、4種類のどれに当てはまるか求める。
乳固形分と乳脂肪分のそれぞれの条件を満たすか上から順に見ていき、満たしたものを出力すればよい。ただし、出力は上から順に 1 , 2 , 3 , 4 となっていることに注意する。

解答例(Python)
https://atcoder.jp/contests/abc194/submissions/20734506

・B問題:Job Assignment

ある会社には従業員 1 から従業員 N までの N 人の従業員がいる。その会社で仕事 A と仕事 B の2つの仕事を受注したので、これらを完了しなければならない。従業員 i は仕事 A を Ai 分、仕事 B を Bi 分でこなすことができる。
仕事 A と仕事 B にそれぞれ従業員を1人割り当てる。同じ従業員に両方の仕事を割り当ててもよいが、その場合2つの仕事が終わるのにかかる時間は、それぞれの仕事が終わるのにかかる時間の和となる。
仕事 A と仕事 B に異なる従業員を割り当てた場合、2つの仕事が終わるのにかかる時間は、隠し事が終わるのにかかる時間の長い方となる。
2つの仕事が終わるのにかかる時間として考えられる最小値を求める。
仕事 A と仕事 B をそれぞれソートし、もっとも早く仕事が終わる従業員をしらべ、その従業員が違う人間ならばどちらか長い方が答えとなる。もし同じ従業員であれば A と B の合計か、A の1番目と B の2番目、A の2番目と B の1番目のうちもっとも短いものが答えとなる。

解答例(Python)
https://atcoder.jp/contests/abc194/submissions/20734408

・C問題:Squared Error

長さ N の数列 A が与えられる。各要素同士の差の2乗の和を求める。
N≦3*10^5 から、全ての組み合わせを試すと N^2 程度の計算量となってしまう為間に合わない。しかし、| Ai |≦200なので、Ai の要素を辞書にまとめておいて要素の組み合わせで計算することで、最大でも 400^2 程度の計算量で求めることができる。ある2要素の差の2乗にそれぞれの要素数の積を掛けたものを足し合わせることで答えを求めることができる。

解答例(Python)
https://atcoder.jp/contests/abc194/submissions/20734026

・D問題:Journey

頂点 1 から頂点 N までの N 頂点からなるグラフの頂点 1 にいる。今このグラフには辺は1つも張られていない。
この状態から以下の操作を繰り返す。
・今いる頂点も含めた N 個の頂点の中から1つランダムに選ぶ。各頂点が選ばれる確率は全て 1 / N であり、選択は操作毎に独立である。
・今いる頂点と選ばれた頂点の間に無向辺を張り、選ばれた頂点に移動する。
グラフが連結になるまでに行われる操作回数の期待値を求める。
全ての頂点の中から1つ選んでいき、全ての頂点を選ぶまでの期待値は N(1+1/2+1/3+...+1/N) で求めることができる(これはコンプガチャ・確率でググるとすぐに出てくる)。ただし今回の場合頂点 1 は既に選ばれている状態から始まる為、1 / N までではなく 1 / (N - 1) までを計算すればよい。

解答例(Python)
https://atcoder.jp/contests/abc194/submissions/20733621