1. 前書き
AtCoderBeginnerContest(ABC)の参加結果と内容の整理、および外部の解説記事を参考にした上で、自分なりに解法を整理していきます。
使用言語はPythonで行きます。本業ではJavaかRubyonRailsユーザーですが、計算速度の問題であったり、トレンドに乗っておくという意味でも（こちらが大きい）、Pythonに慣れていきたいと思います。
2. コンテスト内容
- コンテスト名
- AtCoder Beginner Contest 282
- 開催日時
- 2022/12/17(土) 21:00 - 22:40
- 実施区分
- リアルタイム参加
3. 結果
| 区分 | 結果 | 所要時間 | 実行時間 |
|---|---|---|---|
| A問題 | AC | 6:00 | 19ms |
| B問題 | AC | 26:14 | 24ms |
| C問題 | AC(1) | 68:15 | 197ms |
| D問題 | 未提出 | - | - |
4. 解説
4-1. A - Generalized ABC
4-1-1. 問題文
整数 K が与えられます。
英大文字を A から昇順に K 個繋げて得られる文字列を答えてください。
制約
- Kは1以上26以下の整数
4-1-2. 入力形式
K
4-1-3. 解説
pythonではasciiコードから文字への変換を、chr関数で実現できます。
英大文字「A」はasciiコードで「65」に対応しているので、asciiコードの65~65+Kまでchr関数得られた文字を接続して出力すれば良いです。
4-1-4. ソースコード
k = int(input())
ans = []
for i in range(k):
ans.append(chr(65+i))
print(*ans, sep="")
4-1-5. python文法の整理
asciiコードから文字列へ変換 chr()
asciiコード⇄文字列の相互変換ができます。
#使用法
chr('文字') -> 対応するasciiコード（数値）
chr(数値) -> 対応する文字
#使用例
chr(65) -> 'A'
char('A') -> 65
4-2. B - Let's Get a Perfect Score
4-2-1. 問題文
1 から N までの番号がついた N 人の参加者が、1 から M までの番号がついた M 問からなるコンテストに参加します。
1 以上 N 以下の整数 i 、1 以上 M 以下の整数 j について、Siの j 番目の文字が o のとき参加者 i は問題 j を解くことが可能で、Sの j 番目の文字が x のとき参加者 i は問題 j を解くことが不可能です。
このコンテストは、二人の参加者でペアを組んで参加します。二人が協力することで M 問全てを解くことが可能であるようなペアの個数を答えてください。
より厳密には、1≤x<y≤N を満たす整数の組 (x,y) であって、 1 以上 M 以下の任意の整数 j について、参加者 x か参加者 y の少なくとも一方は問題 j を解くことが可能であるという条件を満たすものの個数を答えてください。
4-2-2. 入力形式
N M
S1
S2
...
SN
4-2-3. 解説
参加者iが解くことが可能な問題を集合Aiで表現することとします。
入力例1の場合、以下のようになります。
5 5
ooooo -> S1 = (1,2,3,4,5)
oooxx -> S2 = (1,2,3)
xxooo -> S3 = (3,4,5)
oxoxo -> S4 = (1,3,5)
xxxxx -> S5 = ()
参加者iと参加者jが条件を満たす時、集合Aiと集合Ajの和集合が、1~Mの全体集合、すなわち、(1,2,...,M)と一致することと等しいので、これを実装していきます。
参加者全体から2名を取り出す組み合わせについては、itertoolsモジュールのcombinationsメソッドを使うことで簡潔に記述できます。
全参加者の集合Aiを配列に格納し、その配列に対してcombinationsメソッドを適用すると、うまく取り出すことができます。
4-2-4. ソースコード
import itertools
n,m = map(int,input().split())
list = []
for i in range(n):
si = input()
tmp = set()
for j in range(len(si)):
if si[j] == "o":
tmp.add(j+1)
list.append(tmp)
ans = 0
all = set()
for k in range(m):
all.add(k+1)
for v in itertools.combinations(list, 2):
if v[0] | v[1] == all:
ans += 1
print(ans)
4-3. C - String Delimiter
4-3-1. 問題文
英小文字、「,」、「"」 からなる長さ N の文字列 S が与えられます。S に含まれる 「"」 の個数は偶数であることが保証されています。
S に含まれる 「"」 の個数を 2K 個とすると、各 i=1,2,…,K について 2i−1 番目の 「"」 から 2i 番目の 「"」 までの文字のことを 括られた文字 と呼びます。
あなたの仕事は、 S に含まれる 「,」 のうち、括られた文字 でないもの を 「.」 で置き換えて得られる文字列を答えることです。
制約
- N は 1 以上 2×105以下の整数
- S は英小文字、「,」、「"」 からなる長さ N の文字列
- S に含まれる 「"」 の個数は偶数
4-3-2. 入力形式
N
S
4-3-3. 解説
文字列Sの長さは2×105以下なので、文字列Sを1文字ずつ検査しても十分間に合う計算量となります。
括られた文字か否かは、それ以前に出てきた「"」の数の偶奇で決まります。
実装上は、フラグ変数を用意して、「"」が出てくるたびにTrue/Falseを反転させることで判定できます。
4-3-4. ソースコード
n = int(input())
s = input()
flg = False
index = []
for i in range(n):
if s[i] == '"':
if flg == False:
flg = True
else:
flg = False
if s[i] == ',' and flg == False:
index.append(i)
if len(index) == 0:
print(s)
else:
ans = []
ans.append(s[:index[0]])
for j in range(len(index)):
if j < len(index)-1 and len(index) > 2:
ans.append('.' + s[index[j]+1:index[j+1]])
elif index[j] == len(s)-1:
ans.append('.')
else:
ans.append('.' + s[index[j]+1:])
print(*ans, sep="")
4-4. D - Make Bipartite 2
4-4-1. 問題文
N 個の頂点と M 本の辺からなる単純な（すなわち、自己ループも多重辺も含まない）無向グラフ G が与えられます。 i=1,2,…,M について、i 番目の辺は頂点 uiと頂点 viを結びます。
1≤u<v≤N を満たす整数の組 (u,v) であって、下記の 2 つの条件をともに満たすものの個数を出力してください。
- グラフ G において、頂点 u と頂点 v を結ぶ辺は存在しない。
- グラフ G に、頂点 u と頂点 v を結ぶ辺を追加して得られるグラフは、二部グラフである。
二部グラフとは？
無向グラフが二部グラフであるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。
- 同じ色に塗られた頂点どうしを結ぶ辺は存在しない。
制約
- 2 ≤ N≤ 2×105
- 0 ≤ M ≤ min{2×105,N(N−1)/2}
- 1 ≤ ui, vi ≤N
- グラフ G は単純
- 入力はすべて整数
4-4-2. 入力形式
N M
u1 v1
u2 v2
...
uM vM
4-4-3. 解説
理解出来次第追記予定