Atcoder ABC247 振り返り
E問題水diffでしたが,いけそうな雰囲気を感じたので頑張ってましたが解けませんでした……解法はほとんど合っていたので後は実装力を付けたいです.
A - Move Right【AC】
左端は必ず0,その他は右端以外の文字列を結合すれば良いです.
s = input() print("0"+s[:-1])
B - Unique Nicknames【解説AC】
1回提出してWAになり,放置したまま次の問題を解いてたらB解くまえに時間が終わってました……
一ペアでも名前のダブりが存在したらダメなので,全探索してダブりがあるか調べます.
N = int(input()) S = [] T = [] for _ in range(N): s, t = input().split() S.append(s) T.append(t) for i in range(N): name_ok = False for s in [S[i], T[i]]: ok = True for j in range(N): if i == j: continue if s == S[j] or s == T[j]: ok = False if ok: name_ok = True if not name_ok: print("No") break else: print("Yes")
C - 1 2 1 3 1 2 1【AC】
(Bより何倍も簡単な気がする……)Pythonは文字列の結合が簡単にできるのでそのまま実装します.
N = int(input()) S = "1" for i in range(2, N+1): S = S + f" {i} " + S print(S)
D - Cylinder【AC】
素直にキューにボールを詰めていたらc=10**9なので10**9個の要素をappendすることになり,時間が足りなくなります.よって,数xのボールがy個あるという情報をキューに入れます.その情報を使う事で時間内に間に合います.
from collections import deque que = deque() for _ in range(int(input())): q = [int(i) for i in input().split()] if q[0] == 1: que.append(q[1:]) else: ans = 0 while que and que[0][1] <= q[1]: ans += que[0][1]*que[0][0] q[1] -= que[0][1] que.popleft() if que: que[0][1] -= q[1] print(ans + q[1]*que[0][0]) else: print(ans)
E - Max Min【解説AC】
公式解説の部分問題2までは自力でたどり着いてました.数列Aには様々な値が入りますが,値kはk==X, K==Y, Y<=k<=X, それ以外, のどれかという情報のみしか必要ないと言うところがポイントでした.更に,それ以外に当たる数字は,解の数列に入ることは必ず無いので,それ以外の数字を区切り文字として分割して考える事が出来るというところもポイントでした。そして,これを尺取り法を使えば解けそうと言う事も気付いていましたが,正しく実装出来ませんでした……実装のコツは掴んだので次回尺取り法使うときは解ける(はず)です.
import math N, X, Y = [int(i) for i in input().split()] A = [int(i) for i in input().split()] ans = 0 i = 0 while i < N: a = [] while i < N and Y <= A[i] <= X: a.append(A[i]) i += 1 if len(a) == 0: i += 1 continue left, right, num_X, num_Y = 0, 0, 0, 0 while left < len(a): while right < len(a) and (num_X == 0 or num_Y == 0): if a[right] == X: num_X += 1 if a[right] == Y: num_Y += 1 right += 1 if num_X > 0 and num_Y > 0: ans += len(a) - right + 1 if a[left] == X: num_X -= 1 if a[left] == Y: num_Y -= 1 left += 1 print(ans)