AtCoder ABC193振り返り(灰コーダー AB2完)

注意：この記事は競プロ初心者が茶色を目指すために復習や反省するだけの記事です。使用言語はPython3で現状のパフォーマンスは200-400程度です。
あくまで自分の備忘録ですが同レベルの方の新しい発見に繋がれば嬉しいです。

#結果
A問題 正解
B問題 正解
C問題 大まかな形までは作れた
D問題以降 考える時間なし

#B問題

B.py

N=int(input())
data=[]
c=0
for i in range(N):
    data.append(input().split())
#dataに[時間　値段　個数]を各パターン入れた二次元配列
m=[-1]
for i in data:
    #売り切れるかどうか
    if int(i[2])-int(i[0])>0:
        #買えるならmに値段を代入
        m.append(int(i[1]))
#mをソートして結果を出力
ans=sorted(m)
if len(ans)>1:
    print(ans[1])
else:
    print(ans[0])

購入できないなら-1を返却とのことだったので購入可能な場合の料金を入れる配列に-1を入れておいた。
入力値がすべて整数との規定があったため0.5分,1.5分,2.5分...と1台ずつ減る場合でも複雑なことを考えずに1分経過なら1台、2分経過なら2台と減ることに少し考えてから気が付いた。
配列に購入可能時の値段をすべて入れソートしたが、値段の最小値min=-1を定義して購入可能時に毎回比較すほうが一般的で簡単だったと思う。

#C問題

数値Nが与えられa^bで表せない数値がN以下に何個あるか求める問題。

思考1
2^2～N^Nまで計算して配列に突っ込む。
(かぶりがあることを見逃していた)
思考2
1～Nまでが入っている配列を用意する。
配列内を二分探索してa^bが配列内にあればdelで消す。
(計算量がオーバー)

思考1.2で被りを気にして計算量が大きく増えた。
回答においてsetの存在を知った。setを使えばN以下のa^bをひたすらsetに追加していけばよかった。

C.py

N=int(input())
s=set()

for a in range(2,N+1):
    if a*a>N:
        break
    for b in range(2,N):
        x=a**b
        if x<=N:
            s.add(x)
        else:
            break

print(N-len(s))

#身についたこと
・setの存在
要素に重複のないリストのようなもの。リストのように順番は保存できない。listなどに変換も可能。

・計算量の大まかな限界
N=10^10の可能性がある時、計算量の都合から競プロでは力任せに1～Nまで求めることはできない。