ABC271(AtCoder Beginner Contest 271) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
更新時はツイッターにて通知します。
https://twitter.com/AtCoder4
京セラ株式会社様について
A - 484558 Dif:28
Nを16進数へ変換します。やり方がわからなかったら「python 16進数」でググりましょう。
hex(N)とすることでNを16進数変換できます。
試しに16進数変換したものを出力してみます。Nは181としてみましょう。
N=181
N=hex(N)
print(N)
【出力結果】
0xb5
前に余計な「0x」がつきました。いらないのでこれは消します。
N[2:]とすることでNの2文字目以降を取り出すことができます。(先頭の「0」は0文字目、次の「x」は1文字目と数えます)
N=181
N=hex(N)
N=N[2:]
print(N)
【出力結果】
b5
先頭の「0x」は消えました。次はbを大文字にしたいですね。またやり方がわからなかったら「python 大文字」などでググりましょう。
N.upper()とすることでNの文字を全て大文字にできます。
N=181
N=hex(N)
N=N[2:]
N=N.upper()
print(N)
【出力結果】
B5
最後に桁数が1桁の場合は先頭に0をつけるようifで条件分岐します。
桁数(=文字数)はlen(N)として確認します。
0は文字列としてくっつけるので、「"0"+」とダブルクオーテーションをつけることに注意してください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
N=int(input())
# 16進数に変換
N=hex(N)
# 2文字目以降を取り出し(「0x」を消す)
N=N[2:]
# 全て大文字へ変換
N=N.upper()
# Nの文字数が1ならば
if len(N)==1:
# 先頭に「0」をつける
print("0"+N)
# そうでなければ
else:
# Nを出力
print(N)
B - Maintain Multiple Sequences Dif:97
リスト(配列)にリスト(配列)を追加することで二次元配列を作ることができます。
例えばa=[]という空のリストに
[0]
[4,1,2,3,4]
[5,6,7,8,9,10]
を追加すると
a=[[0],[4,1,2,3,4],[5,6,7,8,9,10]]
となります。
二次元配列の要素は二つの番号で指定します。
例えば
a[1][1]=1
となります。これは1番目のリストの1番目の要素という意味です。(先頭は0番目、次が1番目です)
よって1番目のリスト=[4,1,2,3,4]の1番目の要素[1]が指定されています。
同様に
a[2][3]=8
となります。
入力を受け取り、リストに追加していくことで二次元配列を作ればa[s][t]という形でs番目の数列のt項を確認できます。
ただし、空のaにそのまま追加していくと1番目の数列=a[0],2番目の数列=a[1]と番号がずれてしまうのでaに[0]等てきとうなリストをいれて番号をずらしておきます。
【提出】
# 入力の受け取り
N,Q=map(int,input().split())
# 空のリストを作る
a=[]
# てきとうな数列で0番目を埋める
a.append([0])
# N回
for i in range(N):
# 入力の受け取り
La=list(map(int,input().split()))
# aに追加
a.append(La)
# Q回
for i in range(Q):
# 入力の受け取り
s,t=map(int,input().split())
# s番目のリストのt番目を出力
print(a[s][t])
C - Manga Dif:842
a：1 2 3 5 6 8 9 9 100 200
の場合を考えます。
まずいらない漫画を考えます。
・2冊以上ある漫画の2冊目以降
・巻数がNより大きい漫画
これらは全て売ります。条件に合うのは9,100,200です。3冊売れると記録します。
残った漫画は
1 2 3 5 6 8 9
です
4巻がないのでまず2冊を売って手に入れます。売れる漫画は残り1冊です。
次に7巻がないのですが、売れる漫画が足りませんので、手持ちから更にどれかを売って手に入れます。
当然残ったうちで最も大きいもの、すなわち9巻を売るのが最適です。
このように足りない巻があったら持っている漫画の巻数が大きい方から売っていくということを繰り返します。
ただし、売ろうとしている巻が次に読もうとしている巻より小さければ終了します。
具体的な実装は以下のとおりです。
(1)売る漫画と残す漫画を分ける(売る漫画の冊数を記録する)
(2冊以上あるか、巻数がNより大きい漫画は売る)
(2)持っている漫画のリストを用意する
(readは持っている漫画をTrueとする。comicsは持っている漫画のリストを作る)
(3)i=1,2,3,...について
・すでに持っている漫画ならば(read[i]=True)
次のiへ
・まだ持っていない漫画ならば(read[i]=False)
・売る漫画が2冊以上あれば
売って手に入れる
・売る漫画が2冊なければ
持っている漫画の巻数が大きい順に売る
(4)read[i]=Trueとなっているもっとも大きいiが答え
【提出】
# 入力の受け取り
N=int(input())
a=list(map(int,input().split()))
# 売る漫画の数
amari=0
# 各巻の冊数確認
count=[0]*(N+1)
# 持っている漫画()
comics=[]
# 持っている漫画
read=[False]*(N+1)
# 0巻を持っている漫画とする
read[0]=True
# (1)売る漫画と残す漫画を分ける(売る漫画の冊数を記録する)
# (2)持っている漫画のリストを用意する
# i=0~(N-1)
for i in range(N):
# 巻数がN以下 かつ a[i]の持っている冊数が0
if a[i]<=N and count[a[i]]==0:
# 1冊持っていると記録
count[a[i]]=1
# comicsに記録
comics.append(a[i])
# a[i]は持っている漫画と記録
read[a[i]]=True
# そうでない場合
else:
# 売る漫画にカウント
amari+=1
# 持っている漫画をソート
comics.sort()
# 読もうとしている漫画
i=1
# 売ろうとしている漫画
k=len(comics)-1
# i≤Nの間
while i<=N:
# i巻を持っていなければ
if read[i]==False:
# 売る漫画が2冊以上あれば
if 2<=amari:
# 2冊売る
amari-=2
# i巻を買う
read[i]=True
# 次の巻へ
i+=1
# そうでなければ
else:
# 0≤k かつ 読もうとしている巻<売ろうとしている巻 ならば
if 0<=k and i<comics[k]:
# 売る
amari+=1
# 持っている漫画から外す
read[comics[k]]=False
# kをマイナス1
k-=1
# そうでなければ
else:
# 終了
break
# そうでなければ
else:
# 次の巻へ
i+=1
# 初期値
i=0
# 持っている巻の最大を探す
# i≤N かつ i巻を持っている
while i<=N and read[i]==True:
# 次のiへ
i+=1
# (i-1)巻まで持っている
print(i-1)
D - Flip and Adjust Dif:886
1枚目のカードまでであり得る総和とその表裏の組み合わせ
2枚目のカードまでであり得る総和とその表裏の組み合わせ
...
と確認していきます。
以下の例を考えます。
N S：3 9
a1 b1：1 2
a2 b2：3 4
a3 b3：5 6
最初は0とします。
1枚目に表を選べば総和は1、裏を選べば総和は2になります。
こうしてできる総和(1,2)を記録します。同時に表裏の組み合わせを記録します。
1：H
2：T
表裏の記録は連想配列を使います。詳細は後述の「defaultdict(連想配列)について」を読んで下さい。
2枚目に表を選べば+3、裏を選べば+4になります。
総和は(1,2)がありましたから、これらそれぞれに+3,+4をして(4,5,5,6)になります。が、5が重複しています。
重複したものはいりませんので(4,5,6)にします。(実装ではsetを使います)
同様に表裏の組み合わせを記録します。1に+3したものはHH、1に+4したものはHT、...という形です。5はTHでもHTでも構いません。
4：HH
5：HT(またはTH)
6：TT
これを繰り返して最後にSになっている表裏の組み合わせがあるかを確認します。
defaultdict(連想配列)について
連想配列は別名「辞書」とも言い、「キー」と対応する「値」を登録できるデータ構造です。
pythonでは標準で搭載されており、dict()と書くことで使えます。
しかし標準のものはデフォルトの値(初期値)が設定できず、存在しない「キー」にアクセスする可能性があるときの処理が面倒です。
defaultdictは標準の連想配列と同様に使えて、さらに初期値を設定できます。
値の割当が行われていない「キー」には自動的に初期値が割り振られます。
「使い方」
・インポート：from collections import defaultdict
・作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
・キー、値の登録【O(1)】：変数名[キー]=値
・値の参照【O(1)】：変数名[キー]
# インポート：from collections import defaultdict
from collections import defaultdict
# 作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
AsArray=defaultdict(int)
# キー、値の登録【O(1)】：変数名[キー]=値
# キー、値ともに数値、文字列、タプルを入れることが可能
# ただしリストをキーにすることはできない
AsArray[1]=10
AsArray["Men"]="Taro"
AsArray[(1,2)]=[3,4,5]
# 値の参照【O(1)】：変数名[キー]
print(AsArray[1])
print(AsArray["Men"])
print(AsArray[(1,2)])
# 値が割当されていないキーも参照可能(値はデフォルト値)
print(AsArray[99])
【提出】
# 入力の受け取り
N,S=map(int,input().split())
# i番目までのありうる和
# 重複を記録しないようにsetで
iSum=set()
# defaultdictのインポート
from collections import defaultdict
# 表裏の組み合わせ記録
# 初期値は空文字列=""
HT=defaultdict(str)
# 0を追加
iSum.add(0)
# i=1~N
for i in range(1,N+1):
# 入力の受け取り
a,b=map(int,input().split())
# 新しい和
NewiSum=set()
# 新しい表裏の組み合わせ
NewHT=defaultdict(str)
# x：iSumの要素それぞれ
for x in iSum:
# 組み合わせの長さがiよりちいさければ
if len(HT[x+a])<i:
# (x+a)が作れると記録
NewHT[x+a]=HT[x]+"H"
NewiSum.add(x+a)
# 組み合わせの長さがiよりちいさければ
if len(HT[x+b])<i:
# (x+b)が作れると記録
NewHT[x+b]=HT[x]+"T"
NewiSum.add(x+b)
# 更新
iSum=NewiSum
HT=NewHT
# Sの組み合わせがあれば
if len(HT[S])==N:
# 「Yes」を出力
print("Yes")
# 表裏の組み合わせを出力
print(HT[S])
# そうでなければ
else:
# 「No」を出力
print("No")
【広告】
『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