ABC - 282
A - Generalized ABC
Python の場合は string.ascii_uppercase を用いると "ABC...XYZ" とタイピングする必要がなくなります。
from string import ascii_uppercase
K = int(input())
ans = ascii_uppercase[:K]
print(ans)
実装例 (Python)
B - Let's Get a Perfect Score
全探索
N から２人を選び出して M 個全部あっているかを全探索する計算量は
今回は
Python では for を３回書かないといけないところを all を使うことで for を１つ減らすことができます。
ans = 0
for i in range(N):
for j in range(i + 1, N):
si = S[i]
sj = S[j]
if all(si[k] == "o" or sj[k] == "o" for k in range(M)):
ans += 1
実装例 (Python)
C - String Delimiter
最初 " で囲まれているところを取り出して replace(",", ".") で置換するのかな〜と思っていたのですが、前から順番に " の数を常にカウントしていて , が出てきた時に、奇数であれば括られた文字なのでそのまま、偶数であれば括られた文字ではないので . とみなしてあげればOKです。計算量も
cnt = 0
T = []
for i in range(N):
if S[i] == ",":
if cnt % 2 == 1:
T.append(",")
else:
T.append(".")
else:
T.append(S[i])
if S[i] == '"':
cnt += 1
公式解説ではそもそも変更される箇所は "." なので文字列のリストで持って変更される箇所だけ置き換えるように実装していてそちらのほうがよりわかりやすいと思いました。
実装例 (Python)
D - Make Bipartite 2
用意されているサンプルケースだけでは考えられないパターンが隠れておりそれに気づくのに時間をかなり要しました。まず、問題文を読んで
- すでに２部グラフである必要がある。そうでなければ
0を出力する。 - この時、２部グラフの各グループを黒、白 (それぞれその色で塗っているイメージです) とすると、黒に含まれるノード、白に含まれるノードのすべてのすでに引かれていない辺の数が答え
と考えました。すでに引かれていない辺の数は一見計算するのが大変なようですがすべての組み合わせは
２部グラフの判定には DFS を用いました。隣合うノードを黒、白、黒、...と交互に塗っていった時すでに隣が塗られていてしかも同じ色であった場合、２部グラフとみなせないので False を返すように実装しました。
しかし以上のことを実装したコードで提出しても WA でした(TLE が２個ありましたが PyPy3 ではなく Python で提出したらなくなりました)。何かぬけているな〜と考えたら辺を１つも持たないノードが存在していることがあることに気づきました (以降、シングルトンと呼びます)。
まず軽く悩んだのがシングルトンを含む場合は２部グラフと言えるのかです。定義を見た感じ２部グラフと考えて良さそうでしたが確信が持てなかったので１WAでもいいやとシングルトンを含む場合は 0 を出力するようにしたところ引き続き WA だったので、安心して(?)２部グラフとみなせると判断しました。(モヤモヤしながら実装するぐらいなら１WAで方針を定めようと思いました)
シングルトンを含むときは、連結しているグラフのすべてのノードからシングルトンへ辺を伸ばす事ができるので、追加で
これで AC できるだろうと思いきや減ったもののまだ WA が残っていました。ここでかなり頭を悩ませたのですがサンプルケース (ここまででもシングルトンを含むケースなど手元でかなりサンプルケースを増やしていました) としてノード１がシングルトン出る場合を作ってみた場合、２部グラフであるかを判定する DFS が当たり前ですがノード１から先に進まず止まってしまっていました。
本来はノード１をシングルトンとみなして他は連結しているグラフであるとみなさないといけないので明らかにこれはバグです。そこではじめて 複数の連結しているグラフがある パターンがあることに気づきました。
そこでノード１, 2, ..., N と前から２部グラフに含まれているかのチェックとどのグループに含まれているか、そして含まれている場合黒に塗られたのか、白に塗られたのかのチェックを追加でするようにしました。このようにするとシングルトンも１個だけですが連結している２部グラフとみなして考えることができます。
最後に肝心の追加できる辺の数ですが、グループ内、グループ外でそれぞれどうなるかを考えると以下のようになります。
- グループ内：最初に考えてたとおり
(グループ_{i}で黒色のノードの数) × (グループ_{i}で白色のノードの数) - (グループ_{i}ですでに引かれている辺の数) M M - グループ外：シングルトンの時の考察同様、どのノード同士をつないでもOKなので
(グループ_{i}に含まれるノードの数) × (グループ_{i}に含まれないノードの数) N - (グループ_{i}に含まれるノードの数)
Python (実装例)
Discussion