ABC212の解説。
A - Alloy
解説
Gold, Silver, Alloyを問題文のとおりに条件分岐してあげるとAC。
コード
a, b = map(int, input().split())
if 0 < a and b == 0:
print('Gold')
elif a == 0 and 0 < b:
print('Silver')
elif 0 < a and 0 < b:
print('Alloy')
B - Weak Password
解説
暗証番号の強さについて求める問題。
弱い暗証番号というのは、
(1)同じ数が4つ続いているもの
(2)0-9の数字が各桁で1ずつ増えているもの
である。
(1)については、s.count(s[0])で文字列のはじめの数字について、文字列sの文字を数え、4であれば、すべて同じ数なので、Weak。
(2)については、数字の折返しを含めて、tempを'0123456789012'と指定する。この中にsがあれば、各桁で1ずつ増えるものなっているので、Weak。
それ以外のものについては、Strongを出力する。
コード
s = input()
temp = '0123456789012'
if s.count(s[0]) == 4:
print('Weak')
elif s in temp:
print('Weak')
else:
print('Strong')
C - Min Difference
解説
数列A、数列Bの中から、差の最小値を持つものを出力する問題。
単純に2重ループをして解けるように見えるが、N、Mの最大値が$2 \times 10^5$をとっているので、計算量が$O(NM)$となってしまい、実行時間が間に合わない。では、どうすればいいか。
これを実装するために、数直線を用いる。
数直線上に表すには、数字を並び替えてあげる必要があるので、先にソートしておく。
まず、A、Bのそれぞれの値をみて、値の絶対値の差を取る。
次に、今見た数値で小さい方をもつ数列から、次の値を参照する。同様に値の絶対値の差をとっていく。こうすることで、最終的に値の大きいものに値の小さいものができるだけ近づいて、絶対値の差を求めることができるので、最小値を求めることができる。
コード
n, m = map(int, input().split())
alist = list(map(int, input().split()))
blist = list(map(int, input().split()))
alist.sort() # 数列Aをソート
blist.sort() # 数列Bをソート
result = 10**9+7 # 比較する値の設定
a = 0
b = 0
while a < n and b < m: # AとBの値がすべて取れるような条件の指定
if abs(alist[a]-blist[b]) < result: # 結果より絶対値の差が小さければ
result = abs(alist[a]-blist[b]) # 値を更新
if alist[a] < blist[b]: # 値の小さい方をもつ数列の値を1つずらす
a += 1
else:
b += 1
print(result)
D - Querying Multiset
解説
ボールと袋の条件分岐問題。制約上、そのまま実装することはできない。したがって、今回はheapというものを使用する。
heapについては以下の記事をご覧いただきたい。
コードの関係上、操作2から説明する。
操作2は、袋に入っているすべてのボールについて、そこに書かれている数を足し合わせるというもの。しかし、これをいちいちすべてのボールについて、足し合わせていると、膨大な計算量になる。したがって、操作3でボールを取り出す際に、今まで操作2で足し合わせたものを足せば良い。
操作3は、袋に入っている最小値のかかれたボールを取り出すというもの。これは、heapq.heappop()で難なく最小値をとりだすことができる。通常のpopであれば、計算量は$O(N)$だが、heappopは、$O(logN)$なので、十分少ない。取り出す際に、操作2で足し合わせた数値を足してあげることで正しい答えが出力できる。
操作1は、袋にボールを入れてあげる作業だ。これは、heapq.heappush()で実装できるが、ひとつ注意点がある。それは、ボール入れるときに操作2で足した値を引いてあげることである。操作1で値を入れるとき、もともと入っているボールにかかれている数値は操作2で足した値分、大きくなっている。つまり、その分引いてあげることで帳尻を合わせることができる。
コード
import heapq
q = int(input())
sack = []
heapq.heapify(sack)
total = 0
for i in range(q):
query = list(map(int, input().split()))
if query[0] == 1:
heapq.heappush(sack, query[1]-total)
elif query[0] == 2:
total += query[1]
else:
ans = heapq.heappop(sack)
print(ans+total)
編集後記
ABCDまで解説すると、時間がかかる.
けど、勉強になる.