AtCoder Beginner Contest 189 備忘録

AtCoder Beginner Contest 189 の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 189 - AtCoder

今回はABC3完でした。

・A問題:Slot

英大文字3文字が与えられ、その3文字が全て同じかどうか判定する。if文で全て同じか調べれば良い。

解答例(Python)
https://atcoder.jp/contests/abc189/submissions/19649016

・B問題:Alcoholic

お酒を N 杯飲み、i  番目に飲んだお酒は Vi ml、アルコール度数が Pi %である。アルコールの摂取量が X mlを越えると酔っ払う。何杯目のお酒を飲んでいるときに酔っ払うか求める。ただし、N 杯全てのお酒を飲んだあとでも酔っ払っていない場合は、かわりに -1 を出力する。
素直に順に足し合わせていき、アルコールの何杯目でアルコールの摂取量が X を越えるか調べれば良いが、1杯毎に Pi / 100 でアルコール量を足していくと少数の計算誤差が発生してしまう為、Vi * Pi を足していき X と比較するときに 100 で割ってアルコール量を求めることに注意する。

解答例(Python)
https://atcoder.jp/contests/abc189/submissions/19648873

・C問題:Mandarin Orange

N 枚の皿が一列に並べられており、左から i 番目の皿には Ai 個のみかんが置かれている。次の3つの条件を全て満たすような整数の組 ( l , r , x ) を1つ選ぶ。

　・1 ≦ l ≦ r ≦ N
　・1 ≦ x
　・l 以上 r 以下の全ての整数 i について、x ≦ Ai

その後、l 番目から r 番目までの全ての皿からみかんを x 個ずつ取って食べる。整数の組 ( l , r , x ) を適切に選んだときに、最大で何個のみかんを食べることができるか求める。
まずは l の位置をループで回し、各 l の時に r を選択する位置をループで回す。その区間の中で最も少ないものを x として、選ぶ皿の枚数は l - r + 1 なのでそれらを掛けたものがその区間を選んだときに食べられるみかんの個数になる。l を固定して r についてループで順に回していくのでその区間での最小値は、累積minで求められるので O(N^2) の計算量になる。
ただし、制限時間は 1.5 secの為PythonではTLEしてしまったので、PyPy3で提出した。

解答例(PyPy3)
https://atcoder.jp/contests/abc189/submissions/19648323