初めての参加
atCoderの過去問や蟻本に多少触れたのち、初めて競技プログラミングというものに参加してみました。
今回参加したのはABC141。
初めてだった今回は4完。
A〜D問題までは1回もWAやTLEを出さずにACを取ることができましたがE問題で詰みました・・・。
初めてということでレートは106だけ上がりました。
CとD問題
今回はC問題とD問題の自分の解答を載せておきます（もちろん最良の方法ではないと思いますが）
競技プログラミング初心者なので非効率な部分が多々あるかと思います。その編はご了承ください。
僕はPython3(PyPy)で解きました。
参考程度に。
C問題
正解するたびにポイントが加算されるのではなく、正解たびに他の全員のポイントが減る方式のクイズ大会。
今回与えられている情報はこんな感じ。
- 参加者はN人
- 最初は全員Kポイント持ってる
- Q回の正解が出た
- i番目に正解したのは参会者$A_i$
- ポイントが0以下になった人は敗退
つまり、もし私が参加していたら、
K - { Q - (自分が正解した回数) } <= 0
なら、自分は敗退するということですね。
n,k,q = map(int,input().split())
a = []
for _ in range(q):
a.append(int(input()))
#番号iの参加者が何回正解したかを格納する配列
b = [0]*n
#番号iの参加者が何回正解したかをカウントしていく
for i in a:
#↑参加者は1〜N番なのに対して、配列は0〜N-1なので、
#b[i-1] += 1というようにしている。
b[i-1] += 1
for i in range(n):
#i番目の参加者が何点引かれるか計算
minus_point = q - b[i]
#それが持ち点（K点）を超えてなければ勝ち
if k - minus_point > 0:
print('Yes')
else:
print('No')
これはfor文が2重、3重になる心配もないので安心して提出できました。
D問題
割引券を駆使してできるだけ安く買い物をする問題。
与えられている情報を軽くまとめておきます。
- N個の商品、全部買う
- i番目に買う商品の値段が$A_i$円
- 割引券をY枚使うと値段Xの商品が$\frac{X}{2^Y}$円になる
「これできるだけで安く買えば良いんでしょ？なら高いやつに1枚1枚割引券を適用すれば良いじゃん」
という安易な発想でプログラムを組みました。つまり、もっと効率的なプログラムは山のようにあると思います。
import heapq
import math
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = [-1*num for num in a]
heapq.heapify(a)
for i in range(m):
#1番高い商品の値段を求める
maximum = heapq.heappop(a)
#割引券により、半額にする
add = math.trunc(maximum/2)
#それをheapqにプッシュする
heapq.heappush(a,add)
#-1をかけることを忘れずに！
print(-1 * sum(a))
ここで大事になってくるのがheapqというモジュール。
これは最大値（最小値）を求めるためのものです。
max(),min()じゃなくてheapqを用いる理由
計算量の違いです。
minやmaxの計算量はO(n)だと思いますが、これをループ毎にやっていると大きい入力があった時に時間がめっちゃかかって時間切れ（TLE）になってしまうと思います。
heapqモジュールは最小値（最大値）を効率的に求めることができるものです。
基本的には最小値を求めるものなのですが、配列の全ての要素に-1をかければ最大値を求めることができます。無理やり感がすごいですが（笑）
では、軽くheapqモジュールにも触れておきます。
参考程度にどうぞ。
import heapq
l = [2,6,1,7,2,5]
#なんか初期化みたいなやつ
heapq.heapify(l)
#リスト内の最小値を求める
minimum = heapq.heappop(l)
print(minimum) #1
#最小値をpopしたので、リストから1が削除されている
print(l) #[2, 2, 5, 7, 6]
#popとは逆にpushもできる
heapq.heappush(l,minimum)
print(l) #[1, 2, 2, 7, 6, 5]
l = [-1*num for num in l]
heapq.heapify(l)
print(l) #[-7,-6,-5,-2,-1,-2]
maximum = -1 * heapq.heappop(l)
print(maximum) #7
なんとなくわかってもらえたら幸いです。
とりあえず、何度もmax()やmin()を使う場合はheapqを考えるというのが良いのかもしれないですね。
まとめ
ABCであれば競技プログラミング初心者でもある程度楽しめることがわかりました。
しかし、今回のABC141はいつもより簡単だったという声が多かったため、たまたまだったのかもしれません。
EとFに関しては何を言っているのかもよくわからなかったですし。
また、PythonはTLEが多いらしいので、C++に変えようか悩んでいます。。。
でも普段使ってる言語がPythonなのでできればPythonを使いたい。。。