AtCoder Beginner Contest (ABC) １９３ A,B,C問題解いてみた
前回解いたやつ
こんにちは。メリーです。
最近一気に寒くなって来ましたね。
半袖で窓を開けると風が入って来て寒いけど、 開けなかったら暑いという微妙な室内温度です・・・。
バイト代がそれなりに入ったので、新しくiPadを買おうかなと模索中・・・
新型いつ出るんでしょうね。
新型出るまで待つか、既存のやつを買うか・・・
悩みます。
家でゴロゴロするときに使いたいのでWi-Fiの方でいいよね、多分。
そんなわけで今日はキャディプログラミングコンテスト2021（AtCoder Beginner Contest (ABC) １９3）の問題を解いていきました。
言語はPyhon 、提出はPyPyです。
目次
A問題
問題文
BはAの何％引きかを出力する問題。
小学校の算数のときにやりましたね。
多分、これ公式的なものを暗記したほうが早いんでしょうけど、僕は暗記が嫌いなので、 こういう問題を解くときは毎回、比で考えてます。
この問題の場合は
A(円) : B(円) = 100(%) : x(%) A * x = 100 * B x = 100 * B / A ans(%) = 100 - x
って感じで計算しました。
xはBがAの何％かって値です。
xを使わない場合は、
A(円) : A - B(円) = 100(%) : ans(%) ans = (A-B) * 100 / A
で一気に出ます。
僕は主義主張の問題で、最初の比にA-Bが出てくるのが気持ち悪いのでｘ使います。
というわけで、書いたコードがこちら
a,b = map(int,input().split()) print(100-((b*100)/a))
これで簡単にACでました。
B問題
問題文
ゲームをショップに買いに行ったときに買えるかどうか、また買える場合は最安値がいくらかを答える問題ですね。
今時ゲームが欲しい場合はダウンロード版で簡単に確実にゲットできるので便利になりましたよね。
僕も大学２年生くらい（２年前くらい）からはダウンロード版メインで買ってます。 家から出なくて買うことができるのが最高なんですよね・・・。
クレジットカード無くても、デビットカードとか、PayPal使えば借金しないのでおすすめです。
本題に入ります。
B問題なので全探索で解けます。
今回の問題では、全てのお店のパターンを調べて、各お店で在庫が残っているかチェック。その後、在庫がある場合は金額を記録する。という流れで正解できます。
一応、AtCoderではループ回数が109くらいまでは回せるらしいので、それをチェック。
今回の問題では、
N < 105
なので問題ないことも確認できます。
で、在庫が残ってるかどうか判定なんですけど、
Xi - Ai で在庫数が出ます。
在庫数は１分ごとに１減るのでこれで問題ないです。
というわけで僕の回答です。
n = int(input())
store = []
for i in range(n):
a,p,x = map(int,input().split())
store.append([a,p,x])
ans = float('inf')
for i in range(n):
stock = store[i][2] - store[i][0]
if stock > 0:
ans = min(ans,store[i][1])
if ans == float('inf'):
ans = -1
print(ans)
ans = float('inf')
でansに無限大を格納できます。
今回は最小値を答えるので、毎ループごとにansの値を更新します。そのときに都合が良いので無限大を格納します。
配列storeは、
store[i][Ai,Pi,Xi]
という形になってます。
なので、store[0][0]だと、１店舗目の徒歩何分かを表しています。
最後のif文で、
ansが初期値から更新できてない＝ゲームを買えない
ということなので、
ansの値を-1 に変更します。
最後にansを出力して終わりです。
C問題 試行錯誤編
問題文
この問題自力では解けなかったです。
アプローチは結構いいとこまで行ってたんだけどなぁ
1からNまでの整数で、何とかの何乗で表せない整数は何個あるのか答える問題。
サンプルケース１を見るからに、a = b でも可能。
まあ、ダメ元で全探索的な感じでアプローチするか~~
と考え、すこ〜〜〜〜しループ回数に気をつけたコードがこちら
n = int(input())
ans = n
for i in range(2,n//2+1):
for j in range(2,n):
if i**j <= n:
ans -= 1
else:
break
print(ans)
はい、まぁ、余裕でTLEだった訳なのですが・・・
このコードは、abのaをi、bをjがやってる感じです。
ijがNより小さければansから−１していきます。
ansは定義時にNで初期化してます。
ループ回数に気をつけたのはこの部分！！！
for i in range(2,n//2+1):
まぁ、最大値を２で割ったくらいまでループ回せば、その後のループで答えでることないやろって思ったので。
実際、 N = 4の時、最大でも22なので、そんなもんかなぁって思ってやりました。
※回答編ではもっとスマートな範囲が出てきます。お楽しみに。
まぁ、サンプルくらいは全部AC出るっしょ！
と思いサンプルを実行してみるも、サンプル２で結果が違う！！！なぜだ！！！
という感じでもうアプローチが思いつかなかったので、解説を見ることに・・・
C問題 回答編
いきなりコード！！！！
n = int(input())
ans = set()
for i in range(2,int(n**0.5+1)):
x = i*i
while x <= n:
ans.add(x)
x *= i
print(n-len(ans))
試行錯誤編で全く触れてなかった点で、サンプル２の回答が違っていた原因はこいつだ！！！！
ans = set()
こいつのなにが問題なのかというと、 こいつを入れなかったせいで、
i = 2, j = 4の時 24 = 16
i = 4, j = 2の時 42 = 16
二重に計上していたのだ！！！！
全く気が付かなかった！！！
というわけでそれを修正。
それともう２つ。
１つめはループの範囲。
至極当然のこととして、２乗してNとなる値は√Nである。
そして、それはN0.5
でもある！！！
ということで範囲は２ ~ N0.5 + 1 までということである。
く”や”し”い”
２つ目はループの回しかた。
jを作る必要はなかったのです。
jが増える = i をかける
ということです！！
ansをカウントした後にiをかければよかったのです・・・
く”や”し”い”（２回目）
こういうところに気がつけるようになると効率の良いプログラムが書けるのだろうなぁとおもいました。
明日も頑張るぞい。
それでは。
