ABC205(AtCoder Beginner Contest 205) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
A - kcal
1mLあたりのカロリーはA×(1/100)となるので、BmlあたりのカロリーはA×(1/100)×Bとなります。
少数のある計算は本来誤差が出る可能性があるためよくないのですが、本問については
想定解答との絶対誤差または相対誤差が10^−6以下であれば正解として扱われる。
と記載があるため誤差が多少あっても問題ありません。
また、入力例1について自分の書いたコードをテストした時、「90」ではなく「90.0」が出力されて不安になった方もいるかもしれませんが、AtCoderでは特別な指示がない限り「90」も「90.0」も同じものとみなされます。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
A,B=map(int, input().split())
# A×(1/100)×Bを出力
print(A*(1/100)*B)
B - Permutation Check
1,2,3,...,NがそれぞれAに存在するかチェックすればよいです。
長さ(N+1)ですべての要素がFalseのリスト numbers を用意し、1があればnumbers[1]=True,2があればnumbers[2]=True,...と更新していきます。
(長さがNではなくN+1なのは0から始まるため、すなわちnumbers[0]も存在するからです)
もしnumbers[1]~[N]のなかにひとつでもFalseがあればNo、全てTrueならYesを出力します。
途中でプログラムを終了するときはexit()と書きます。
【提出】
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# 数1,2,3,...Nが存在するかチェックするリスト
numbers=[False]*(N+1)
# i=0~N-1まで
for i in range(N):
# A[i]が存在する⇔numbers[A[i]]=True
numbers[A[i]]=True
# i=1~Nまで
for i in range(1,N+1):
# numbers[i]=False⇔iが存在しないなら
if numbers[i]==False:
# Noを出力
print("No")
# 終了
exit()
# イエスを出力
print("Yes")
C - POW
愚直にpow(A,C),pow(B,C)を計算すると数が大きくなりすぎてTLEします。
大小関係は以下3つの要素によって決まります。
・Cの偶奇
①C：偶数、②C：奇数
・Aの符号
①A：0以上(+)、②A：0未満(-)
・Bの符号
①B：0以上(+)、②B：0未満(-)
・|A|,|B|の大小関係
①|A|<|B|、②|A|=|B|、③|A|>|B|
以上の組み合わせは2×2×2×3=24通りです。
少々面倒ですがひとつひとつどうなるか確認しましょう。
よくわからなくなったら具体的な数をA,B,Cに当てはめて計算してみればOKです。
あとはこれをif文でコードにすれば解けます。
【提出A】
表をじっくり見てみるともう少し簡単にできそうです。
たとえばCが偶数のときはA,Bの符号によらず、|A|,|B|の大小関係だけで出力結果が決まります。
省略可能な場所を考えると以下のようになります。
「*」は任意(どんな値でもよい)ことを表します。
こちらの表を使うと短くコードが書けます。
【提出B】
【提出A】
# 入力の受け取り
A,B,C=map(int, input().split())
# C：偶数
if C%2==0:
# A：0以上
if 0<=A:
# B：0以上
if 0<=B:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# B：0未満
if B<0:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# A：0未満
if A<0:
# B：0以上
if 0<=B:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# B：0未満
if B<0:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# C：奇数
if C%2==1:
# A：0以上
if 0<=A:
# B：0以上
if 0<=B:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# B：0未満
if B<0:
# |A|<|B|
if abs(A)<abs(B):
# 「>」を出力
print(">")
# |A|=|B|
if abs(A)==abs(B):
# 「>」を出力
print(">")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# A：0未満
if A<0:
# B：0以上
if 0<=B:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「<」を出力
print("<")
# |A|>|B|
if abs(A)>abs(B):
# 「<」を出力
print("<")
# B：0未満
if B<0:
# |A|<|B|
if abs(A)<abs(B):
# 「>」を出力
print(">")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「<」を出力
print("<")
【提出B】
# 入力の受け取り
A,B,C=map(int, input().split())
# C：偶数
if C%2==0:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# C：奇数
if C%2==1:
# A：0以上
if 0<=A:
# B：0以上
if 0<=B:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# B：0未満
if B<0:
# 「>」を出力
print(">")
# A：0未満
if A<0:
# B：0以上
if 0<=B:
# 「<」を出力
print("<")
# B：0未満
if B<0:
# |A|<|B|
if abs(A)<abs(B):
# 「>」を出力
print(">")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「<」を出力
print("<")
D - Kth Excluded
二分探索でも解けますが、実装がめんどうなのでクエリを先読みし、Kの小さい順から確認する方法を紹介します。
A1,A2,…,ANのいずれとも異なる正整数を「良い整数」と呼びましょう。
まずAの値それぞれについて、「Aiより前にいくつ良い整数があるか」を確認します。
たとえば
A：3 6 9 10 15
の場合、以下のようになります。
実装の都合上、Aの左端に0、右端に∞(10^18より大きな数)を置いています。
下部にある数がAの値までにいくつ良い整数があるかを表します。
例えば
A1=3について、3より前に1,2があるので「2」
A2=6について、6より前に1,2.4.5があるので「4」
となっています。
計算は
「A[i+1]より前の良い整数の数」=「A[i]より前の良い整数の数」+A[i+1]-A[i]-1
となります。
例えばA[3]ならば
「A[3]より前の良い整数の数」=「A[2]より前の良い整数の数」+A[3]-A[2]-1=4+9-6-1=6
となります。
この表を使えばk番目の良い整数を簡単に計算できます。
k=7であれば
「A[4]より前の良い整数の数」：6個
「A[5]より前の良い整数の数」：10個
ですからA[4]~A[5]＝10~15の間に答えがあることがわかります。
さらに「A[4]より前の良い整数の数」は6個あったので、7番目の良い整数は
A[4]+(k-「A[4]より前の良い整数の数」)=10+(7-6)=11
で7番目の良い整数は「11」となることがわかります。
実装は以下の手順で行います。
(1)クエリを先読みする(何番目のクエリなのかも同時に記録する)
(2)クエリをKの小さい順にソートする
(3)i=0~Nについて
「A[i]より前の良い整数の数」=order_left
「A[i+1]より前の良い整数の数」=order_right
を確認する
(4)・A[i]より前の良い整数の数」<k<=「A[i+1]より前の良い整数の数」ならば
k番目の良い整数を計算して記録
次のkへ
・そうでないなら
次のiへ
(5)答えの出力
クエリを先読みする際、何番目のクエリなのかも同時に記録することで答えを出力するときクエリの順番に出力できるようにしています。
「A[i]より前の良い整数の数」(=order_left)については最初を0とし、次のiへ行くときに「A[i+1]より前の良い整数の数」(=order_right)で更新してしまえばよいです。
【提出】
# 入力の受け取り
N,Q=map(int, input().split())
A=list(map(int, input().split()))
# Aの両端に0,大きい数(10^20)を追加
A=[0]+A+[10**20]
# クエリ格納用
query=[]
# Q回
for i in range(Q):
# 入力の受け取り
K=int(input())
# クエリを格納
query.append([K,i])
# kの小さい順にソート
query.sort()
# 答えの格納リスト
ans=[0]*Q
# 「A[i]より前の良い整数の数]
# 最初は0
order_left=0
# x番目のクエリ
x=0
# i=0~Nまで
for i in range(N+1):
# 「A[i+1]より前の良い整数の数]=「A[i]より前の良い整数の数]+(A[i+1]-A[i]-1)
order_right=order_left+A[i+1]-A[i]-1
# x<Qの間
while x<Q:
# クエリの値
k=query[x][0]
# クエリの番号(q番目のクエリ)
q=query[x][1]
# 「A[i]より前の良い整数の数]<クエリの値≦「A[i+1]より前の良い整数の数]ならば
if order_left<k<=order_right:
# q番目のクエリの値=A[i]+(k-「A[i]より前の良い整数の数])
ans[q]=A[i]+k-order_left
# 次のxへ
x+=1
# そうでない場合(「A[i+1]より前の良い整数の数]≦クエリの値)
else:
# 「A[i]より前の良い整数の数]→「A[i+1]より前の良い整数の数]へ更新
order_left=order_right
# 次のiへ
break
# 答えを出力
for a in ans:
print(a)
【広告】
『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】