ABC314復習
AtCoder Beginner Contest 314 - AtCoder
■結果
- AC2完。(BのケアレスミスでWAしたままDが時間切れ。)
- レートは-15と余り落ちなかったが、落ち着いてれば取れた内容で悔しい。
■A問題(3.14)
設問の「切り捨て・末尾の0を取り除かない」の条件だと演算は不要で文字列処理が最適そうなので文字列でスライス。(所要時間約3分)
n = int(input())
pi="3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
print(pi[:n+2])
■B問題(Roulette)
1)xに賭けた人のリストを作成、賭けた目数も同時に保存し目数の最小を算出
2)上記から目数が最小の人のリストを作成
の2段階に分けて人番号を抽出。最後にソートして出力。20分で提出。
ここでケアレスミスがあり、賭けた目数の最小値を初期値30からカウントダウンする実装にしてしまった。(各人37か所まで賭けられるので、全員30か所以上賭けた場合にWAになる。)これに気づかずWA。コンテスト後に以下でAC。
n = int(input())
bets=[]
for ii in range(n):
c = int(input())
bet = set(map(int, input().split()))
bets.append([c,bet])
x = int(input())
result=[]
min_bet=100 # 最初30にした箇所
for ii in range(n):
if x in bets[ii][1]:
c = bets[ii][0]
result.append([ii+1,c])
min_bet = min(c, min_bet)
if min_bet == 100:
print(0)
exit()
ans_list=[]
for r in result:
if r[1] == min_bet:
ans_list.append(r[0])
ans_list.sort()
print(len(ans_list))
print(*ans_list)
■C問題(Rotate Colored Subsequence)
色ごとに右ローテートしたいので、下記の2回のループにした。
ループ1)色ごとに最後の文字が何かを取得してv[c]の初期値にする。
ループ2)色ごとに一つ前の文字としてv[c]を書き出してからv[c]更新。
(所要時間約9分でACし巻き返し)
n,m = map(int, input().split())
s = input()
c_list = list(map(int, input().split()))
# 1st scan loop
v=[0]*m
for ii in range(n):
c=c_list[ii]-1
v[c] = s[ii]
# 2ns output loop
for ii in range(n):
c=c_list[ii]-1
print(v[c],end="")
v[c]= s[ii]
強い方に、pythonのdeque.rotate()だと直接ローテート出来るという見識を習う。色毎にローテートするには下記の様に辞書で色別のdequeを作るとか。今回は元解がシンプルだが、これはこれで使い勝手良さそう。
from collections import deque,defaultdict
d = defaultdict(deque)
for ii in range(n):
c = c_list[ii]
d[c].append(s[ii])
for c in set(c_list):
d[c].rotate(1)
■Ⅾ問題(LOWER)
クエリのバッチ処理の問題。残念ながら時間切れ。
素性は判る問題だったので素早く整理すれば解けたかも。反省は2点。
反省1)Q=2,3のUpper/Lowerでは過去分の操作影響が消えるのが判っていながら、まず逐次処理で解いてからコード改修しようと考えて時間を消費。
反省2)Pythonの文字列はimmutableなのでList化し処理する必要あるが、毎回、文字列→リスト化→文字置換→joinで再文字列化するコードを書いてTLEした。
コンテスト後、最初のループでQ=2,3の最後の回を決め、2回目にQ=1の操作全部とQ=2,3の最後の回をリストに対して適用するコードにしてAC。
n = int(input())
s = list(input())
q = int(input())
commands = []
lastCaseChange = 0
for ii in range(q):
cmd, x, c = input().split()
x = int(x)
cmd = int(cmd)
commands.append([cmd, x, c])
if cmd != 1:
lastCaseChange = ii
for ii in range(q):
cmd = commands[ii][0]
x = commands[ii][1]
c = commands[ii][2]
if cmd == 1:
s[x-1]=c
if cmd == 2 and lastCaseChange==ii:
s=list("".join(s).lower())
if cmd == 3 and lastCaseChange==ii:
s=list("".join(s).upper())
print("".join(s))