📈

ABC - 282

2022/12/17に公開約3,400字

A - Generalized ABC

Python の場合は string.ascii_uppercase を用いると "ABC...XYZ" とタイピングする必要がなくなります。

from string import ascii_uppercase
 
K = int(input())
ans = ascii_uppercase[:K]
print(ans)

実装例 (Python)

https://atcoder.jp/contests/abc282/submissions/37323122

B - Let's Get a Perfect Score

全探索

N から2人を選び出して M 個全部あっているかを全探索する計算量は O(N^2 * M) です。
今回は N, M どちらも小さい値のなので余裕で間に合います。

Python では for を3回書かないといけないところを all を使うことで for を1つ減らすことができます。

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)

https://atcoder.jp/contests/abc282/submissions/37327801

C - String Delimiter

最初 " で囲まれているところを取り出して replace(",", ".") で置換するのかな〜と思っていたのですが、前から順番に " の数を常にカウントしていて , が出てきた時に、奇数であれば括られた文字なのでそのまま、偶数であれば括られた文字ではないので . とみなしてあげればOKです。計算量も O(N) で余裕です。

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)

https://atcoder.jp/contests/abc282/submissions/37334960

D - Make Bipartite 2

用意されているサンプルケースだけでは考えられないパターンが隠れておりそれに気づくのに時間をかなり要しました。まず、問題文を読んで

  • すでに2部グラフである必要がある。そうでなければ 0 を出力する。
  • この時、2部グラフの各グループを黒、白 (それぞれその色で塗っているイメージです) とすると、黒に含まれるノード、白に含まれるノードのすべてのすでに引かれていない辺の数が答え

と考えました。すでに引かれていない辺の数は一見計算するのが大変なようですがすべての組み合わせは (黒色のノードの数) × (白色のノードの数) であり、すでに M 本が引かれていることが自明なため新たに引ける辺の数は (黒色のノードの数) × (白色のノードの数) - M とわかります。

2部グラフの判定には DFS を用いました。隣合うノードを黒、白、黒、...と交互に塗っていった時すでに隣が塗られていてしかも同じ色であった場合、2部グラフとみなせないので False を返すように実装しました。

しかし以上のことを実装したコードで提出しても WA でした(TLE が2個ありましたが PyPy3 ではなく Python で提出したらなくなりました)。何かぬけているな〜と考えたら辺を1つも持たないノードが存在していることがあることに気づきました (以降、シングルトンと呼びます)。

まず軽く悩んだのがシングルトンを含む場合は2部グラフと言えるのかです。定義を見た感じ2部グラフと考えて良さそうでしたが確信が持てなかったので1WAでもいいやとシングルトンを含む場合は 0 を出力するようにしたところ引き続き WA だったので、安心して(?)2部グラフとみなせると判断しました。(モヤモヤしながら実装するぐらいなら1WAで方針を定めようと思いました)

シングルトンを含むときは、連結しているグラフのすべてのノードからシングルトンへ辺を伸ばす事ができるので、追加で (連結しているグラフの数) x (シングルトンの数) 個辺が増えます。さらにシングルトン同士の間でも自由に辺を伸ばす事ができるので (シングルトンの数)C_{2} 個さらに増えます。

これで AC できるだろうと思いきや減ったもののまだ WA が残っていました。ここでかなり頭を悩ませたのですがサンプルケース (ここまででもシングルトンを含むケースなど手元でかなりサンプルケースを増やしていました) としてノード1がシングルトン出る場合を作ってみた場合、2部グラフであるかを判定する DFS が当たり前ですがノード1から先に進まず止まってしまっていました。

本来はノード1をシングルトンとみなして他は連結しているグラフであるとみなさないといけないので明らかにこれはバグです。そこではじめて 複数の連結しているグラフがある パターンがあることに気づきました。

そこでノード1, 2, ..., N と前から2部グラフに含まれているかのチェックとどのグループに含まれているか、そして含まれている場合黒に塗られたのか、白に塗られたのかのチェックを追加でするようにしました。このようにするとシングルトンも1個だけですが連結している2部グラフとみなして考えることができます。

最後に肝心の追加できる辺の数ですが、グループ内、グループ外でそれぞれどうなるかを考えると以下のようになります。

  • グループ内:最初に考えてたとおり (グループ_{i}で黒色のノードの数) × (グループ_{i}で白色のノードの数) - (グループ_{i}ですでに引かれている辺の数) です。すでに引かれている辺の数の計算が大変ですが各グループですでに引かれている辺の数の和は結局 M になるので最後に全体から M 引いてあげればOKです。
  • グループ外:シングルトンの時の考察同様、どのノード同士をつないでもOKなので (グループ_{i}に含まれるノードの数) × (グループ_{i}に含まれないノードの数) です。後者は N - (グループ_{i}に含まれるノードの数) で求めてあげることができます。ACしたコードではダブるようにカウントしているので最後に 2 で割っています。

Python (実装例)

https://atcoder.jp/contests/abc282/submissions/37362592

Discussion

ログインするとコメントできます