ABC247(AtCoder Beginner Contest 247) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
A - Move Right
なにやら問題文がややこしいですが、要するに与えられた文字を一つ右にずらしてくださいという問題です。
例えば「1010」なら「0101」、「1111」なら「0111」となります。
左端の文字を0文字目、左端から1つ右に進んだ場所の文字を1文字目、……とすると答えは以下のようになります。
答え：「0」+「Sの左から0文字目」+「Sの左から1文字目」+「Sの左から2文字目」
これを出力すればよいです。「Sの左から0文字目」はS[0]、「Sの左から1文字目」はS[1]、……と表します。
「0」は文字列としてくっつけるので"0"とダブルクオーテーションをつけることに注意してください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
S=input()
# 「0」+「Sの左から0文字目」+「Sの左から1文字目」+「Sの左から2文字目」
S="0"+S[0]+S[1]+S[2]
# 答えを出力
print(S)
B - Unique Nicknames
i番目の人のあだ名は姓か名なので、siかtiです。これらの両方が他の人の姓、名のどれかと被っていれば「No」となります。
i番目の人について、「i番目の人以外の姓、名が入ったリスト」を作ります。
i番目の人の姓、名の両方が「i番目の人以外の姓、名が入ったリスト」に含まれていれば「No」となりますので、出力してプログラムを終了すればOKです。
リストに要素xが含まれるかどうか？は以下のように書けば判定できます。
if x in (リスト):
【提出】
# 入力の受け取り
N=int(input())
# 姓のリスト
s_list=[]
# 名のリスト
t_list=[]
# N回
for i in range(N):
# 入力の受け取り
s,t=map(str,input().split())
# リストへ格納
s_list.append(s)
t_list.append(t)
# i=0~(N-1)
for i in range(N):
# 「i番目の人以外の姓、名が入ったリスト」
OtherNameList=[]
# k=0~(N-1)
for k in range(N):
# i≠kならば(自分以外の姓、名をリストに入れるため)
if i!=k:
# k番目の人の姓をリストに追加
OtherNameList.append(s_list[k])
# k番目の人の名をリストに追加
OtherNameList.append(t_list[k])
# i番目の人の姓、名の両方が「i番目の人以外の姓、名が入ったリスト」に含まれていれば
if s_list[i] in OtherNameList and t_list[i] in OtherNameList:
# 「No」を出力
print("No")
# 終了
exit()
# 「Yes」を出力
print("Yes")
C - 1 2 1 3 1 2 1
問題文の指示どおりにSnを作っていきましょう。
Sを[1]のリストとすればi=2~Nとして
S=S+[i]+S
という操作を繰り返すことでSnを作ることができます。
最後にSを出力します。
print(*S)
とすることでリストの[]をなしで出力ができます。
【提出】
# 入力の受け取り
N=int(input())
# S1
S=[1]
# i=2~N
for i in range(2,N+1):
# Siを作る
S=S+[i]+S
# 答えの出力
print(*S)
D - Cylinder
問題文の操作そのままに数を筒(リスト)へ記録していくとTLEしたりMLE(メモリ制限超過)したりします。
必要な情報は筒の左から「何が」「いくつ」入っているかという情報です。このペアを順番に記録していきます。
queという筒に記録していきましょう。
例えば
2が書かれたボールが3個
4が書かれたボールが6個
5が書かれたボールが3個
あるという場合、
que：[[2,3],[4,6],[5,3]]
と記録しておきます。
この時「2 8」つまり「8個のボールを取り出して書かれている数の合計を出力する」クエリが来た場合を考えます。
左端から要素を取り出します。
[2,3]なので「2が書かれたボールが3個」あります。
3個≤8個なので「2が書かれたボール」は全て取り出せます。
答えに2*3=6を加算します。
答え：6
残り取り出すボールの数は8-3=5個です。
また左端から要素を取り出します。[2,3]は取り出しているので左端にあるのは[4,6]です。
[4,6]なので「4が書かれたボールを6個」あります。
5個≤6個なので「4が書かれたボール」は5個取り出して終わりです。
答えに4*5=20を加算します。
答え：26
「4が書かれたボール」は5個取り出しているので、6-5=1個残っています。[4,1]をqueの左端に戻します。
que：[[4,1],[5,3]]
答えである26を出力します。
このように「数」と「個数」のペアを記録していけばうまくいくのですがリストで管理するとうまくいきません。リストは左端から要素を取り出すのに時間がかかる(リストの要素数をNとしてO(N))かかるからです。
そこでdequeを使います。
dequeについて
dequeはリストのようなものですが、先頭から要素を取り出す操作をO(1)で行うことができます。
(リストだとO(N)かかります)
インポート：from collections import deque
作成：変数名=deque()
先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
末尾(右端)に要素追加【O(1)】：変数名.append(要素)
先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()
【使用例】
# インポート：from collections import deque
from collections import deque
# 作成：変数名=deque()
que=deque()
# 先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
que.appendleft(1)
# 末尾(右端)に要素追加【O(1)】：変数名.append(要素)
que.append(3)
# 先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
x=que.popleft()
# 末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()
y=que.pop
詳しく知りたい人は以下のページを見てください。
dequeから要素を取り出す時、
a,b=que.popleft()
というように書くと左端から一度に2つの要素を取り出せます。例えばque=[[1,2]]だったらa=1,b=2となります。
なお、入力の受け取りについてはクエリ1,2で要素数が違うので、一旦リストで受け取り、リストの0番目、1番目という形で割り振りし直すのがよいです。
【提出】
# 入力の受け取り
Q=int(input())
# dequeをインポート
from collections import deque
# dequeを用意
que=deque()
# Q回
for i in range(Q):
# 入力の受け取り(クエリ1,2で要素数が違うのでリストで受け取り)
query=list(map(int,input().split()))
# クエリ1
if query[0]==1:
# x,cを割り振り
x=query[1]
c=query[2]
# 「数」「個数」の順で記録
que.append([x,c])
# クエリ2
else:
# cを割り振り
c=query[1]
# 答え
ans=0
# c(取り出す個数)が0より大きい間
while 0<c:
# queの左端の要素を取り出し
# num:数(number)
# count:個数
num,count=que.popleft()
# 「個数」≤取り出す個数なら
if count<=c:
# 全て取り出せる
# 「数」*「個数」を答えに加算
ans+=num*count
# 「個数」個取り出した
# 残りの取り出す個数をマイナス
c-=count
# 取り出す個数<「個数」なら
else:
# c個取り出して終わり
# 答えに「数」*cを加算
ans+=num*c
# 取り出した個数をマイナスして左端に戻す
que.appendleft([num,count-c])
# 取り出す個数を0にする
c=0
# 出力
print(ans)
【広告】
『AtCoder 凡人が『緑』になるための精選50問詳細解説』
AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/gp/product/B09C3TPQYV/
【booth(pdf)】
https://sano192.booth.pm/items/3179185
1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf
『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』
ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV
【booth(pdf)】
https://booth.pm/ja/items/3698647
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/
【booth(pdf)】
https://sano192.booth.pm/items/3698668
『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』
ABC226~250、ARC129~139 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC129~139の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS
【booth(pdf)】
https://sano192.booth.pm/items/4025713
ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF
【booth(pdf)】
https://sano192.booth.pm/items/4025737
『Excelでリバーシを作ろう!! マクロ、VBAを1から学ぶ』
Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！ 丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)
サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb
【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW
【booth(pdf】
https://sano192.booth.pm/items/3785312