UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269) A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
更新時はツイッターにて通知します。
https://twitter.com/AtCoder4
UNICORN株式会社様について
ホームページ
A - Anyway Takahashi Dif:8
指示通りに出力を行います。
「Takahashi」は文字列なので「""」(ダブルクオーテーション)をつけなければならないことに注意してください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
a,b,c,d=map(int,input().split())
# (a+b)*(c-d)を出力
print((a+b)*(c-d))
# 「Takahashi」を出力
print("Takahashi")
B - Rectangle Detection Dif:68
A,B,C,Dについて全通り試してみましょう。
以下のように4重ループを書けば全ての組を作ることができます。
for A in range(10):
for B in range(A,10):
for C in range(10):
for D in range(C,10):
これで以下のように代入しながら処理ができます。
(A,B,C,D)
(0 0 0 0)
(0 0 0 1)
(0 0 0 2)
(0 0 0 3)
...
(0 0 0 9)
(0 0 1 1)
(0 0 1 2)
(0 0 1 3)
...
(9 9 8 8)
(9 9 8 9)
(9 9 9 9)
pythonは0インデックスなのでリストの先頭は0番目、文字の先頭は0文字目となりますから、A=1,2,3,...ではなくA=0,1,2,...と一つずれます。
答えを出力するときに+1してずらします。
i=0~9,j=0~9について、Siのj文字目を確認します。
まず条件を満たしている間はTrueとする変数OKを用意します
A≤i≤B かつ C≤j≤D で、Siのj文字目が「.」→条件を満たさない→OKをFalseにする
上記以外でSiのj文字目が「#」→条件を満たさない→OKをFalseにする
OKが最後までTrueのままになっているA,B,C,Dの組があればそれが答えになります。
【提出】
# 入力の受け取りリスト
Slist=[]
# 10回
for i in range(10):
# 入力の受け取り
S=input()
# リストへ追加
Slist.append(S)
# A=0~9
for A in range(10):
# B=A~9
for B in range(A,10):
# C=0~9
for C in range(10):
# D=C~9
for D in range(C,10):
# 条件を満たしている間True
OK=True
# i=0~9
for i in range(10):
# j=0~9
for j in range(10):
# A≤i≤B かつ C≤j≤D の場合
if A<=i<=B and C<=j<=D:
# Siのj文字目が「.」ならば
if Slist[i][j]==".":
# 条件を満たさない
OK=False
# そうでなければ
else:
# Siのj文字目が「#」ならば
if Slist[i][j]=="#":
# 条件を満たさない
OK=False
# 条件を満たしていれば
if OK==True:
# 答えの出力
print(A+1,B+1)
print(C+1,D+1)
# 終了
exit()
C - Submask Dif:384
なにやらややこしく見えますが、要するに
Nが「0」の桁はxも「0」
Nが「1」の桁はxは「0」か「1」
となるようにxを作ればいいということです。
例えばN=11であれば2進数に直すと(1011)で、右から0桁目,1桁目,3桁目が「1」です。
つまりxは右から0桁目,1桁目,3桁目が「0」か「1」で、2桁目は「0」になります。
よって
0000=0
0001=1
0010=2
0011=3
1000=8
1001=9
1010=10
1011=11
となります。
xを右から0桁目から順に作っていきます。
まず空の文字「""」が入ったリストxを作ります。
i=0,1,2,...について、
・Nの右からi桁目が「0」ならば
x内の各要素について、左端に「0」を付け足します。
・Nの右からi桁目が「1」ならば
x内の各要素について、左端に「0」または「1」を付け足します。
付け足したものはNewxというリストに記録します。
処理が終わったらx=Newxと更新します。
後はソートして2進数→10進数へ戻せば終わりです。
実装にはいくつかコツがあります。
・Nを2進数へ変換して反転
まずNを2進数へ変換しましょう。名前をNbitとします。
bin(10進数)
とすることで10進数を2進数の文字列へ変換できます。
ただし頭に「0b」という文字が入ります。
(例)bin(11)="0b1011"
邪魔なので2文字目以降を取るようにして「0b」を消しましょう。
更にこのままだと右からi桁目が取りづらいので反転します。
反転は
文字列[::-1]
と書きます。
(例)Nbit="1011"→Nbit[::-1]="1101"
これでNbit[i]とすることでNの右からi桁目を確認できます。
・リストxの要素を順に格納して処理
for 変数 in リスト:
と書くことでリストの要素を変数へ順に格納して処理ができます。
・2進数→10進数へ変換
int(2進数,2)と書くことで2進数の文字列を10進数へ変換できます。
【提出】
# 入力の受け取り
N=int(input())
# Nを2進数へ変換
Nbit=bin(N)
# 「0b」を消す
Nbit=Nbit[2:]
# 反転
Nbit=Nbit[::-1]
# xへ空の文字列を入れておく
x=[""]
# i=0~(Nbitの長さ-1)まで
for i in range(len(Nbit)):
# 新しいxのリスト
Newx=[]
# Nの右からi桁目が「0」ならば
if Nbit[i]=="0":
# xの要素を順にaへ格納して処理
for a in x:
# 先頭に「0」をつける
Newx.append("0"+a)
# Nの右からi桁目が「1」ならば
else:
# xの要素を順にaへ格納して処理
for a in x:
# 先頭に「0」をつける
Newx.append("0"+a)
# 先頭に「1」をつける
Newx.append("1"+a)
# xを更新
x=Newx
# 小さい順に並び替え
x.sort()
# xの要素を順にansへ格納して処理
for ans in x:
# ansを10進数へ変換
print(int(ans,2))
D - Do use hexagon grid Dif:612
BFSを使います。
BFSは幅優先探索(breadth first search)の略称で、グラフを探索するアルゴリズムです。
BFSの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。
黒いマスを辿ってどのマスに進めるかを確認し、連結成分の数を数えていきます。
まず入力を受け取ると同時に黒いマスの座標をStartというリストに入れていきます。
これはスタート地点の候補という意味です。
また、黒いマスの座標をGridという二次元配列で管理します。黒いマスは1、そうでなければ0とします。
例えばGrid[1][3]=1ならば(1,3)は黒いマスということです。
次に訪問済みの座標を記録するvisitedという二次元配列を用意します。
初期値は全てFalseで、既に訪問済みの座標についてはTrueにします。
更にキューを用意します。
これはリストのような物だと思ってください。
詳しくは後述の「dequeについて」を読んでください。
以下の手順で連結成分数を数えていきます。
(1)Startから座標を取り出す
(2)取り出した座標が訪問済みでなければキューに入れて、訪問済みにする
(3)連結成分数を+1する
(4)キューが空になるまで以下を繰り返す
・今いる場所(キューから取り出した座標)から進める座標が黒いマス かつ 訪問済みでなければ
(4_1)訪問済みにする
(4_2)座標をキューに入れる
(5)キューが空になったら(1)へ戻る
Startから座標を取り出した時、
・初めて訪れる座標なら→連結成分数が増える
・他の座標から黒いマスを辿って訪問済みならば(visited=1)→連結成分数は増えず、無視する
ということを繰り返しています。
実装では座標としてマイナスが入力されることがありますが、管理がややこしいで+1000して全て0以上にすると良いです。
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
詳しく知りたい人は以下のページを見てください。
【提出】
# 入力の受け取り
N=int(input())
# 黒いマスの管理
Grid=[[0]*3000 for i in range(3000)]
# スタート地点の候補
Start=[]
# N回
for i in range(N):
# 入力の受け取り
X,Y=map(int,input().split())
# 0以上にするため1000プラスする
X+=1000
Y+=1000
# (X,Y)が黒いマス
Grid[X][Y]=1
# スタート地点の候補
Start.append([X,Y])
# 訪問済み座標の管理
visited=[[False]*3000 for i in range(3000)]
# dequeを用意
from collections import deque
que=deque()
# 答え
ans=0
# (1)Startから座標を取り出す
for X,Y in Start:
# (2)取り出した座標が訪問済みでなければキューに入れて、訪問済みにする
if visited[X][Y]==0:
# キューへ追加
que.append([X,Y])
# 訪問済みにする
visited[X][Y]=1
# 答えをプラス1
ans+=1
# (4)キューが空になるまで
while 0<len(que):
# 今いる座標
NowX,NowY=que.popleft()
# ・今いる場所(キューから取り出した座標)から進める座標が黒いマス かつ 訪問済みでなければ
if Grid[NowX-1][NowY-1]==1 and visited[NowX-1][NowY-1]==0:
# (4_1)訪問済みにする
visited[NowX-1][NowY-1]=1
# (4_2)座標をキューに入れる
que.append([NowX-1,NowY-1])
if Grid[NowX-1][NowY]==1 and visited[NowX-1][NowY]==0:
visited[NowX-1][NowY]=1
que.append([NowX-1,NowY])
if Grid[NowX][NowY-1]==1 and visited[NowX][NowY-1]==0:
visited[NowX][NowY-1]=1
que.append([NowX,NowY-1])
if Grid[NowX][NowY+1]==1 and visited[NowX][NowY+1]==0:
visited[NowX][NowY+1]=1
que.append([NowX,NowY+1])
if Grid[NowX+1][NowY]==1 and visited[NowX+1][NowY]==0:
visited[NowX+1][NowY]=1
que.append([NowX+1,NowY])
if Grid[NowX+1][NowY+1]==1 and visited[NowX+1][NowY+1]==0:
visited[NowX+1][NowY+1]=1
que.append([NowX+1,NowY+1])
# 答えの出力
print(ans)
E - Last Rook Dif:1030
行と列、それぞれについて二分探索で範囲を絞っていきます。
例えばN=10のとき、
・1行目~5行目(1~10の中央)までにいくつルークがあるか聞く。
すなわち(1,5,1,10)を投げる。
・答えが「5」より小さいならば(「4」の場合)
1~5行目のどこかに置ける
・答えが「5」ならば
6~10行目のどこかに置ける
答えが「5」より小さかったとします。
この時点で行の範囲は1~5に絞られます。
・1~3行目(1~5の中央)までにいくつルークがあるか聞く。
すなわち(1,3,1,10)を投げる。
・答えが「3」より小さいならば(「2」の場合)
1~3行目のどこかに置ける
・答えが「3」ならば
4~5行目のどこかに置ける
答えが「3」だったとします。
この時点で行の範囲は4~5に絞られます。
・4~4行目までにいくつルークがあるか聞く。
すなわち(4,4,1,10)を投げる。
・答えが「1」より小さいならば(「0」の場合)
4行目で確定
・答えが「1」ならば
5行目で確定
一般には以下の手順で解きます。
探索範囲の最小をGmin,最大をGmaxとします。
中央はGcen=(Gmin+Gmax)//2です。
・Gmin~Gcen行目(Gmin~Gmaxの中央)までにいくつルークがあるか聞く。
すなわち(Gmin,Gcen,1,N)を投げる。
・答えが(Gcen-Gmin+1)より小さいならば
Gmin~Gcen行目のどこかに置ける
→Gmax=Gcenに更新
・答えが(Gcen-Gmin+1)ならば
(Gcen+1)~Gmax行目のどこかに置ける
→Gmin=Gcen+1に更新
Gmin=Gmaxになったら行が確定
列も同様にします。
【提出】
# 入力の受け取り
N=int(input())
# 行の探索範囲
Gmin=1
Gmax=N
# 列の探索範囲
Rmin=1
Rmax=N
# 20回
for i in range(20):
# 範囲の中央を確認
Gcen=(Gmin+Gmax)//2
Rcen=(Rmin+Rmax)//2
# Gmin~Gcenの個数を確認
print("?",Gmin,Gcen,1,N)
T=int(input())
# 答えが(Gcen-Gmin+1)より小さいならば
if T<Gcen-Gmin+1:
# Gmin~Gcen行目のどこかに置ける
Gmax=Gcen
# それ以外(答えが(Gcen-Gmin+1)ならば)
else:
# (Gcen+1)~Gmax行目のどこかに置ける
Gmin=Gcen+1
# 列も同様
print("?",1,N,Rmin,Rcen)
T=int(input())
if T<Rcen-Rmin+1:
Rmax=Rcen
else:
Rmin=Rcen+1
# 行、列の範囲が定まったら
if Gmin==Gmax and Rmin==Rmax:
# 答えの出力
print("!",Gmin,Rmin)
# 終了
exit()
【広告】
『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