ABC213(AtCoder Beginner Contest 213) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下
A - Bitwise Exclusive Or
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
方法は2つあります。
(1)A xor C=Bを変形する。
A+C=BだったらC=B-Aで解けますね。
同じノリでC=B xor Aとすれば答えが出ます。
厳密には両辺へ xor Aという処理を行うことでうんぬんかんぬんという話があるのですがそれは公式解説をごらんください。
# 入力の受け取り
A,B = map(int, input().split())
# 答えの出力
print(B^A)
(2)全探索する
こっちのほうが簡単です。
問題文に「Cは0以上255以下」と書いているので256個全部試せばどれかが答えになるわけです。
というわけでC=0～255までfor文で一個一個条件を満たすか確かめましょう。
# 入力の受け取り
A,B=map(int,input().split())
# C=0~255まで探索(range(探索範囲+1)になることに注意！)
for C in range(256):
# 条件を満たしていれば
if A^C==B:
# 答えを出力する
print(C)
# 途中でプログラムを終了するときはexit()
exit()
B - Booby Prize
ソート(並び替え)して下位から2番目(スコアが大きい順で2番目)の人は誰か？を確認します。
ソートについて以下2つを覚えましょう
・二次元配列の場合、先頭の要素の順で並び替えられる(入力の受け取りを[スコア,選手の番号]とすればスコアの順に並び替えできます)
・reverse=Trueとすると大きい順に並び替えられる
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# スコアと選手の番号を記録するリスト
score=[]
# i=0～N-1まで
for i in range(N):
# [スコア,選手の番号(i+1)]を順に受け取る
score.append((A[i],i+1))
# 大きい順にソート
score.sort(reverse=True)
# 2番目(インデックスは1)の選手の番号を出力
print(score[1][1])
C - Reorder Cards
座標圧縮というテクニックを使います。
行から考えましょう。
1,3,9行目にカードがあったとします。
2,4~8行目はカードがなくて消されるので
1行目→1行目
3行目→2行目
9行目→3行目
とカードが移動します。
そして行を消そうが列の数には影響しません。
よってもとのカードを置いている行、列の数字が小さい方から何番目なのか？ということを確認できればOKです。
具体的な実装を説明します。行を使って説明しますが列についても同じです。
(1)カードが置いている行の番号をリストにする
(2)重複した番号を削除する(setにする)
(3)リストに戻してソートする
(4)もとの数字が何番目か？の対応表を作る(連想配列)
例を見ましょう。
「入力例」
5 5 5
1 1
4 3
2 2
4 4
5 5
(1)カードが置いている行の番号をリストにする
カードが置いているのは1,4,2,4,5行目なのでgyou=[1,4,2,4,5]を作ります。
(2)重複した番号を削除する(setにする)
4が重複しているので削除します。gyou=(1,4,2,5)となります。
(3)リストに戻してソートする
gyou=[1,2,4,5]となります。
(4)もとの数字が何番目か？の対応表を作る(連想配列を作る)
1→1
2→2
4→3
5→4
と変換できるように対応する連想配列を作ります。もとの数値→ソートしたインデックス番号+1とすればOKです。
# 入力の受け取り
H,W,N=map(int, input().split())
# カードの[行番号,列番号]受け取り用リスト
cards=[]
# 行番号だけ受け取るリスト
gyou=[]
# 列番号だけ受け取るリスト
retu=[]
# i=0～Nまで
for i in range(N):
# 入力の受け取り
A,B=map(int, input().split())
# カードの[行番号,列番号]を受け取り
cards.append([A,B])
# 行番号を受け取り
gyou.append(A)
# 列番号を受け取り
retu.append(B)
# 重複の削除(setにする)
gyou=set(gyou)
# リストに直す
gyou=list(gyou)
# ソートする
gyou.sort()
# 変換先を記録する連想配列(conv=convert)
gyou_conv=dict()
# 重複削除後の行の個数分
for i in range(len(gyou)):
# もとの行番号→インデックス番号+1と変換できるように記録(小さい方から何番目にあるか？)
gyou_conv[gyou[i]]=i+1
#列も同じことをする
retu=set(retu)
retu=list(retu)
retu.sort()
retu_conv=dict()
for i in range(len(retu)):
retu_conv[retu[i]]=i+1
# それぞれのカードについて行、列番号を変換して出力
for gyou,retu in cards:
# 行の変換
ans_gyou=gyou_conv[gyou]
# れつの変換
ans_retu=retu_conv[retu]
# 答えを出力する
print(ans_gyou,ans_retu)
D - Takahashi Tour
↑動画で説明しています。
DFS(深さ優先探索)の問題。
まず図を書いてみます。
「入力例1」
4
1 2
4 2
3 1
探索順序は
1→2→4→2→1→3→1
と深い方へ深い方へ進んで、進めなくなったら戻るという方式。
これはそのままDFSの探索順序と同じです。
しかし難しいのは実装の方。再帰関数で実装しますが慣れないうちは何が起こっているかわからないと思います。
まずコードを見せ、そのあとコードがどのような挙動になるか説明します。
# 再帰回数上限。再帰関数を書くときは必ず最初に書くこと
import sys
sys.setrecursionlimit(10**6)
# 入力受け取り
N=int(input())
# 辺の情報格納
connect=[[] for i in range(N+1)]
# 辺の情報受け取り
for i in range(N-1):
A,B=map(int, input().split())
connect[A].append(B)
connect[B].append(A)
# connect[1]=[2,3,4]ならば1と2,3,4がつながっている、というように確認できる
# 小さい順に回るからソート
for i in range(N+1):
connect[i].sort()
# 答えの格納リスト
ans=[]
# DFS(今いる場所,前にいた場所)
def DFS(now,pre):
# 今いる場所を答えに入れる
ans.append(now)
# to=今いる場所から行ける場所
for to in connect[now]:
# もしtoが前にいた場所と違うなら
if to!=pre:
# 更に先へ探索する
DFS(to,now)
# 戻ってきたら答えへ格納
ans.append(now)
# 最初の場所=1,前にいた場所=-1(前にいた場所がないので便宜上-1)としてスタート
DFS(1,-1)
# 答えの出力
print(*ans)
まず再帰関数はデフォルトだと上限回数がありますので、それを外すために以下を書きます。
再帰関数を使うときは必ずこれを最初に書くと覚えてください。
# 再帰回数上限。再帰関数を書くときは必ず最初に書くこと
import sys
sys.setrecursionlimit(10**6)
辺の受け取り、ソートの後、DFSに入ります。
最初はnow=1、pre=-1です。
-1に意味はありません。最初は前いた場所がないのでとりあえず、です。
DFSの部分を見てみます。
# DFS(今いる場所,前にいた場所)
def DFS(now,pre):
# 今いる場所を答えに入れる
ans.append(now)
# to=今いる場所から行ける場所
for to in connect[now]:
# もしtoが前にいた場所と違うなら
if to!=pre:
# 更に先へ探索する
DFS(to,now)
# 戻ってきたら答えへ格納
ans.append(now)
DFS(1,-1)
まず今いる場所=1がansに入ります。
次に1から行ける場所=2,3がtoに入ります。
・to=2
DFS(2,1)としてさらにDFSが始まります。
ここで気をつけるべきなのはDFS(1,-1)のDFSはDFS(2,1)のDFSが終わるまで待機状態ということです。DFS(2,1)が終わるのを待っています。
DFS(2,1)
まず今いる場所=2がansに入ります。
次に2から行ける場所=1,4がtoに入ります。
・to=1
1=preであるため何もしません
・to=4の場合
DFS(4,2)としてさらにDFSが始まります。
ここでもDFS(2,1)のDFSはDFS(4,2)のDFSが終わるまで待機状態です。DFS(4,2)が終わるのを待っています。
DFS(4,2)
まず今いる場所=4がansに入ります。
次に2から行ける場所=4がtoに入ります。
・to=4
2=preであるため何もしません
ここでDFS(4,2)のDFSが終了しました。待機状態のDFS(2,1)へ戻りましょう。
DFS(2,1)(続き)
DFS(to,now)の部分で待機していたのでその続きからスタートします。
ansにnow=2を格納します。
これでDFS(2,1)が終了します。DFS(1,-1)へ戻りましょう。
DFS(1,-1)(続き)
ansにnow=1を格納します。
to=2の途中で待機状態に入ったので、残りのto=3の処理が始まります。
・to=3
DFS(3,1)としてさらにDFSが始まります。また待機です。
DFS(3,1)
まず今いる場所=3がansに入ります。
次に3から行ける場所=1がtoに入ります。
・to=1
1=preであるため何もしません
DFS(3,1)のDFSが終了しました。待機状態のDFS(1,-1)へ戻りましょう。
DFS(1,-1)(続き)
ansにnow=1を格納します。
DFS(1,-1)が終了です。
後は答えを出力します。
【広告】
『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】