前回のABC211のC問題の耳DPを理解するのに非常に時間がかかったため、ブログ更新の期間が空きました。
ABCは楽しく参加させてもらっていて、この記事は、ABC212に参加した際の記録です。
使用言語はPython3です。レートは茶色中位です。茶コーダーのため、厳密性などには欠けます。私が理解した内容で書いていきます。
今回から8問体制になるようで、D問題、E問題あたりが増えるようです。
私は今まで通り、C問題まではスムーズに解けたら良いな。D問題もできたら解きたいな。Eが解けちゃったりしたらすごく嬉しいな。と思い参加しました。
A – Alloy
標準入出力と、条件分岐が書けるかが問われる問題。1行に複数変数がある場合は、Python3の場合は、map(input().split())
を利用するのが良いですね。
あとは、問題文に書かれている通りにコードを書いていけばOKです。
# AtCoder Beginner Contest 212
# A - Alloy
A,B=map(int,input().split())
if 0<A and B==0:
print("Gold")
elif A==0 and 0<B:
print("Silver")
else:
print("Alloy")
B – Weak Password
繰り返し処理と条件分岐が書けるかが問われる問題。
私はこの問題、コンテスト中解けませんでした。難しくないですか、この問題。
翌日落ち着いて、考えたら普通に解けたのですが、コンテスト中はWAが出て、落ち着いて解けなかったです。
以下、この問題の方針です。
- すべての桁の数が同じ場合は”Weak”を出力して終了する。
- 各桁間の差が1であれば”Weak”を出力して終了する。
- 上記2つ以外のパスワードであれば”Strong”を出力する。
2を実施するための前処理として、0が出現したらその桁以降は+10しておく。
これらをコードに落とし込めばOKですね。
# AtCoder Beginner Contest 212
# B - Weak Password
S=list(input())
if S[0]==S[1]==S[2]==S[3]:
print("Weak")
exit()
nums=[]
for i in range (4):
nums.append(int(S[i]))
has_0_appeared=False
for i in range (4):
if nums[i]==0:
has_0_appeared=True
if has_0_appeared==True:
nums[i]=nums[i]+10
a,b,c,d=nums
if b==a+1 and c==b+1 and d==c+1:
print("Weak")
exit()
print("Strong")
C – Min Difference
Pythonのbisectモジュールが使用できるかが問われる問題。
今回、Cも解けませんでした。答え用の変数の初期値が小さかったです。(10**9+7を10*9+7としていました。)
冒頭、C問題まではスムーズに解けたらとか書いていましたが、まさかA問題だけしか解けないなんて…
2つの数列から1つずつ取り出した時の差の絶対値の最小値なので、すべての組み合わせを試したら答えはわかりますが、そうとすると、実行時間制限に引っ掛かります。
効率よく、差の絶対値が最小にできるような組み合わせを考えます。
Bの配列をソートしておき、Aの配列から1つ取り出した後、Bの配列のどこに入るかがわかれば、その前後を見るだけでよさそうなことがわかります。
なぜなら、それよりも前(または後ろ)は、2つの値の差の絶対値は絶対に大きくなるからです。
あとは、Pythonのbisectモジュールのbisect_leftを利用したら、Aからとってきた数が、Bの配列のどこ(index番号)に入るかがわかるため、その前後で差の絶対値を確認して、今までの最小値よりも小さければ答えを更新していけばOKです。
実装上の小細工としては、Bの配列に、最終的な答えに影響しないような小さい数と、大きい数を追加してからソートすると、場合分けをしなくて済むようになります。
# AtCoder Beginner Contest 212
# C - Min Difference
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
B.append(-100_000_000_000_000_000)
B.append(100_000_000_000_000_000)
B.sort()
ans=10**9+7
for i in range (N):
t=bisect.bisect_left(B,A[i])
ans=min(ans,abs(B[t]-A[i]),abs(B[t-1]-A[i]))
print(ans)
コメント