AtCoder Beginner Contest 247 - プログラミングの備忘録

こんにちは。
今回は、前回散々な結果であった競技プログラミング「AtCoder Beginner Contest 247」の復習をしてみます。

taq.hatenadiary.jp

本番が終わっても提出は受け取ってくれるようですし、「バーチャル順位表」というものもつくようなので、参加してみたいという方は以下からどうぞ。

atcoder.jp

復習
- 振り返る
- 見てみる
また参加する
まとめ

復習

振り返る

まずは、自分のコードを振り返ります。

プログラムを書いたのは問題A～Cなので、それぞれ見てみます。
（問題文は省略します。）

他の問題に関してはさっと見てみましたが解けそうに無かったので捨てました。

問題A

「A - Move Right」

いわゆる「ビットシフト」というやつでした。

s = input()
 
a = []
a += str(0)
for i in s:
    a += i

print('{}{}{}{}'.format(a[0], a[1], a[2], a[3]))

aという配列の最初に0を入れておき、その後に入力した列を入れる、という方法で配列をつくりました。
そして、配列aの0～3番目を空白無しで並べて出力して答えとしました。

問題B

「B - Unique Nicknames」

被りの無いようにあだ名をつけるというものでした。

n = int(input())
s = []
t = []
for i in range(n):
    l = input().split()
    s += [l[0]]
    t += [l[1]]
    
for i in range(n):
    for j in range(n):
        if i != j and ((s[i] == s[j] and t[i] == t[j]) or s[i] == t[j]):
            break
    
    if i != j and ((s[i] == s[j] and t[i] == t[j]) or s[i] == t[j]):
        print("No")
        break
    else:
        print("Yes")
        break

「No」となる条件は

同姓同名がいる
ある人の名字と別の人の名前が同じ

と考え、それ以外のときに「Yes」とするようにしました。

結局この問題は「WA」でしたが、13個中9個がACという結果となり、いじっている内にどうすればいいか分からなくなって諦めました。

問題C

「C - 1 2 1 3 1 2 1」

条件に従って数列をつくるというものでした。

n = int(input())
 
def sn(v):
    if v > 1:
        return '{} {} {}'.format(sn(v-1), v, sn(v-1))
    else:
        return 1
    
print(sn(n))

再帰を使って$n=v$のときの数列$S_n$を求める関数sn(v)をつくり、それを出力するだけで答えとなるようにしました。

これは割ときれいにいった方なのではないかと自負しています。

また、'{} {} {}'.format(sn(v-1), v, sn(v-1))の'{} {} {}'に空白を入れ忘れる、というような細かいミスもあったので、できたからといってすぐに提出すると痛い目を見ますね…

見てみる

さて、ここまでで本番で書いたプログラムを振り返りました。

本番では時間制限に焦って大事なところを見逃していたかもしれないし、違った視点で考えられるかもしれないので、また考えてみて自分なりの回答をつくるというのも良いです。

が、今回の場合は時間に余裕もあったし、単純に地頭力の問題だということで、答えを見て学ぶことにします。
主催側や有志の解説ページがあるのでそちらを参考にしたり、他の参加者の回答を見て学ぶというのもありです。

以下、他の方のコードを参考にしつつ自分がわかりやすいように変えて載せています。

問題A

配列をつくらずとも、文字列aを0としておいて、そこに入力した文字列を3番目まで加えていくという方法でも良かったようです。

s = input()

a = "0"
for i in range(3):
    a += s[i]

print(a)

Submission #30993157 - AtCoder Beginner Contest 247

これを縮めて、

print("0" + input()[:3])

Submission #30992637 - AtCoder Beginner Contest 247

問題B

結局よくわからないままなんかうまくいきました。

n = int(input())
s, t = [], []
for i in range(n):
    u, v = input().split()
    s += [u]
    t += [v]

for i in range(n):
    can_give = False
    for l in [s[i], t[i]]:
        s_ok = True
        for j in range(n):
            if i != j:
                if l == s[j] or l == t[j]:
                    s_ok = False
        if s_ok == True:
            can_give = True
    if can_give == False:
        print("No")
        break
if can_give == True:
    print("Yes")

Editorial - AtCoder Beginner Contest 247

問題C

ほぼ正解でしたが、少し変えました。

n = int(input())
 
def sn(v):
    if v > 1:
        return sn(v-1) + [v] + sn(v-1)
    else:
        return [1]
    
print(*sn(n))

Editorial - AtCoder Beginner Contest 247

format()を使って並べていましたが、配列でreturnして、printするときに「*」をつけるとタプル（複数のデータの並び）として表示してくれて、それが出力のレギュレーションに合うようなので、そうするようにしました。
（「*」が無いと配列でprintされる。）

問題D

自分なりに考えてみた結果、

Q = int(input())

b = []
for i in range(Q):
    q = list(map(int, input().split()))

    s = 0
    if q[0] == 1:
        for i in range(q[2]):
            b.append(q[1])
    elif q[0] == 2:
        for i in range(q[1]):
            s += b[i]
        del b[:q[1]]
        print(s)

というプログラムになったのですが、入力が「1 10000 10000」など大きくなると実行時間制限を超過してしまいました。

そこで、実際に配列に並べて計算するのではなく、追加するボールに書かれた数字とその個数の形で扱うことにすれば、計算量が減らせます。
（Editorial - AtCoder Beginner Contest 247）

Q = int(input())

b = [] #ボールの並び方の情報
for i in range(Q):
    q = list(map(int, input().split()))
    
    s = 0
    if q[0] == 1: #1つ目が1だったら
        b.extend((q[1], q[2])) #ボールの数字と個数を保存
    elif q[0] == 2: #1つ目が2だったら
        while q[1] > 0: #取り出すべきボールの個数が0になるまで繰り返す
            if b[1] > q[1]: #取り出す個数が同じ数字のボールの個数より多かったら
                s += b[0] * q[1] #合計値にボールの数字と取り出す個数の積を足す
                b[1] -= q[1] #取り出した分だけボールを減らす
                q[1] = 0 #取り出すべき個数は0になった
            else: #取り出す個数が同じ数字のボールの個数より少なかったら
                s += b[0] * b[1] #合計値にボールの数字とその個数の積を足す
                q[1] -= b[1] #取り出した分だけ取り出すべき個数を減らす
                del b[:2] #全て取り出したボールの情報は要らないから消す
        print(s) #合計値を出力