AtCoder Beginner Contest 159 備忘録

AtCoder Beginner Contest 159の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 159 - AtCoder

今回はABCD4完でした。

・A問題:The Number of Even Pairs

n個の偶数が書かれたボールとm個の奇数が書かれたボールがあり、そこから2個選んだ時に偶数になるような選び方の個数を求める。
n+m個のボールから2個選んで偶数になるのは

・偶数+偶数
・奇数+奇数

の時だけなので、n個から2個とm個から2個選んだ時の合計になる。
n個から2個選ぶ組み合わせの数は、

・n * (n - 1) / 2

で求められる。

解答例(Python)
https://atcoder.jp/contests/abc159/submissions/11160588

・B問題:String Palindrome

文字列 S が与えられるので、Sが回文かつ前半と後半もそれぞれ回文か判定する。
但しSが回文でかつ前半が回文であれば、後半も回文であることが確定するので判定は2回すればよい。

解答例(Python)
https://atcoder.jp/contests/abc159/submissions/11160923

・C問題:Maximum Volume

正の整数 L が与えられる。3辺の長さの合計がLとなる直方体の体積の最大値を求める。
体積が最大になるのは1辺がL/3の時なので、(L/3)^3が答えとなる。

解答例(Python)
https://atcoder.jp/contests/abc159/submissions/11161113

・D問題:Banned K

N個のボールがあり、i番目のボールには整数Aiが書かれている。
N個の各ボールを選ばない時に同じ数字の書かれたボールの選び方の個数を求める。
辞書に書かれた数字とボールの数を記録し、i番目のボールを選ばない時Aiのボールの数を-1した組み合わせの数と他の各数字のボールの組み合わせの数を合計したものが答えとなる。
但し、制約がNが10^5以下、AiはN(最大10^5)以下なので都度計算していたのでは間に合わない。
そこでまず全て選べる時の組み合わせの数と各数字を選ばない時に組み合わせがいくつ減るかを求めておき、全体から各数字の減る量を引いて出力する。

解答例(Python)
https://atcoder.jp/contests/abc159/submissions/11161620