アルゴリズムの学習改善のための自身の備忘録及び学習の一環として記事を書くことにしました.
読んでくれた方で何かありましたら気兼ねなくコメントしてください.お待ちしております.
A - Move Right
問題文 概要
$4$桁の$0,1$からなる文字列を右に移動し,先頭に$0$を挿入.上$4$桁を出力する
制約と入力
制約
$S$は$0,1$からなる長さ$4$の文字列
入力
入力は以下の形式で標準入力から与えられる。
$S$
考察
問題より,先頭の$0$は固定である.
与えられた文字列の末尾を除く$3$文字をそのままの順序で出力する.
サンプルコード
s=input()
print('0'+s[0]+s[1]+s[2])
B - Unique Nicknames
問題文 概要
あだ名は苗字または名前と等しいものを定義する.
あだ名が一意か判定する.
制約と入力
制約
$2\leq N \leq 100$
$N$は整数である。
$s_i,t_i$は英小文字からなる$1$文字以上$10$文字以下の文字列である。
入力
入力は以下の形式で標準入力から与えられる。
$N$
$s_1 \ \ t_1$
$s_2 \ \ t_1$
$ \vdots $
$s_N \ \ t_N$
考察
全体の出現回数が$1$回であればあだ名として成立する.
苗字と名前が同じである場合,全体での出現回数が$2$回であればよいことに注意したい.
サンプルコード
n=int(input())
ST=[]
for i in range(n):
s,t=map(str,input().split())
ST.append(s)
ST.append(t)
for i in range(n):
if (ST.count(ST[2*i])!=1 and ST.count(ST[2*i+1])!=1) or ():
if ST[2*i]==ST[2*i+1] and ST.count(ST[2*i]):
continue
print("No")
exit()
print("Yes")
C - 1 2 1 3 1 2 1
問題文 概要
- $S_1=1$
- $S_n=S_{n-1},n,S_{n-1}$
を定義する.
$S_N$を求める.
制約と入力
制約
$N$は整数
$1 \leq N \leq 16$
入力
入力は以下の形式で標準入力から与えられる。
$N$
考察
$S_0$を空とする.
以降$S_n=S_{n-1},n,S_{n-1}$として順に定義し$S_n$を求める.
これは,$S_1=1$になるため問題に反しない.
サンプルコード
n=int(input())
s=[]
for i in range(1,n+1):
s=s+[i]+s
print(*s)
D - Cylinder
問題文 概要
- $1$:数$x$を右から$c$回挿入する.
- $2$:左から$c$回取り出し,取り出した合計の数値を出力.
この操作を全てのクエリを実行する.
制約と入力
制約
$1 \leq Q \leq 2 \times 10^5$
$0 \leq x \leq 10^9$
$1 \leq c \leq 10^9$
$2 \ c$のクエリが与えられるとき、筒の中には$c$個以上のボールがある
入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
$Q$
$query_1$
$\vdots$
$query_Q$
$i$番目のクエリを表す$query_i$は以下の$2$種類のいずれか
$1 \ \ x \ \ c$
$2 \ \ c$
考察
挿入と出力を愚直に行うと計算回数は$10^5 \times 10^9 = 10^{14}$となるので,実行時間が間に合わない.
$x,c$を$1$つのまとまりとして扱う.
出力の際,充足するまで取り出し続ける.超過分は左から挿入する.
サンプルコード
from collections import deque
q=int(input())
Deque=deque()
for i in range(q):
query=list(map(int,input().split()))
if query[0]==1:
Deque.append([query[1],query[2]])
else:
cnt=0
j=query[1]
while j:
POP=Deque.popleft()
if POP[1]<=j:
cnt+=(POP[0]*POP[1])
j-=POP[1]
else:
cnt+=(POP[0]*j)
POP[1]-=j
j=0
Deque.appendleft(POP)
print(cnt)