AtCoder Beginner Contest 173 備忘録

AtCoder Beginner Contest 173 の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 173 - AtCoder

今回はABCD4完でした。

・A問題:Payment

N円の商品を1000円札のみを使って支払うとお釣りがいくらになるか求める。
Nを1000で割った余りを1000から引けばよい。但し余りが0の場合はぴったり払えたという事なので0を出力する。

解答例(Python)
https://atcoder.jp/contests/abc173/submissions/15019664

・B問題:Judge Status Summary

N個のテストケースに対してジャッジ結果が返されるので "AC","WA","TLE","RE" の個数をそれぞれ数える。
辞書のkeyに各結果を入れて初期化し、入力をkeyとして辞書に個数をカウントする。

解答例(Python)
https://atcoder.jp/contests/abc173/submissions/15020510

・C問題:H and V

H行W列からなるマス目があり、上から i 行目、左から j 行目のマスの色が文字 Cij として与えられ、Cij が ' . ' の時白、' # ' の時黒である。
行を0行以上、列を0列以上選び、選んだ各行、列を赤く塗った時に黒いマスが K 個残るような選び方が何通りか求める。
H,Wがそれぞれ6以下という制約なので各行、列からどの列を選ぶのかを全探索して求めることができる。
今回はbit全探索で求めてみる。行、列に対してそれぞれ0から1<<H、1<<Wまでループを回し各bitが1であれば選んだとして処理する。行、列が選び終わったら更にループを回して各マスが何色かを調べる。選ぶ行のbit集合を i ,列のbit集合を j として、調べる行を l ,列を m とした時に、選んだかどうかは (i>>l)&1 で調べることができる( i>>l で l 行目のbitを1桁目に移動させ、&1 で1かどうかを判定している)。1であればマスは赤なのでカウントせず、0であれば各列を同様に選んだか調べて黒のマス目の数を数えていく。全てのマスを調べ終わったら黒のマスの数が  K と一致していれば ans を増やし選ぶマスを変えてまた調べる。

解答例(Python)
https://atcoder.jp/contests/abc173/submissions/15022924

・D問題:Chat in a Circle

N人のプレイヤーがとある場所を訪れると到着した順に環状に並び、後から来たプレイヤーは好きな位置に割り込んで加わることになった。各プレイヤにはフレンドリーさが設定されており、人 i のフレンドリーさは Ai である。そして、最初に到着した人以外は到着した時点で時計回りか反時計回りで最も近い人のうちフレンドリーさの小さい方に等しい心地よさを感じる。
N 人が到着する順番や割り込む位置を適切に決めた時に、全員の心地よさの合計の最大値を求める。
この時フレンドリーさの小さい方と等しい心地よさを感じ、また最後に訪れるプレイヤーのフレンドリーさは合計に影響しないので、フレンドリーさの大きいプレイヤーから訪れる方が合計を最大化できる。
既に到着しているプレイヤーとその間の数は同じなので到着した時に既に到着しているプレイヤーのフレンドリーさの中央値の心地よさを感じることができるので、2番目以降のプレイヤー全てで求めればよい。

解答例(Python)
https://atcoder.jp/contests/abc173/submissions/15024093