ABC193参戦記

ブログ記事として投稿するのが遅くなりましたが、ABC193の参戦記です。

茶色の中位から下位程度の私が、私が理解したことをアウトプットする内容です。
厳密性などに書ける部分があると思います。

使用言語はPython3です。

ちなみに、今回のコンテストはキャディ株式会社さんが主催してくれています。

A – Discount

割合の計算が出来るかを問われる問題。

空で計算式の変形が出来なくて、ノートに計算式を書いていきました。

# キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)
# A - Discount

A,B=map(int,input().split())
ans=100-((B/A)*100)

print(ans)

B – Play Snuke

繰り返し処理が書けるか、条件分岐が書けるかを問われる問題。

それぞれのiについて、XからAを引いたときに、1以上であれば条件を満たして、
Pと今までのPの最低値を比較してより低ければPを更新していく。
最後に、最低値を出力すればOKです。

もしも、1つも条件を満たすものがなければ、-1を出力すればOKです。

# キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)
# B - Play Snuke

N=int(input())

ans=10**9+7

for i in range (N):
    a,p,x=map(int,input().split())
    if x-a>0:
        ans=min(ans,p)

if ans==10**9+7:
    ans=-1

print(ans)

C – Unexpressed

数学的な考察と、set が使えるかを問われる問題。

すぐに思いつくのは、Nまでの各数字を素因数分解して、a**bと表せないかを確認していく方法だと思います。
しかし、これだとN=10**10の場合は計算量が多くなりTLEします。
Pythonだと、10**7あたりがTLEしない計算量だと思っておけば良いようです。
(処理が軽ければ10**8も、可能なようです。あとは、Pypyを利用すればPythonよりも実行時間は短くなります。)

ここは逆転の発想で、2以上の整数 a , b を用いて、a**b で表せる数字を、Nから引いて考えるようにすればOKと考えます。
a**bと表せる数を数えるには、a**b<=N になっているかを判定します。

探索する範囲は、
a は大体、<N**0.5 までであり、
b は 34 までです。

# print(10**10)   >> 10000000000
# print(2**34)    >> 17179869184
# print(3**34)    >> 16677181699666569
# print(4**34)    >> 295147905179352825856

こうして a**b となる数を全探索して、それらの数をNから引いた数が答えかというと少し違ってて、

a=2,b=4 の場合、2**4=16
a=4,b=2 の場合、4**2=16

と、aとbの組み合わせが異なる場合でも計算結果が同じになる場合があることがわかります。
この重複分をうまく除くには、Python3の set が便利です。

Python3の set には、同じ数字をこのデータ構造に入れても、重複している分は勝手に省いてくれるため、この set にどんどん計算結果を追加していけばOKです。

Nよりも大きい数字になった場合は、for文を抜けるようにしたほうが計算量的に安全です。
(一応抜けなくれもTLEしなさそうではありますが。)

あとは、set に入っているデータの個数をNから引けばACします。

# キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)
# C - Unexpressed

N=int(input())

R=int(N**0.5)+1
Nums=set()

for i in range (2,R):
    for j in range (2,34):
        num=i**j
        if num<=N:
            Nums.add(num)
        else:
            break

print(N-len(Nums))

この問題、コンテスト中にACしたのですが、前回のABC192-Dのイメージが強すぎて、bの範囲を二分探索で求めるという無駄なことをしていました。