AtCoder Beginner Contest 187 備忘録

AtCoder Beginner Contest 187の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 187 - AtCoder

今回はABCD4完でした。

・A問題:Large Digits

整数 n に対して、n を十進法で表した時の各桁の和を S(n) で表すとする。例えば S(123) = 1 + 2 + 3 = 6 となる。
2つの3桁の整数 A,B が与えられるので、S(A) と S(B) のうち大きい方の値を求める。
各桁の値はそれぞれ 100 で割り切り捨て、100 で割った余りから 10 で割り切り捨て、10 で割った余りで求める事ができる。A,Bそれぞれ求めて大きい方の値を出力すれば良い。

解答例(Python)
https://atcoder.jp/contests/abc187/submissions/19164321

・B問題:Gentle Pairs

xy平面状に1,2,...,N の番号がついた N 個の点があり、N 個の点の x 座標は互いに異なる。
点 i と点 j を通る直線の傾きが -1 以上 1 以下である点の組の個数を求める。
直線の傾きは ( y [ j ] - y [ i] ) / (x [ j ] - x [ i ] )で求める事ができるので、全ての点の組に対してこの値が -1 以上 1 以下か判定し数える事で求める事ができる。

解答例(Python)
https://atcoder.jp/contests/abc187/submissions/19164161

・C問題:1-SAT

n 個の文字列 S1,S2,...Sn が与えられる。各文字列は、英小文字からなるから出ない文字列の先頭に ! を 0 文字か 1文字付加したものである。文字列 T は、T の先頭に ! を０文字付加しても 1 文字付加しても S1,S2,...Sn のいずれかに一致する時、不満な文字列である。不満な文字列があるかどうか判定し、あれば 1 つ出力する。
付加してもしなくても不満な文字列になる為には、文字列 S に文字列 T とその頭に ! を加えた文字列の両方が含まれている必要がある。なので ! の付かない文字列をキーとして ! の付かない文字列と付く文字列の有無を持った辞書を作り、両方存在する文字列が存在すればその文字列を出力する。存在しない場合は satisfiable と出力する。

解答例(Python)
https://atcoder.jp/contests/abc187/submissions/19164492

・D問題:Choose Me

ある市で市長選挙がある。N 個の町があり、i 番目の町には K 派の人間が Ai 人、T 派の人間が Bi 人存在する。T 氏は、それぞれの町で演説を行う事ができる。ある町で演説を行うと、その町の人間は全員 T 氏に投票する。一方、T 氏が演説を行わなかった場合、その町の K 派の人間は全員 K 氏に投票し、T 派の人間は投票に行かない。T 氏が K 氏より多く票を獲得する為には、最小で幾つの町で演説をする必要があるか求める。
N ≦ 2 * 10 ^ 5 なので全ての町で演説をするかどうかを調べることはできない。なので演説をする事で得られる票の多い順にソートし、K 派の票の総数を求めておき、順番に票を計算していき T 氏の票数が K 氏を上回った時の回数を出力すればよい。ただし、ソートする際には単純な得られる票でソートするのではなく、得られる票 + 相手の失う票で並べ替える必要がある。

解答例(Python)
https://atcoder.jp/contests/abc187/submissions/19163611