ABC158に参加したよ

ABC158をゆる～く振り返っていきます。

目次

A - Station and Bus

文字列SにA,Bが両方含まれているか否かを判定するだけですね。

ACコード

s = input()
if 'A' in s and 'B' in s:
    print('Yes')
else:
    print('No')

B - Count Balls

先頭から最大個のボールを見ていくわけにはいかないので簡単な方法を考えます。
1回の操作で加えられるボールを1セットとし、N個に含まれるセット数とその余りを出せば計算できますね。

ACコード

n, a, b = map(int,input().split())
c = a + b  #1セットのボール
d = n % c  #先頭からN個取った時、セットにならなかったボール(余り)
ans = (n // c) * a
if a <= d:
    ans += a
else:
    ans += d
print(ans)

C - Tax Increase

制約から全探索が見えてきますね。小さい方から探して終わりです。コンテスト中はなぜか上限を110にしてWA、その後焦って999にして2ペナです…。

ACコード

import math

a, b = map(int, input().split())

for i in range(b+1,1010):
    if math.floor(i * 0.08) == a and math.floor(i * 0.1) == b:
        ans = i
        break
else:
    ans = -1
print(ans)

この問題、解説PDFを見ると

課題 : O(1) で答えを求めてください。

との一文が。
ということでやってみました。

O(1)コード

a, b = map(int,input().split())
if b * 10 <= (a * 25 + 24) // 2 and -(-a * 25 // 2) < (b + 1) * 10:
    print(max(-(-a*25//2), b * 10))
else:
    print(-1)

D - String Formation

与えられた手順に従って文字列を操作していく問題です。制約から文字列の反転操作を正直にやっていては間に合わないことがわかるので、文字列が反転しているかという情報だけを保持しておいて文字を追加していき、必要があれば最後に反転させるという手順で解けます。
しかしここで注意したいのは時間計算量です。長さnの文字列の先頭に文字を追加するとき、insert(0, v)としてしまうとO(n)かかるため、TLEになってしまいます。
そこでdequeを使うことにより、この問題を解決することが可能になります。
Python公式ドキュメントでは、以下のように記されています。

Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

今回の問題では、文字列の先頭末尾への操作しか必要がないため、dequeが適しているのがわかると思います。これを用いたコードが以下になります。

ACコード

from collections import deque

s = input()
q = int(input())
ans = deque(s)
cnt = 0
for i in range(q):
    f = [i for i in input().split()]
    if f[0] == '1':
        cnt += 1
    else:
        if f[1] == '1':
            if cnt % 2 == 0:
                ans.appendleft(f[2])
            else:
                ans.append(f[2])
        else:
            if cnt % 2 == 0:
                ans.append(f[2])
            else:
                ans.appendleft(f[2])
if cnt % 2 != 0:
    ans.reverse()
print(''.join(map(str,ans)))

最後に

今回はdequeや文字列操作の時間計算量を知らず、コンテスト中にD問題をACすることができなかったため3完2ペナ茶パフォと大敗北を喫しました。
コンテスト成績
しっかりと復習や精進をして、次回は今回の分も取り戻したいですね。