ABC212のA,B,C,D,E問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、その他のご意見・ご要望などはマシュマロまでお気軽にどうぞ！
Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト : プレゼントしていただけると、やる気が出ます！
よかったらLGTMや拡散していただけると喜びます！
目次
ABC212 まとめ
A問題『Alloy』
B問題『Weak Password』
C問題『Min Difference』
D問題『Querying Multiset 』
E問題『Safety Journey』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC212 まとめ
全提出人数: 7893人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 27分 | 5662(5431)位 |
| 400 | ABC----- | 600 | 97分 | 4616(4386)位 |
| 600 | ABC----- | 600 | 42分 | 3785(3557)位 |
| 800 | ABC----- | 600 | 13分 | 2950(2725)位 |
| 1000 | ABCD---- | 1000 | 67分 | 2192(1969)位 |
| 1200 | ABCD---- | 1000 | 36分 | 1573(1355)位 |
| 1400 | ABCDE--- | 1500 | 125分 | 1101(891)位 |
| 1600 | ABCDE--- | 1500 | 63分 | 759(555)位 |
| 1800 | ABCDE--- | 1500 | 40分 | 511(321)位 |
| 2000 | ABCDE--- | 1500 | 21分 | 340(171)位 |
| 2200 | ABCDE-G- | 2100 | 105分 | 212(84)位 |
| 2400 | ABCDE-G- | 2100 | 76分 | 133(40)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3611 | 98.4 % | 71.8 % | 36.7 % | 7.8 % | 0.7 % | 0.0 % | 0.1 % | 0.0 % |
| 茶 | 1345 | 99.5 % | 98.1 % | 85.6 % | 40.1 % | 2.7 % | 0.1 % | 0.3 % | 0.1 % |
| 緑 | 1046 | 99.6 % | 98.8 % | 97.2 % | 73.4 % | 15.7 % | 0.4 % | 0.4 % | 0.0 % |
| 水 | 635 | 99.5 % | 99.2 % | 98.9 % | 90.7 % | 56.1 % | 0.9 % | 3.6 % | 0.0 % |
| 青 | 372 | 100.0 % | 99.7 % | 100.0 % | 97.6 % | 85.5 % | 16.1 % | 19.4 % | 2.1 % |
| 黄 | 176 | 94.3 % | 93.8 % | 93.8 % | 94.3 % | 88.1 % | 25.6 % | 53.4 % | 7.4 % |
| 橙 | 37 | 97.3 % | 97.3 % | 97.3 % | 97.3 % | 97.3 % | 48.6 % | 73.0 % | 32.4 % |
| 赤 | 19 | 89.5 % | 89.5 % | 89.5 % | 94.7 % | 89.5 % | 89.5 % | 100.0 % | 63.2 % |
※表示レート、灰に初参加者は含めず
A問題『Alloy』
問題ページ：A - Alloy
灰コーダー正解率：98.4 %
茶コーダー正解率：99.5 %
緑コーダー正解率：99.6 %
考察
問題文どおりにif文を書けばいいです。条件は以下の3つです。
- $0 < A$ かつ $ B = 0$ なら
Gold - $A = 0$ かつ $0 < B$ なら
Silver - $0 < A $ かつ $0 < B $ なら
Alloy
$0\lt{A+B}$ ですから、$A=0$ かつ $B = 0$ はありません。（無から無を生成するのは意味がわかりませんね）
よく考えると、$A,B$ それぞれが $0$ かどうかだけ判定すれば良いので、以下のように判定を簡略化できます。
- $B=0$ なら
Gold - $A=0$ なら
Silver - 上 $2$ つのどちらでもないなら
Alloy
コード
def main():
A, B = map(int, input().split())
if B == 0:
print("Gold")
elif A == 0:
print("Silver")
else:
print("Alloy")
if __name__ == '__main__':
main()
B問題『Weak Password』
問題ページ：B - Weak Password
灰コーダー正解率：71.8 %
茶コーダー正解率：98.1 %
緑コーダー正解率：98.8 %
考察
問題文の意味がわかりづらいので、$20$ 種類しかない弱いパスワードを全列挙してみます。
全部同じ数字: 0000,1111,2222,3333,4444,5555,6666,7777,8888,9999
数字が4つ連続している: 0123,1234,2345,3456,4567,5678,6789,7890,8901,9012
これらを直接打ち込んで比較してもACできますが、for文などでこれらの文字列を作ったほうが楽です。
コード
20種類の弱いパスワードを書いて比較するコード
打ち間違えの恐れがあるので、おすすめはしません。
def main():
X = input()
P = ['0000', '1111', '2222', '3333', '4444', '5555', '6666', '7777', '8888', '9999',
'0123', '1234', '2345', '3456', '4567', '5678', '6789', '7890', '8901', '9012']
print('Weak' if X in P else 'Strong')
if __name__ == '__main__':
main()
20種類の弱いパスワードをfor文で生成して比較するコード
def main():
X = input()
P = [str(i) * 4 for i in range(10)] # とりあえず0000～9999を作る
# ここで0123～9012を作る
for i in range(10):
s = ""
for j in range(4):
s += str((i + j) % 10) # 9の次は0なので、i + j = 10のとき0にしたい
P.append(s)
print('Weak' if X in P else 'Strong')
if __name__ == '__main__':
main()
真面目に判定するコード
def main():
def solve():
if len(set(X)) == 1:
return 'Weak' # Xの文字種が1種類のみです
for i in range(3):
if (int(X[i]) + 1) % 10 != int(X[i + 1]):
return 'Strong' # 1箇所でも連続していなければ、その時点で強いパスワードです
return 'Weak' # 1234のような4連続の数字なので、弱いパスワードです
X = input()
print(solve())
if __name__ == '__main__':
main()
C問題『Min Difference』
問題ページ：C - Min Difference
灰コーダー正解率：36.7 %
茶コーダー正解率：85.6 %
緑コーダー正解率：97.2 %
考察
もちろん、すべての $A_i$ と $B_j$ の組を試すとTLEになります。
ある $A_i$ を $1$ つに対して、数列 $B$ の中で『差の絶対値の最小』になる相手を高速に探すことを考えます。これができれば、数列$A$ の $N$ 個ある全要素に対して同様に 『差の絶対値の最小』 を求めることで、この問題を解くことができます。
そのために、二分探索を使います。
二分探索を使う
二分探索は、ソートされた数列 $L$ にある値 $x$ を挿入するとき、$x$ が何番目に入るかを $O(log\, N)$で求めることができます。（二分探索の詳しい説明はググってください）
下図の数列$B$ の $5$ と $9$ の間に $A_i$ が入るとわかったとき、『差の絶対値の最小』の候補は、すぐ左の $|A_i - 5|$ か、すぐ右の $|9-A_i|$です。これらより遠くにある$|A_i-2|$ や $|13-A_i|$ は最小値にはなり得ません。そのため、両隣 $2$ 箇所だけ計算してみて、小さいほうが答えです。
まとめ
さて、この問題を解くアルゴリズムは以下の通りです。
- 数列 $B$ をソートする
- forループを使って、すべての $A_i$ で $B$ を二分探索して、すべての $A_i$ に対する最適解を求める
- そのうち最小のものが答え
ただし、$B$ の最大値よりも $A_i$ が大きい場合と、$B$ の最小値よりも $A_i$ が小さい場合に、配列外参照を起こさないように注意してください。（if文でチェックします）
二分探索 $1$ 回の計算量は$O(log\, M)$ なので、長さ$N$ の 数列$A$ の要素すべてについて行うと $O(N log\,M)$ です。また、$B$ のソートの計算量は$O(Mlog\,M)$ です。したがって、全体の計算量は$O((N+M)log\,M)$です。
コード
def main():
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
B.sort() # 二分探索するので、Bはソートしておきます
INF = float('INF')
ans = INF # 正の無限大で初期化します
for a in A:
i = bisect.bisect_left(B, a) # bisect_rightでもいいです
# 配列外やB[-1]を参照するのを防ぐために、if文を使います
if 0 <= i - 1 < M:
b1 = B[i - 1]
ans = min(ans, abs(a - b1))
if 0 <= i < M:
b2 = B[i]
ans = min(ans, abs(a - b2))
print(ans)
if __name__ == '__main__':
main()
D問題『Querying Multiset 』
問題ページ：D - Querying Multiset
灰コーダー正解率：7.8 %
茶コーダー正解率：40.1 %
緑コーダー正解率：73.4 %
考察
$3$ つの操作を簡単に書き直します。
- 操作 $1$ : $X_i$ が書かれたボールを袋に入れる
- 操作 $2$ : 袋に入っているすべてのボールの数字に $X_i$ を足す
- 操作 $3$ : 袋から『数字が一番小さいボール』を取り出して、書かれている数字を出力する
操作2さえなければ簡単だが
袋全体のボールの数字を書き換える操作 $2$ さえなければ、優先度付きキュー（Priority Queue, Pythonではheapqモジュール)を使うだけで簡単に解けます。
優先度付きキューは、次の操作を以下の計算量で行えるデータ構造です。要素の追加や削除があるときに、ソートの代わりに使うものだと思ってください。
- 最小の要素の取得：$O(1)$
- 最小の要素の削除：$O(log\,N)$
- 要素の追加：$O(log\,N)$
もし操作 $2$ がなければ、操作 $1$ が来たら要素を追加、操作 $3$ が来たら要素を取得・出力・削除をするだけで解けてしまいます。
操作2 の処理を考える
しかし、操作 $2$ が来るたびに優先度付きキュー内の数字をすべて書き換えるとTLEになります。（$10$ 万個のボールの数字を $10$ 万回書き換えるケースができます）そもそも、優先度付きキューは通常の実装では要素の書き換えをすることができません。
そこで、操作 $2$ が来たとき、優先度キュー内の要素は一切変更せず、代わりに全体に足された値を変数 $S$ で管理することにします。そして、以下のように操作をすれば、ボールの数字そのものを書き換えることなく、ボールと書かれた数字を優先度付きキューで管理することができます。
- はじめ は 袋（優先度付きキュー）は空、$S=0$ である
- 操作 $2$ では $S$ に $X_i$ を足す（$S \leftarrow{S+X_i}$）
- 操作 $3$ で袋から最小のボール $X_{min}$ を取り出したあと、$X_{min}+S$ を出力する（$S$ が袋全体に足されているからです）
- 操作 $1$ で袋にボール $X_i$ を追加するとき、代わりに $X_i - S$ を追加する（このまま $X_i$ を追加すると、袋に$X_i + S$ のボールが追加されてしまいます。そのため、$S$ を引いて $(X_i - S) + S = X_i$ となるように調整してあげます）
計算量は $O(Qlog\, Q)$です。
コード
# python標準ライブラリのheapqは大変使いづらいので、使いやすいようクラスにしておくと良いです
# なお、このクラスにバグがあっても責任は一切取りません、自分で書いてね
class PriorityQueue:
def __init__(self, a=None):
import heapq
self.heapq = heapq
self.__container = []
if a:
self.__container = a[:]
self.heapq.heapify(self.__container)
@property
def is_empty(self):
return not self.__container
def pop(self):
return self.heapq.heappop(self.__container)
def push(self, x):
self.heapq.heappush(self.__container, x)
def sum(self):
return sum(self.__container)
def __len__(self):
return len(self.__container)
def __str__(self):
return str(sorted(self.__container))
def __repr__(self):
return self.__str__()
def main():
Q = int(input())
pq = PriorityQueue()
S = 0
for _ in range(Q):
q = list(map(int, input().split()))
query = q[0]
if query == 1:
x = q[1]
pq.push(x - S) # x + S - S = x です
elif query == 2:
x = q[1]
S += x # 袋全体にx足します
elif query == 3:
y = pq.pop()
print(y + S) # もともとyが書かれたボールに、袋全体のSを足します
if __name__ == '__main__':
main()
E問題『Safety Journey』
問題ページ：E - Safety Journey
灰コーダー正解率：0.7 %
茶コーダー正解率：2.7 %
緑コーダー正解率：15.7 %
考察
無向グラフが与えられます。都市 $1$ からはじめて、$K$ 回移動した後、最後に都市 $1$ に戻るルートの組み合わせ数を求める問題です。$K$ は最大で $5000$ です。
都市の数 $N$ は最大 $5000$ です。どの $2$ つの相違なる都市の間も双方向に通れるとあります。$N\times(N-1)$ 通りの都市の組があるため、辺の数は最大でおよそ $2500$ 万本になります。
ただし、$N\times{(N-1)}$ 本の辺のうち、$M$ 本の辺が使えないとあります。$M$ は最大で $5000$ しかありません。
ほとんどの道は使える→使えない道だけ引けばいい
この問題は動的計画法で解けます。しかし、$5000$ 回 の 移動のたびに $2500$ 万本の辺すべてを見て遷移をしていては、当然間に合いません。
ここで、ほとんどの道は使うことができて、使えない道は非常に少ないことに着目します。つまり、一旦全ての道を使えるものとして計算したあと、使えない道の分を引けば、高速で解くことができます。
具体的には、以下の操作を$K$ 回繰り返すことで計算量 $O(K(N+M))$ でこの問題を解くことができます。
- 一旦使えない道のことは忘れて、全都市から移動できることにする（そのために、全都市の組み合わせ数の操作を
sum関数で求めておく） - 同じ都市から同じ都市に直接移動はできないので、その分を引く
- 使えない $M$ 個 の 辺それぞれについて、組み合わせ数を引く
実装
$10^9 + 7$ ではなく $998244353$ で割った余りを求めることに気をつけましょう。
コード
Pythonで通すのは大変厳しい（numpyかnumbaを使わないとおそらく無理です）ので、PyPyで提出してください。
MOD = 998244353 # 998244353の余りを答えることに気をつけてください。タイプミスを防ぐために、問題文からコピペしましょう。
def main():
N, M, K = map(int, input().split())
edge = []
for _ in range(M):
u, v = map(int, input().split())
edge.append((u, v))
dp_prev = [0] * (N + 1)
dp_prev[1] = 1
for _ in range(K):
dp_next = [0] * (N + 1)
S = sum(dp_prev) % MOD # 前の日の、全都市の組み合わせ数の合計です
for i in range(1, N + 1):
dp_next[i] = (S - dp_prev[i]) % MOD # i以外の都市からiに向います。都市iから都市iには行けないので引きます
for u, v in edge:
# u -> v と v -> u が封鎖されていて使えないので、その分引きます
dp_next[u] -= dp_prev[v]
dp_next[v] -= dp_prev[u]
dp_next[u] %= MOD
dp_next[v] %= MOD
dp_prev = dp_next
print(dp_prev[1])
if __name__ == '__main__':
main()