AtCoder Beginner Contest 185 備忘録

AtCoder Beginner Contest 185 の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 185 - AtCoder

今回はABCD4完でした。

・A問題:ABC Preparation

100点、200点、300点、400点の問題がそれぞれ A1,A2,A3,A4 個あり、各点数の問題を1問ずつ使ってコンテストを開く。このとき何回コンテストを開く事ができるか求める。ただし、1度使った問題は使用する事ができない。
コンテスト1回につき各点数の問題を1問消費するので、各点数の問題数のうちもっとも少ない問題数が答えとなる。

解答例(Python)
https://atcoder.jp/contests/abc185/submissions/18765462

・B問題:Smartphone Addiction

スマートフォンのバッテリー容量は N [mAh]であり、時刻 N+0.5 ( n は整数)になる度にバッテリー残量が 1 [mAh]ずつ減少する。
スマートフォンを満充電した状態で時刻 0 に外出する。途中で M 回時刻 Ai から時刻 Bi まで充電し、その間はバッテリー残量は減少せず、代わりに時刻 n+0.5 ( n は整数)になる度にバッテリー残量が 1 [mAh]増加する。ただし、バッテリー容量を超えて充電することはできない。そして時刻 T に帰宅する。
外出中にバッテリー残量が 0 になることなく帰宅する事ができるか判定する。
バッテリーの消費量は充電を始める時刻 Ai から前回充電を終えた時刻 A(i-1)の差で求める事ができ、また充電量も同様に充電を終えた時刻 Bi から充電を始めた時刻 Ai の差で求める事ができるので残量の消費と増加はそれぞれ O(1) で計算できる為、M≦1000 から全てシミュレーションする事で判定する事ができる。

解答例(Python)
https://atcoder.jp/contests/abc185/submissions/18765376

・C問題:Duodecim Ferra

長さ L の棒があり、この棒を11箇所で切断して12本に分割する。この時分割後の各棒の長さが全て正整数になるように分割しなければならない。このような分割の仕方が何通りあるか求める。
このような N 個のものを R 個に分割するというような組み合わせの数を求めるには、n! / (r! * (n - r)!) で求める事ができる。Pythonでは階乗は math.factorial() で求める事ができる。

解答例(Python)
https://atcoder.jp/contests/abc185/submissions/18765098

・D問題:Stamp

N 個のマスが1列に並んでおり、左から i 番目のマスをマス i と呼ぶことにする。この N 個のマスのうち、マス A1,A2,A3…,AM の M 個のマスは青色で、それ以外のマスは白色である。1度だけ正整数 k を一つ選んで幅 k のハンコを作る。そのハンコを1回使用すると N 個のマスのうち連続する k マスを選び、それらを赤色に塗り替える事ができる。ただし塗り替えるマスに青色のマスが入ってはいけない。
k とハンコの使用方法をうまく決めた時、最小で何回ハンコを使用すれば、白色のマスが存在しない状態にできるか求める。
まず k をどうするか考える。k 個の連続したマスを塗り替えられるが、その中に青色のマスが入ってはいけない為、白色のマスが連続する区間のうちもっとも短いものを k とするのがよい。k が決まればあとは白色のマスが連続する区間をそれぞれ何回で塗り替える事ができるか計算していき、その合計を出力すれば良い。

解答例(Python)
https://atcoder.jp/contests/abc185/submissions/18764901