ABC225(AtCoder Beginner Contest 225) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
UNICORN株式会社様について
UNICORN株式会社様は広告主や広告代理店が従来行ってきた“人による細かな運用や数値分析”に費やす時間を削減し、“人にしか行えない業務”に専念できる環境を整えると共に、さらにマーケティング本来の目的である製品やサービスの売上拡大をミッションとして、全自動マーケティングプラットフォーム「UNICORN」の開発・提供を実現しています。
興味のある方はホームページをご覧ください。
AtCoder Jobsにて求人情報も掲載されています。
A - Distinct Strings
Sのうち
・3文字が同じ→1種類
・2文字が同じ→3種類
・同じ文字がない→6種類
となります。
これをifで条件分岐します。
pythonでは最初の文字を0文字目、左から2つ目は1文字目、左から3つ目は2文字目、...と数えます。
Sのx文字目はS[x]で確認できます。
ゆえに
・3文字が同じ
S[0]==S[1]==S[2]:
・2文字が同じ(0文字目と1文字目 または 1文字目と2文字目 または 2文字目と0文字目が同じ)
S[0]==S[1] or S[1]==S[2] or S[2]==S[0]:
・同じ文字がない
上記以外
として判定します。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
S=input()
# 0文字目、1文字目、2文字目が同じなら
if S[0]==S[1]==S[2]:
# 「1」を出力
print(1)
# 0文字目と1文字目 または 1文字目と2文字目 または 2文字目と0文字目 が同じなら
elif S[0]==S[1] or S[1]==S[2] or S[2]==S[0]:
# 「3」を出力
print(3)
# そうでなければ(すべて違う文字ならば)
else:
# 6を出力
print(6)
B - Star or Not
「スター」である条件が問題文だけではよくわからないと思います。
こういうときはまず入力例を見て、紙に書いてみましょう。
入力例1は
N：5
a1 b1：1 4
a2 b2：2 4
a3 b3：3 4
a4 b4：4 5
となっています。
このグラフは「スター」です。
図にすると以下のようになります。
確かに1つの頂点(=④)から他の全ての頂点に1本ずつ辺が出ています。
頂点ごとに辺の本数を数えて、その本数が(N-1)本の頂点があれば「Yes」、なければ「No」を出力します。
countというリストを用意し、入力を受け取りながら辺の本数をカウントしていきます。
例：頂点④から出ている辺の数が3ならcount[4]=3
countが作れたらそれぞれの頂点について辺の本数を確認します。
一つでもN-1本の頂点があれば「Yes」を出力して終了です。
途中で終了する場合はexit()とします。
辺の本数が(N-1)本の頂点が一つもなければ「No」を出力します。
【提出】
# 入力の受け取り
N=int(input())
# 辺の本数を数える
count=[0]*(N+1)
# N-1回受け取り
for i in range(N-1):
# 入力の受け取り
a,b=map(int, input().split())
# a,bから出ている辺の数を数える
count[a]+=1
count[b]+=1
# i=1～Nまで
for i in range(1,N+1):
# 頂点iから出ている辺の数がN-1なら
if count[i]==N-1:
# 「Yes」を出力
print("Yes")
# プログラムの終了
exit()
# 「No」を出力
print("No")
C - Calendar Validator
大きなカレンダーAがあって、Bはそれを一部切り出したものであるか？を判定する問題です。
以下の手順で確認します。
(1)Bの一番上の行はAのある行を切り出してできるものか
(2)Bの1行目(上から2段目)以降は上の段+7となっているか
例として以下の入力を考えましょう。
N：2
M：3
B：
9 10 11
16 17 18
まずAがどんなふうになっているのか見てみましょう。
このようにカレンダーが延々と続くような形をしています。
(1)Bの一番上の行はAのある行を切り出してできるものか
Bの一番上の行は「9 10 11」です。
Aを見ればわかるようにこれはAの2行目を切り出して作れます。
切り出して作れないパターンは2つあります。
・2行にまたがる
Bの一番上の行が「13 14 15」であればAから切り出しては作れません。
・連続になっていない
Bの一番上の行が「9 11 13」であればAから切り出しては作れません。
それぞれを判定する方法を考えます。
・2行にまたがる
Bの一番上の行、左端(=B[0][0])を見ればそれがAの何行目にあるかはわかります。
Aの一番上の行を0行目、上から2番目の行を1行目、...とすれば、計算は
(B[0][0]-1)//7
となります。
例で考えましょう。
Bの一番上の行、左端は「9」です。計算式に当てはめると
(9-1)//7=1
で1行目であることがわかります。
つまりBの一番上の行はAの1行目を切り出したものであるということです。
次にAのその行における左端、右端を確認します。
左端=(行数)*7+1
右端=左端+6
となります。
「9」は1行目だったので
左端=1*7+1=8
右端=8+6=14
であることがわかります。
あとはBの一番上の行の値(9,10,11)がそれぞれが左端～右端(8～14)に収まっているか確認すればOKです。
収まっていなければ2行にまたがっているので「No」を出力して終了です。
・連続になっていない
この判定は簡単で、単に隣の数字と差が1になっているか確認するだけです。
具体的には列番号をretuとして
if B[0][retu]!=B[0][retu-1]+1:
とすればよいです。
(2)Bの1行目(上から2段め)以降は上の段+7となっているか
一番上の行がAを切り出したものだとわかれば、Bの1行目以降について「上の段+7」になっているか愚直に確認すればOKです。
具体的には行番号をgyou、列番号をretuとして
if B[gyou][retu]!=B[gyou-1][retu]+7:
として確認します。
【提出】
# 入力の受け取り
N,M=map(int, input().split())
# B記録用リスト
B=[]
# N回受け取り
for i in range(N):
# i行目をリストとして受け取り
B_tmp=list(map(int, input().split()))
# Bへ格納
B.append(B_tmp)
# (1)Bの一番上の行はAのある行を切り出してできるものか
# Aの行数
A_gyou=(B[0][0]-1)//7
# Aの左端
left=A_gyou*7+1
# Aの右端
right=left+6
# retu=0～(M-1)まで
for retu in range(M):
# Aの左端～右端の間になければ
if B[0][retu]<left or right<B[0][retu]:
# 「No」を出力
print("No")
# 終了
exit()
# retu=1～(M-1)まで
for retu in range(1,M):
# 0行目i列目 が 0行目(i-1)列目+1 でなければ
if B[0][retu]!=B[0][retu-1]+1:
# 「No」を出力
print("No")
# 終了
exit()
# (2)Bの1行目(上から2段目)以降は「上の段+7」となっているか
# gyou=1~(N-1)まで
for gyou in range(1,N):
# retu=0～(M-1)まで
for retu in range(M):
# 「上の段+7」になっていなければ
if B[gyou][retu]!=B[gyou-1][retu]+7:
# 「No」を出力
print("No")
# 終了
exit()
# 「Yes」を出力
print("Yes")
D - Play Train
車両ごとに前にある車両番号、後ろにある車両番号を記録します。
クエリ③が与えられたら記録した情報からまず先頭の車両を探す→後ろに向かって進みながら答えを記録するという手順を踏みます。
まず前後の車両番号を記録するリストを作ります。
前の車両番号：front
後ろの車両番号：back
前後に車両がない場合は0で記録します。
クエリ①
車両を連結
例：車両3の後ろに車両5を連結
front[5]=3
back[3]=5
クエリ②
車両を分離
例：車両3、車両5を分離
front[5]=0
back[3]=0
クエリ③
frontをたどって先頭の車両番号を確認(front[x]=0になったらxが先頭)
backをたどって順に後ろの車両番号を記録(back[x]=0になったらxが最後尾)
記録した車両番号を出力
クエリ③については最悪のケースでO(N)かかるので一見TLEしそうですが、制約に
3 xの形式のクエリで出力する電車の番号の個数の合計は10^6以下
とあるので間に合います。
※この条件がなければこの解法は使えません。
【提出】
# 入力の受け取り
N,Q=map(int, input().split())
# 前の車両番号を記録 なにもなければ0
front=[0]*(N+1)
# 後ろの車両番号を記録 なにもなければ0
back=[0]*(N+1)
# Q回受け取り
for i in range(Q):
# クエリをリストとして受け取り
query=list(map(int, input().split()))
# クエリ1
if query[0]==1:
x=query[1]
y=query[2]
# yの前にx
front[y]=x
# xの後ろにy
back[x]=y
# クエリ2
elif query[0]==2:
x=query[1]
y=query[2]
# 連結を外す=0にする
front[y]=0
back[x]=0
# クエリ3
elif query[0]==3:
x=query[1]
# 先頭の車両番号 最初はx
head=x
# 前の車両番号が0になるまで
while front[head]!=0:
# headを前の車両番号で更新
head=front[head]
# 答えの格納用
ans=[]
# 今の車両
now=head
# 車両番号が0になるまで
while now!=0:
# 答えに今の車両を格納
ans.append(now)
# 後ろへ
now=back[now]
# 長さ、ansを出力
print(len(ans),*ans)
【広告】
『AtCoder 凡人が『緑』になるための精選50問詳細解説』
AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
1～24問目まではサンプルとして無料公開しています
『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』
ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを5問分公開しています
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
『Excelでリバーシを作ろう!! マクロ、VBAを1から学ぶ』
Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！ 丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)
サンプルとして「準備」～「三目並べ」を無料公開しています。
【kindle】
【booth(pdf】