【Atcoder Beginner Contest】ABC193に参加しました。

AtCoder Beginner Contest 193に参加しました。

A問題

提出コード

A,B=map(float,input().split())
S = abs(A-B) #A-Bの絶対値
X = max(A,B) #
P = S/X
C = P*100
print(C)

A,B=map(float,input().split())

S = abs(A-B) #A-Bの絶対値

X = max(A,B) #

P = S/X

C = P*100

print(C)

修正コード

A,B=map(float,input().split())
print(((abs(A-B))/A)*100)

1 2	A,B=map(float,input().split()) print(((abs(A-B))/A)*100)

行数を減らしてみました。見やすさはあまり変わらない。

他の方が見ても一発でよくわかるように綺麗に書きたい。

B問題

提出コード(AC)

N = int(input())
A = []
P = []
X = []
S = []
for i in range(N):
  a,p,x = map(int,input().split())
  A.append(a)
  P.append(p)
  X.append(x)
  if x-a>0:
    S.append(p)
 
if S == []:
  print(-1)
else:
  print(min(S))

N = int(input())

A = []

P = []

X = []

S = []

for i in range(N):

a,p,x = map(int,input().split())

A.append(a)

P.append(p)

X.append(x)

if x-a>0:

S.append(p)

if S == []:

print(-1)

else:

print(min(S))

早く解かないとという焦りで意味のない部分が多いですが、恥を忍んで書き残しておこうと思います。

修正コード(AC)

N = int(input())
S = []
for i in range(N):
  a,p,x = map(int,input().split())　#a：経過時間=在庫が減った個数, p：価格, x：在庫
  if x-a>0: #まだ在庫があれば
    S.append(p) #その店の価格をSに追加
if S == []: #すべての店で在庫がない場合
  print(-1) #-1を出力
else: #そうでなければ
  print(min(S)) #Sの要素の中で最小値、つまり最も値段の低い価格を出力

N = int(input())

S = []

for i in range(N):

a,p,x = map(int,input().split())　#a：経過時間=在庫が減った個数, p：価格, x：在庫

if x-a>0: #まだ在庫があれば

S.append(p) #その店の価格をSに追加

if S == []: #すべての店で在庫がない場合

print(-1) #-1を出力

else: #そうでなければ

print(min(S)) #Sの要素の中で最小値、つまり最も値段の低い価格を出力

自分なりに無駄な部分を削ぎ落してみました。

問題文には0.5分、1.5分、2.5分・・・とあり、どうすれば良いのか迷いましたが、

切り上げてしまって1分、2分、3分としても良いのでは？と思い安直に1分毎に在庫が1個減るものだと考えました。(x-a)

ACにはなっていますが、あまりよくない考え方のような気がします。

C問題：Unexpressed

公式解説

N = int(input())
sq = int(N**0.5) #平方根を求める
S = set() #SetオブジェクトSを用意
for a in range(2, sq+1):
    x = a*a
    while x <= N:
        s.add(x) #sにxの値を追加(重複は無視される)
        x *= a  #x = x*a と同じ
print(N-len(s))

N = int(input())

sq = int(N**0.5) #平方根を求める

S = set() #SetオブジェクトSを用意

for a in range(2, sq+1):

x = a*a

while x <= N:

s.add(x) #sにxの値を追加(重複は無視される)

x *= a #x = x*a と同じ

print(N-len(s))

作成コード

参加中の作成コード(未提出)

N = int(input())
S = 0
for i in range(2,N):
  for j in range(2,50):
    if N >= i**j >=1:
      S = S + 1
#      print(i**j,i,j)
    if i**j >N:
      break
print(abs(N-S))

N = int(input())

S = 0

for i in range(2,N):

for j in range(2,50):

if N >= i**j >=1:

S = S + 1

# print(i**j,i,j)

if i**j >N:

break

print(abs(N-S))

100000の入力の時に99593という出力になり、結果が合わず解答できませんでした。

修正コード

N = int(input())
S = set()
for i in range(2,N):
  for j in range(2,50):
    if N >= i**j >=1:
      S.add(i**j)
#      print(i**j,i,j)
    if i**j >N:
      break
print(abs(N-len(S)))

N = int(input())

S = set()

for i in range(2,N):

for j in range(2,50):

if N >= i**j >=1:

S.add(i**j)

# print(i**j,i,j)

if i**j >N:

break

print(abs(N-len(S)))

これだと入力例2はクリアできましたが、提出するとTLEになりました。

計算量を確認するのはこういうことがあるからだと身をもって感じることができます。

ACコード(終了後)

N = int(input())
S = set()
T = round(N**0.5)
for i in range(2,T+1):
  for j in range(2,T+1):
    if N >= i**j >=1:
      S.add(i**j)
    if i**j > N:
      break
print(N-len(S))

N = int(input())

S = set()

T = round(N**0.5)

for i in range(2,T+1):

for j in range(2,T+1):

if N >= i**j >=1:

S.add(i**j)

if i**j > N:

break

print(N-len(S))

計算の範囲がNの平方根までで良い理由という解説があるのですが、理由を理解できていません。

入力例1だと8が入力されますが、その平方根は2.828・・・です。

Nの平方根までの計算だと2**3=8が抜けてしまうのではないかと思い、腹落ちしていない。。。

平方根を求める

n = 4
print(4**0.5)
#2

n = 4

print(4**0.5)

平方根の求め方を知りませんでした。

次に出てきたときに使えるように書き残しておきます。

Set

pythonのSetは集合を扱うための型。

複数の値を格納できる。
重複した要素がない
要素に順番がない
Setに重複した要素を入れても、重複した要素は削除されて一意の値のみが残る
集合演算(和集合、積集合、差集合)ができる

要素の追加

#変数.add(追加する要素)
X = set([1,2,3])
X.add(4)

#変数.add(追加する要素)

X = set([1,2,3])

X.add(4)

addメソッドで追加できる。

要素の削除

値を指定して要素を削除

X = set([1,2,3,4])
X.remove(1)

1 2	X = set([1,2,3,4]) X.remove(1)

removeメソッドで削除できる。

全ての要素を削除

X = Set([1,2,3,4])
X.clear()

1 2	X = Set([1,2,3,4]) X.clear()

clearメソッドで削除できる。

集合演算

2つのSet型オブジェクトに対して集合演算を行うことができる。

以下は各演算とその演算をするためのメソッド

・和集合：union　もしくは　|

→すべての要素を含む

・積集合：intersection　もしくは　&　(アンパサンド)

→どちらにも存在する要素のみ含む

・差集合：difference もしくは　-

→一方のオブジェクト(A)から、もう一方のオブジェクト(B)ともう一方との共通する要素(A&B)を除いた要素を含む

・排他的論理和：symmetric_difference　もしくは　^

→2つのSetオブジェクトの和集合(A | B)から、要素(A & B)のみを除いた要素を含む

結果と振り返り

結果はB問題までの正解で終わりました。C問題はもう少しで解けそうな気はしたのですが、

解くことができず、かなり悔しい思いをしました。レーティングは少し上昇しましたが、次は時間いっぱい使って3完を目指します。

C問題が正解できなかったのは重複する整数があったことを見落としていたからでした。

終了後に2^4=4^2=16のように重複する整数があることには気が付きましたが、a^bとなる組み合わせの数を調べるのではなく、a^bと表せる整数の個数を数える必要があることになぜか納得できず悶々としていました。

公式の解説にSetが出ていたので調べてみました。Setを使うと重複した要素を無視してくれるので、今回のC問題はa^bで表せる整数をSetオブジェクトに加えていき、最後にその要素数をNから引けば良いということだったのですね。

また、10^10を計算するには時間が足らないため、計算量を減らすことが必要になるようでした。

次回はC問題まで解けるようにしたいです。今週はC問題を集中して練習しようと思います。