ABC212参戦記

プログラミング

前回の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が出て、落ち着いて解けなかったです。

以下、この問題の方針です。

  1. すべての桁の数が同じ場合は”Weak”を出力して終了する。
  2. 各桁間の差が1であれば”Weak”を出力して終了する。
  3. 上記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)

コメント

タイトルとURLをコピーしました