[PythonでAtcoder] AtCoder Beginner Contest 173 解説

スポンサーリンク

自分用の勉強記録もかねて、Atcoderの解説をしていきたいと思います。

今回は、AB完答でした。Cは実装に手間取り提出できずという感じです。

最近振るわないなぁ〜。

Dは解説読んだら理解できました。数学の問題といった印象ですね。

A~Dについて解説していきます。

僕もプログラミングについて絶賛学習中なので、間違えなどありましたら気軽にご連絡ください。

スポンサーリンク

A - Payment

問題はこちら

n = input()
n_l = int(n[-3:])
if n_l==0:
    print(0)
else:
    print(1000-n_l)

シンプルな問題。僕はこんな感じで書きましたが。mod1000で考えたほうが、場合わけもないし、ベターだと思います。

n = int(input())
print((1000-(n % 1000))%1000)

最後に %1000 しているのは入力が6000などの場合、1000%1000で0とするためです。

B - Judge Status Summary

問題はこちら

n = int(input())
c0 = 0
c1 = 0
c2 = 0
c3 = 0
for _ in range(n):
    word = input()
    if word=='AC':
        c0 +=1
    elif word == 'WA':
        c1 +=1
    elif word == 'TLE':
        c2 +=1
    else:
        c3 +=1
print('AC x '+str(c0))
print('WA x '+str(c1))
print('TLE x '+str(c2))
print('RE x '+str(c3))

シンプルな条件分岐と繰り返し文の問題。解説はなし。

C - H and V

問題はこちら

h,w,k = map(int,input().split())
C = list([] for _ in range(h)) # h×wの2次元配列を作る。
for _ in range(h):
    C[_] = list(input())

ans =0

for s in range(2**h):
    b_h = '{:06b}'.format(s) #sを2進数に直す。:bが2進数への変換、06が6桁で0埋めすることを表す。
    for t in range(2**w):
        b_w = '{:06b}'.format(t)
        black = 0 #黒の数を数える
        for i in range(h):
            for j in range(w):
                if C[i][j]=='#' and b_h[-(i+1)] == '0' and b_w[-(j+1)]=='0':
                    # 該当のマスが黒かつ、赤く塗られていない(2進数で0)場合
                    black += 1
        if black==k:
            ans +=1
print(ans)

PDFの解説にもあるように、それぞれの行を赤く塗るか考えた場合の数は「2の(H+W)乗 」通り。今回の制約 H, W ≤ 6 のもとでは最大でも 2の12 乗= 4096 通りで数え上げればOK。

数え上げの際に2進数を導入する。

2進数への変換はいくつかやり方があるが今回はこちらのformatの書式変換を使った。

ちなみに僕はまだ使い慣れませんが、2進数を導入したときはビット演算子と論理積を組み合わせる方法もベターなようです。

参考:Pythonの演算子の一覧表とわかりやすい解説他の人の参考

D - Chat in a Circle

問題はこちら

フレンドリーさを大きい順に足していく感じです。

直感的にはイメージできると思いますが、証明は少しコツがいる感じですかね。

詳しくは公式のPDF公式のYoutube動画を参考にしてください。

n = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
print(A[0]+sum(A[1:n//2])+sum(A[1:n-n//2]))

コメント

タイトルとURLをコピーしました