AtCoder Beginner Contest 151 ／ Python

• 初学者です。（ 2019 / 9 ～ 現在５ヵ月目 ）
• AtCoder の問題に Python で取り組んでいます。
• ABC で４問目（茶か緑）まで解けることを目標にしています。

完全に独学なのでコードは酷いと思います。

AtCoder やってる方、お気軽にコメントください。

また３問、最近アルゴリズムの勉強をサボっているから４問以降がさっぱりだ。

結果

まだ暫定だ。
９回参加しなければならないらしい。

問題と解答と勉強

atcoder.jp

提出したコード

N = "abcdefghijklmnopqrstuvwxyz" 
 
print(N[N.find(input())+1])

atcoder.jp

提出したコード

N,K,M = map(int,input().split()) 
 
A = list(map(int,input().split()))
 
x = N*M - sum(A)
 
if x < 0:
    print(0)
elif x <= K:
    print(x)
else:
    print(-1)

atcoder.jp

提出したコード

import numpy as np
 
N,M = map(int,input().split()) 
 
AC = np.array([0]*N)
WA = np.array([0]*N)
 
for i in range(M):
    p,S = input().split()
    
    if AC[int(p)-1] ==0 and S == "WA":
       WA[int(p)-1] += 1
    else:
        AC[int(p)-1] = 1

print(sum(AC),sum(AC*WA))

個人的にはシンプルに作れたかなと。

正解を入れる箱 [0,0,0,0,0]
不正解を入れる箱 [0,0,0,0,0]

を作っておいて、

まだ「正解が出てない & 不正解」なら不正解の箱に＋１

それ以外は正解の箱に＋１

最後に正解の箱、不正解の箱の中身を足す。

ただし不正解の箱は最後まで正解が出なかった問題はペナルティ無しにする必要があるので、正解の箱の中身と掛け合わせて消しておく。



最後の処理を忘れていたので一度WAをくらってしまった。



そういえば、「正解が出ていない & 正解」「正解が出ている & 不正解」「正解が出ている & 正解」の場合分けや、全問正解になったら後の処理はパスする場合分けなどを入れようと思ったのだが、入れるとむしろ遅くなってしまうので止めた。入れ方が下手くそだからそうなるだけかもしれないが。

atcoder.jp

解けていない。

スタートとゴールの組み合わせ全通りを何とか探索のアルゴリズムで計算して一番長いものを出す、いやそんなことしてたら絶対時間がダメだろ、と思ったのだが、どうやらそれで良かったようだ。

何とか探索について不勉強なのでコードはよくわからない。

とりあえず、ほとんどの人が

from collections import deque

を使っていることはわかった。

コンテナデータ型とかいうやつで、

両端における append や pop を高速に行えるリスト風のコンテナ

だそうだ。両端のデータにだけ頻繁にアクセスする場合に使うと早くなるようだ。そのくらいで、後は探索のアルゴリズムでゴリゴリやるだけっぽい。



深さ優先探索と幅優先探索を勉強せねばなぁ。

英語で言うとDFSとBFS。それしか知らん。

atcoder.jp

５問めにしては問題の意味は非常にわかりやすい、何をすれば良いのかはすぐわかる、しかし、言われた通りに計算した場合、絶対に時間が足りないことは明白だ。

ということはわかるが、工夫の仕方がさっぱりだ、解説を読んでもよくわからん。理解するのに超時間が掛かりそうなので今回はここで諦め。

ということで例によって６問めは見ていない。

atcoder.jp

おまけ

前回の「第6回 ドワンゴからの挑戦状 予選」も一応参加した。

まあ１問しか解けなかったけど。

atcoder.jp

提出したコード

N = int(input())
s_list = []
t_list = []
 
for i in range(N):
    s,t = input().split()
    s_list.append(s)
    t_list.append(int(t))
 
X = input()
del t_list[:s_list.index(X)+1]
 
print(sum(t_list))

1問めと２問めの差が激しすぎないだろうか、２問め以降はさっぱりだ。