ABC260(AtCoder Beginner Contest 260) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
更新時はツイッターにて通知します。
https://twitter.com/AtCoder4
A - A Unique Letter Dif:12
単純にa,b,c,...,zまでSに1文字だけ存在するかを確認していきましょう。
(文字列).count(文字)とすることで(文字列)に(文字)がいくつ含まれるか確認できます。
例えばSに「a」がいくつ含まれるか確認するなら以下のようになります。
S.count("a")
これが1ならば「a」が答えになるというわけです。
答えを出力するときは「"a"」というようにダブルクオーテーションで囲みます。これはpythonに「これは文字だよ」と伝える印です。
【提出1】
もう少し賢くやるなら以下のように条件分岐する方法もあります。
Sの先頭を0文字目、真ん中を1文字目、右端を2文字目と呼びます。
・Sの0文字目≠Sの1文字目 かつ Sの0文字目≠Sの2文字目→答え：Sの0文字目
・上記でなく Sの0文字目≠Sの1文字目 かつ Sの1文字目≠Sの2文字目→答え：Sの1文字目
・上記でなく Sの0文字目≠Sの2文字目 かつ Sの1文字目≠Sの2文字目→答え：Sの2文字目
・上記全て成り立たない→答え：-1
Sのx文字目はS[x]と書きます。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出1】
# 入力の受け取り
S=input()
# 「a」の個数が1個ならば
if S.count("a")==1:
# 「a」を出力
print("a")
elif S.count("b")==1:
print("b")
elif S.count("c")==1:
print("c")
elif S.count("d")==1:
print("d")
elif S.count("e")==1:
print("e")
elif S.count("f")==1:
print("f")
elif S.count("g")==1:
print("g")
elif S.count("h")==1:
print("h")
elif S.count("i")==1:
print("i")
elif S.count("j")==1:
print("j")
elif S.count("k")==1:
print("k")
elif S.count("l")==1:
print("l")
elif S.count("m")==1:
print("m")
elif S.count("n")==1:
print("n")
elif S.count("o")==1:
print("o")
elif S.count("p")==1:
print("p")
elif S.count("q")==1:
print("q")
elif S.count("r")==1:
print("r")
elif S.count("s")==1:
print("s")
elif S.count("t")==1:
print("t")
elif S.count("u")==1:
print("u")
elif S.count("v")==1:
print("v")
elif S.count("w")==1:
print("w")
elif S.count("x")==1:
print("x")
elif S.count("y")==1:
print("y")
elif S.count("z")==1:
print("z")
# それ以外なら
else:
# 「-1」を出力
print(-1)
【提出2】
# 入力の受け取り
S=input()
# ・Sの0文字目≠Sの1文字目 かつ Sの0文字目≠Sの2文字目
if S[0]!=S[1] and S[0]!=S[2]:
# 答え：Sの0文字目
print(S[0])
# ・上記でなく Sの0文字目≠Sの1文字目 かつ Sの1文字目≠Sの2文字目
elif S[0]!=S[1] and S[1]!=S[2]:
# 答え：Sの1文字目
print(S[1])
# ・上記でなく Sの0文字目≠Sの2文字目 かつ Sの1文字目≠Sの2文字目
elif S[0]!=S[2] and S[1]!=S[2]:
# 答え：Sの2文字目
print(S[2])
# ・上記全て成り立たない
else:
# 答え：「-1」
print(-1)
B - Better Students Are Needed! Dif:195
問題文の通り、順番に合格者を決めていきましょう。
(1)数学の点が高い方からX人を合格とする。
まず数学の点数と受験生の番号を二次元配列へ格納します。配列の名前をMathPとしましょう。
ここで重要なことは受験生の番号をマイナスで記録することです。
例えば
1番の受験生の数学点数=30
2番の受験生の数学点数=30
3番の受験生の数学点数=80
であった場合、
MathP=[[30,-1],[30,-2],[80,-3]]
というようにします。
次にMathPを大きい順にソートします。二次元配列をソートするとまず先頭の要素が大きい順、次に2つ目の要素が大きい順になります。
この例ならソートすると以下のようになります。
MathP=[[80,-3],[30,-1],[30,-2]]
あとはこのリストの前からX人の番号を合格とすればいいわけです。
同点の場合、合格者は番号の小さい方が優先されますから、受験生の番号をマイナスで記録と楽に処理ができるというわけです。
(2)次に、この時点でまだ合格となっていない受験者のうち、英語の点が高い方からY人を合格とする。
同様に英語の点数を記録していきますが、すでに合格している受験者は記録しないように注意しましょう。
if (要素) in (リスト):
とすれば「(要素)が(リスト)に含まれるなら」という条件を作れます。逆に含まれない場合は
if (要素) not in (リスト):
と書きます。合格者のリストを用意しておけば合格者を含めない英語の点数リストが作れるわけです。
(3)次に、この時点でまだ合格となっていない受験者のうち、数学と英語の合計点が高い方からZ人を合格とする。
同じように点数、受験生の番号を記録して処理すればOKです。
最後に合格者のリストをソートして出力すれば終わりです。
【提出】
# 入力の受け取り
N,X,Y,Z=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
# 合格者のリスト
ans=[]
# 数学の点数と受験番号リスト
MathP=[]
# i=0~(N-1)
for i in range(N):
# 「数学の点数」,「受験番号のマイナス」を記録
MathP.append([A[i],-(i+1)])
# 大きい順にソート
MathP.sort(reverse=True)
# リストの前からX人合格
# i=0~(X-1)
for i in range(X):
# 答えに合格者の番号を格納
ans.append(-MathP[i][1])
# 英語の点数と受験番号リスト
EngP=[]
# i=0~(N-1)
for i in range(N):
# 合格者のリストに番号がなければ
if (i+1) not in ans:
# 「英語の点数」,「受験番号のマイナス」を記録
EngP.append([B[i],-(i+1)])
# 大きい順にソート
EngP.sort(reverse=True)
# リストの前からY人合格
# i=0~(Y-1)
for i in range(Y):
# 答えに合格者の番号を格納
ans.append(-EngP[i][1])
# 数学と英語の合計点数と受験番号リスト
MEP=[]
# i=0~(N-1)
for i in range(N):
# 合格者のリストに番号がなければ
if (i+1) not in ans:
# 「数学と英語の合計点数」,「受験番号のマイナス」を記録
MEP.append([A[i]+B[i],-(i+1)])
# 大きい順にソート
MEP.sort(reverse=True)
# リストの前からZ人合格
# i=0~(Z-1)
for i in range(Z):
# 答えに合格者の番号を格納
ans.append(-MEP[i][1])
# 答えのリストをソート
ans.sort()
# x：ansの各要素
for x in ans:
# xを出力
print(x)
C - Changing Jewels Dif:413
最終目標はレベル1の青い宝石をたくさん手に入れることなので、レベルが1以上の宝石は全て変換したほうが良いです。
レベルの大きい順に宝石を全て変換しながらいくつになるかシュミレーションを行います。
レベルiの赤い宝石の数をRed[i]
レベルiの青い宝石の数をBlue[i]
とします。
最初はレベルNの赤い宝石が1個なので
Red[N]=1
となります。
赤い宝石を変換すると1個につきレベル(n-1)の赤い宝石1個、レベルnの青い宝石X個になるので
Red[i-1]+=Red[i]
Blue[i]+=Red[i]*X
となります。
青い宝石を変換すると1個につきレベル(n-1)の赤い宝石1個、レベル(n-1)の青い宝石Y個になるので
Red[i-1]+=Blue[i]
Blue[i-1]+=Blue[i]*Y
となります。
これをi=N,(N-1),...と順に計算し、最後にBlue[1]を出力すれば終わりです。
【提出】
# 入力の受け取り
N,X,Y=map(int,input().split())
# 赤い宝石の個数
Red=[0]*(N+1)
# 青い宝石の個数
Blue=[0]*(N+1)
# レベルNの赤い宝石が1個ある
Red[N]=1
# i=N~2 -1ずつ
for i in range(N,1,-1):
# 赤い宝石を変換
# 1個につきレベル(n-1)の赤い宝石1個に変換
Red[i-1]+=Red[i]
# 1個につきレベルnの青い宝石X個に変換
Blue[i]+=Red[i]*X
# レベルiの赤い宝石はなくなる
Red[i]=0
# 青い宝石を交換
# 1個につきレベル(n-1)の赤い宝石1個に変換
Red[i-1]+=Blue[i]
# 1個につきレベル(n-1)の青い宝石Y個に変換
Blue[i-1]+=Blue[i]*Y
# レベルiの青い宝石はなくなる
Blue[i]=0
# レベル1の青い宝石の個数を出力
print(Blue[1])
D - Draw Your Cards Dif:1074
管理すべき情報を考えましょう。
まずカードを引くたびにどこの山に重ねるか確認するため、場に見えている表向きのカードの一覧が必要です。
更にカードを重ねたタイミングで山を食べるか考えるので、山の枚数も必要です。
そして答えを記録するため、山の中にどのカードがあるかも必要です。
よって以下のように山の番号と山の中身を管理します。
例えば山1には「1」「5」「7」が含まれていて、表向きになっているのは「1」である、というような形です。
実装ではこれらは山の番号をキー、カードのリストを値とする連想配列(defalutdict)で管理します。
連想配列(defalutdict)がよくわからないという人は以下を確認してください。
defaultdict(連想配列)について
辞書または連想配列と言います。
キー：値
というような対応付を行えるデータ構造です。
連想配列はdict()と書くことでも使えますが、デフォルトの値(初期値)が設定できません。そのため存在チェックなど色々面倒が発生します。
その面倒を避けるためにdefaultdictを使います。
import：from collections import defaultdict
作成(デフォルト0)：変数名=defaultdict(int)
キー、値の登録：変数名[キー]=値
値の取り出し：変数名[キー]
【使用例】
# インポート
from collections import defaultdict
# 作成(デフォルト0)：変数名=defaultdict(int)
dictionary=defaultdict(int)
# キー、値の登録：変数名[キー]=値
dictionary[5]=1
# 値の取り出し：変数名[キー]
x=dictionary[5]
詳しく知りたい人は以下を参照してください。
初期値は空のリストにするため、
変数名=defalutdict(list)
とします。
カードを引いた時、どの山にカードを追加すべきか確認する方法を考えます。
「場に見えている表向きのカードのうち、X以上で最小のもの」を探すということで二分探索をしたいところですが、カードを重ねるたびに場に見えている表向きのカード一覧を更新してソートしていてはTLEします。
そこでFenwickTreeを使います。
図では「1」「3」「2」「4」「9」が表向きで場に見えています。
FTというリストを用意し、場に見えているカードの部分だけ「1」にします。残りは0です。
次のカードが「6」だったとしましょう。「6」をどの山に追加すべきか、すなわち「場に見えている表向きのカードのうち、6以上で最小のもの」を探すためにFTの区間和を考えます。
例えばFT[6]~FT[7]の区間和は0+0=0となります。つまりこの区間には1がない⇔表向きになっているカードがない ということです。
FT[6]~FT[9]の区間和は0+0+0+1=1となります。これはこの区間に1がある⇔表向きになっているカードがある ということを意味します。
よってFT[6]~FT[p]が1以上となるpのうち、最小のものが「場に見えている表向きのカードのうち、6以上で最小のもの」ということになります。(この例ではp=9です)
このpを探すために二分探索を使います。
二分探索
二分探索は区間の中央の値が条件を満たすか確認し、徐々に区間を狭めて目的の値を得るアルゴリズムです。
探索を行う前に対象の数列は単調増加、または減少となっている必要があります。
(1)区間[左,右]を指定する
左=最小値(単調減少なら最大値)のインデックス番号
右=最大値(単調減少なら最小値)のインデックス番号
(2)中央=(左+右)//2が条件を満たすか確認
(3)(2)の結果より左または右を更新する
・中央が条件を満たす：右(または左)=中央と更新
・中央が条件を満たさない：左(または右)=中央と更新
(4)1<(右-左)となっている間(2)~(4)を繰り返す
本問ではカードXがどの山に入るか確認するため、FT[X]~FT[p]の区間和が1以上となるpのうち最小のものを探します。
【二分探索を実装したことがない場合】
この問題は二分探索問題としては難易度が高いため、他の問題で練習してから解くことをおすすめします。
以下が比較的簡単な二分探索問題です。
ABC146 C：https://atcoder.jp/contests/abc146/tasks/abc146_c
ABC231 C：https://atcoder.jp/contests/abc231/tasks/abc231_c
ABC231 Cは以下で解説をしています。
https://qiita.com/sano192/items/2b2656202b767109387e#c---counting-2
ABC146 Cについては拙著『AtCoder 凡人が『緑』になるための精選50問詳細解説』で解き方、二分探索のコツ、実装方法まで詳細に解説しています。
詳細は【広告】をご確認ください。
通常区間和は計算にO(N)かかるのですが、FenwickTreeを使って管理するとO(logN)で計算ができます。
FenwickTree
FenwickTreeは数列の要素への加算、区間和計算を高速で行えるデータ構造です。
FenwickTreeについては以下の記事でとてもわかり易くまとめている方がいらっしゃるので興味があれば読んでください。
ただし実装については理解できなくても、以下のclassをコピペして使えれば問題ありません。
灰色～茶色コーダーの方はFenwickTreeの考え方を「ふ～んなるほどね～」くらいで理解しておけば十分です。
FenwickTreeのクラス内容については『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』にて詳細に解説しています。
内容までしっかり理解したいという人は購入をご検討ください。
詳しくは【広告】をご覧ください
class FenwickTree:
def __init__(self,n):
self._n=n
self.data=[0]*n
def add(self,p,x):
p+=1
while p<=self._n:
self.data[p-1] +=x
p+=p&-p
def _sum(self,r):
s=0
while 0<r:
s+=self.data[r-1]
r-=r&-r
return s
def sum(self,l,r):
r+=1
return self._sum(r)-self._sum(l)
def select(self,p):
return self.sum(p,p)
「使い方」
・初期化【O(N)】：変数名=Fenwick_Tree(要素数)
・加算【O(logN)】：add(インデックス番号,加算する数)
・区間和の計算【O(logN)】：sum(左インデックス番号,右インデックス番号)
・値の参照【O(logN)】：select(インデックス番号)
「使用例」
# 初期化【O(N)】：変数名=Fenwick_Tree(要素数)
FT=FenwickTree(10)
# 加算【O(logN)】：add(インデックス番号,加算する数)
FT.add(0,4)
FT.add(5,-1)
FT.add(7,3)
# 区間和の計算【O(logN)】：sum(左インデックス番号,右インデックス番号)
print(FT.sum(2,8))
# 値の参照【O(logN)】：select(インデックス番号)
print(FT.select(7))
引いたカードを重ねる山の番号がわかったら情報を更新します。
すなわち場に見えている表向きのカードがpからXに変わるので
・FT[X]=1にする
・FT[p]=0にする
と処理を行います。更に表に来ているカードXがどの山にあるのかという情報も記録します。
最後にXを重ねた山の枚数を確認し、Kになっていれば食べます。
すなわち山のカードについて何ターン目で消したのか記録し、Xが表向きで場にあるカードであるという情報を変更します。(FT[X]=0にする)
pythonでは間に合わないのでpypyで提出します。
【提出】
# pypyで提出
class FenwickTree:
def __init__(self,n):
self._n=n
self.data=[0]*n
def add(self,p,x):
p+=1
while p<=self._n:
self.data[p-1] +=x
p+=p&-p
def _sum(self,r):
s=0
while 0<r:
s+=self.data[r-1]
r-=r&-r
return s
def sum(self,l,r):
r+=1
return self._sum(r)-self._sum(l)
def select(self,p):
return self.sum(p,p)
# 入力の受け取り
N,K=map(int,input().split())
P=list(map(int,input().split()))
# FenwickTreeを用意
FT=FenwickTree(N+1)
# defaultdictのインポート
from collections import defaultdict
# 山の情報を管理
# 山3にカード「1」「5」「8」が入っているならDeck[3]=[1,5,8]
Deck=defaultdict(list)
# 山の番号管理
DeckNum=0
# カードが何番の山にあるか
# CardDeck[1]=2 ならばカード「1」が2番の山にある
CardDeck=[0]*(N+1)
# 答え
ans=[-1]*(N+1)
# 二分探索
# 場に見えているカードのうち、x以上で最小のものを探す
def Nibutan(x):
# (1)区間[左,右]を指定する
# 左端=最小値(単調減少なら最大値)のインデックス番号
# 右端=最大値(単調減少なら最小値)のインデックス番号
l=x
r=N
# (4)1<(右-左)となっている間(2)~(4)を繰り返す
while 1<r-l:
# (2)中央=(左+右)//2が条件を満たすか確認
c=(l+r)//2
# FT[x]~FT[c]の区間和が1以上なら
if 1<=FT.sum(x,c):
# 右=中央と更新
r=c
# そうでなければ(FT[x]~FT[c]の区間和が0なら)
else:
# 左=中央と更新
l=c
# 右を返す
return r
# i=0~(N-1)
for i in range(N):
# 引いたカード
X=P[i]
# K=1ならば
if K==1:
# カードXを(i+1)ターン目に食べることを記録
ans[X]=i+1
# FT[X]~FT[N]の区間和が0ならば
# ⇔表に見えている中にXより大きい数字のカードはない
elif FT.sum(X, N)==0:
# 新しい山を作る
# 山の番号をプラス1
DeckNum+=1
# DeckNum番目の山にXを追加
Deck[DeckNum].append(X)
# Xが場に見えている表向きのカードになる
FT.add(X, 1)
# XはDeckNum番目の山にあるカードであることを記録する
CardDeck[X]=DeckNum
# そうでなければ(FT[X]~FT[N]の区間和が1以上ならば)
else:
# p：場に見えている表向きのカードのうち、x以上で最小のもの
p=Nibutan(X)
# カードpが置かれている山の番号
pNum=CardDeck[p]
# カードXを山pNumに置く
Deck[pNum].append(X)
# カードpは場に見えている表向きのカードでなくなる
FT.add(p, -1)
# カードXが場に見えている表向きのカードになる
FT.add(X, 1)
# XはpNum番目の山にあるカードであることを記録する
CardDeck[X]=pNum
# pNum番目の山のカード枚数がK枚になったら
# ⇔カードを食べる
if len(Deck[pNum])==K:
# q：pNum番目の山のカードそれぞれについて
for q in Deck[pNum]:
# (i+1)ターン目に食べたことを記録
ans[q]=i+1
# Xが表向きで場にあるカードでなくなる
# ⇔マイナス1して0にする
FT.add(X, -1)
# i=1~N
for i in range(1,N+1):
# 答えの出力
print(ans[i])
【広告】
『AtCoder 最速で緑になる 基礎・典型50問詳細解説』
ABC201～250から基礎・典型問題50問をとてつもなく丁寧かつ詳細に解説した本(kindle)、pdf(booth)です。
灰色、茶色コーダーにおすすめ！
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP
【booth(pdf)】
https://booth.pm/ja/items/4102300
冒頭5問をサンプルとして無料公開しています
https://qiita.com/sano192/items/6361ed72106cb6dd5843
『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