ABC182参戦記

金、土、日となかなかハードなスケジュールをこなして迎えたABC182の参戦記です。

一番の疲労の原因は市民農園の玉ねぎの植え付け！今年もいっぱい収穫して楽しみました。
来年も家族で玉ねぎパーティーできるようにたくさん植えてきました！自分で植えると市中にはあまり出回らない葉玉ねぎを思う存分楽しめるのが良いですね。
もうちょっとスペース空いてるから追加で植え付けしようかと迷い中です。

そんなこんなで、家庭菜園が趣味の非ITエンジニアが趣味で競技プログラミングの解説をするブログ記事です。
ちょっと前のARCで茶色になりましたが、前回のABCでちょっとレートを落としてしまい、今回もパフォーマンスが良くないと灰色に戻ってしまいそうです。
毎回ABCのC問題が解けるか解けないか位の私がPython3でのACコード付きで書いていきます。

A – twiblr

標準入出力と四則演算ができるかを問われる問題。

標準入力が1行に2つの値があるのは、慣れるまで大変でしたが、これは慣れるしかないですね。

計算式自体はそんなに難しいことはないと思います。

# AtCoder Beginner Contest 182
# A - twiblr

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

print(ans)

B – Almost GCD

与えられた数列の各要素をより多く割り切れるような2以上の数を調べたい。

問題文を読んで初めの内は意味が分からなかったです。入力例を見てからしばらく考えてからようやく理解できました。

調べる数kを2から数列の最大値まで全探索して、各数列の要素で割り切れるかを確認すればOKですね。

二重のfor文で実装出来ます。
先週のABCのB問題で二重のfor文書いてTLE出したので、計算量も計算して大丈夫なことを確認しました。

答えをどうやって保持しておくかですが、kで割り切れた数をカウントして、現在のGCD度と比較して大きければkを暫定の答えに書き換えるのが良いかと思います。

# AtCoder Beginner Contest 182
# B - Almost GCD

N=int(input())
Als=list(map(int,input().split()))

ans=-1
kValue=-1

# for文のrangeに注意！2から開始。終了はmax(Als)なので、+1
for k in range (2,max(Als)+1):
    count=0
    for a in Als:
        if a%k==0:
            count+=1
    if count >ans:
        ans=count
        kValue=k

print(kValue)

私は問題文を読んでよくわからずに、入力例を読んでもよくわからずに迷走したため、各ｋのGCD度をメモする配列を作成して、その配列のMAXのインデックスを取得する。という変なことをしました。

# AtCoder Beginner Contest 182
# B - Almost GCD

N=int(input())
Als=list(map(int,input().split()))

ansls=[0]*(max(Als)+1)

for i in range (N):
    for j in range (2,max(Als)+1):
        if Als[i]%j==0:
            ansls[j]+=1

maxG=max(ansls)

ans=ansls.index(maxG)
print(ans)

答えの経過をメモする用の配列とかを利用するのも良いのですが、今回の問題に関して言えば、不要でしたね。。。

C – To 3

3の倍数判定の問題。

3の倍数判定は、各桁の総和が3の倍数であればOKです。
数学的な証明については、今回もこちらのサイトや数学ガール秘密のノートでご確認ください。

数学ガールの秘密ノート/整数で遊ぼう (数学ガールの秘密ノートシリーズ)

入力を受け取って、まずは３で割った余りを求めるところからスタートです。
3で割った余りということは、0か1か2の3つしかないので、それぞれの場合について考えればOKですね。

余りが0の場合

0を出力して終了

余りが1の場合

入力で受け取った数字から、余りが1になる数(1,4,7)のいずれか1つを削除すればOKです。
しかし、入力で受け取った数字に上記3つの数字がない場合は、余りが2になる数字(2,5,8)を2つ合わせて(4,7,10,13,16分を)削除すればOKです。

余りが2の場合

余りが1の場合の逆ですね。
入力で受け取った数字から余りが2になる数(2,5,8)のいずれか一つを削除すればOKです。
受け取った数字に上記3つがない場合は、余りが1になる数字2つを組み合わせて削除すればOKです。

注意事項としては、
全部の数字を削除してしまった場合は、-1を出力する必要がある。ってことですね。
入力例4(11)のような場合、

11%3=2
1%3=1
1%3=1

余りが2になる数は存在しないので、余りが1になる数を2つ削除するのですが、この場合は1以上の数字にならないのでNGとして-1を出力する必要があります。

以上をコードとして記述して提出すればOKです。

# AtCoder Beginner Contest 182
# C - To 3

n=input()
originr=int(n)%3
if originr==0:
    print(0)
    exit()

N=list(map(int,n))
r1=0
r2=0

for e in N:
    r=e%3
    if r==1:
        r1+=1
    elif r==2:
        r2+=1

if originr==1:
    if r1>0:
        ans=1
    else:
        ans=2
else:
    if r2>0:
        ans=1
    else:
        ans=2
if ans==len(N):
    print(-1)
else:
    print(ans)

私はこの問題で、入力で受け取った数の余りが1の場合と2の場合で分岐させずに1つWAが取れずにコンテスト中解けませんでした。

BIT全探索で解いた方も多いようですね。

今回のABCのパフォーマンスが悪く、灰色に戻ってしまいました。(´;ω;｀)