AtCoder Beginner Contest 190 備忘録

AtCoder Beginner Contest 190 の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 190 - AtCoder

今回はABCD4完でした。

・A問題:Very Very Primitive Game

T君とA君がそれぞれA個、B個の飴を持っている。
C が 0 ならばT君が先手、1 ならばA君が先手で交互に飴を1つ食べる。先に飴を食べられなくなった者の負けになる。どちらが勝つか求める。
飴の個数が違う場合は、最初に持っている飴の個数の多い方の勝ちになる。同じ場合は後に食べる方の勝ちになる。

解答例(Python)
https://atcoder.jp/contests/abc190/submissions/19822470

・B問題:Magic 3

N 種類の魔法を使うことができ、i 番目の魔法は詠唱に Xi 秒かかり、威力は Yi である。相手には魔法以外の方法でダメージを与えることはできず、また詠唱に S 秒以上かかる魔法や、威力が D 以下の魔法でもダメージを与えることができない。相手にダメージを与えられるか求める。
各魔法について、Xi < S、Yi > D を満たすか調べ、満たすものがあれば "Yes" を出力、なければ "No" を出力する。

解答例(Python)
https://atcoder.jp/contests/abc190/submissions/19822341

・C問題:Bowls and Dishes

1,2,...,N の番号がついた N 枚の皿と、 1,2,...,M の番号がついた M 個の条件がある。条件 i は、皿 Ai と皿 Bi の両方にボールが1個以上置かれているとき満たされる。1,2,...,K の番号がついた K 人の人がいて、人 i は皿 Ci か皿 Di のどちらか一方にボールを置く。満たされる条件の最大の個数を求める。
K ≦ 16 と小さいので人 i がどちらの皿にボールを置くかを全探索して満たす条件の個数を調べることで求めることができる。
全探索をする方法はいくつかあるが、今回はDFSを用いて解いた。

解答例(Python)
https://atcoder.jp/contests/abc190/submissions/19822149

・D問題:Staircase Sequences

整数からなる公差 1 の等差数列のうち、総和が N であるものの個数を求める。
N ≦ 10^12 と非常に大きい為、効率よく調べる必要がある。まずは探索範囲を絞ることを考える。等差数列の要素が [ N ] の場合、それだけで総和が N となる。また等差数列の和を N にするには N - (数列の中央値) が数列の中央値の2倍した値の倍数になっている必要がある為、N の約数を求めて各約数について前記の式を満たすか調べることで求めることができる。また、ここまでに求めた各数列の最初の値を X として、X-1 から - ( X - 1 ) の総和が 0 になることから各数列に X-1 から - ( X - 1 ) を加えたものも同様に満たすことになるので、最後に求めた答えの個数を2倍にする必要がある。

解答例(Python)
https://atcoder.jp/contests/abc190/submissions/19821224