初めに
AtCoderに参加した記録を残します。どのような考察をしながら問題に取り組んだかを記録していますので、必ずしも教育的なコードとは限りません。
始めたばかりの人など、どなたかの助けになれば嬉しいです。
コメントなどいただけると嬉しいです！！
成績
ABC297 3冠。
少し落ち着けばE問題まで解けそうだった...。気持ち的な部分も鍛えていかないとですね。
目次
A - Treasure Chest
B - Trick Taking
C - Dango
D - Find by Query
E - Nearest Black Vertex
A - Treasure Chest
問題ページ
与えられた文字列Sが、'*' が'|'に挟まれているか判定する問題。
コンテスト中の考察
制約はとても小さいので思いつく方法でやれば良いと思います。
私がコンテスト中に思いついて方法は、'|' の数をcntで数えておき、cnt = 1の時に'*' が存在しているかで判定することにしました。このようにすれば先頭から見ていくだけで（めんどくさい処理なく）判定可能です。
コンテスト中のコード
N = int(input())
S = input()
cnt = 0
for s in S:
if s == '|':
cnt += 1
if s == '*' and cnt == 1:
print('in')
exit()
print('out')
改善点
着想面
正規表現で解くこともできたらしいです。
正規表現とは、特定のパターンにマッチする文字列を検索するための決まりのことです。
コード面
reはPythonで正規表現を扱う際のライブラリです。
' \ 'はエスケープ文字と呼ばれ、直後の文字を記号ではなく文字として定義するのに利用します。
' . 'は任意の1文字を定義し、' * 'は直前の文字が0個以上連続することを定義します。すなわち、' . * 'は任意の連続する文字列を定義しています。
これらのことがわかれば、' \ |. * \ * . * \ |' は、*の前後に|があり、その間は任意の文字列で埋められているような文字列を定義していることがわかります。
import re
N, S = input(), input()
print('in' if re.search('\|.*\*.*\|', S) else 'out')
B - Trick Taking
問題ページ
数列Cの条件に合わせて数列Rの最大値を求める問題。
コンテスト中の考察
与えられる数字T が数列Cに存在する場合には
max(R[i]), i in C[i]==T
を、そうでない場合には
max(R[i]), i in C[i]==C[0]
を出力れば良いです。
コンテスト中のコード
最初にTがCの中に含まれるかを判定し、colorにみるべき色を指定します。
Cがcolorと一致する、かつこれまでの最大値よりも大きければansを更新します。
ansは答えのindexであるので、先頭に[0]を追加することによって初期化をおこなっています。
N, T = map(int, input().split())
C = [0]+list(map(int, input().split()))
R = [0]+list(map(int, input().split()))
ans = 0
if T in set(C):
color = T
else:
color = C[1]
for i in range(1, N+1):
if C[i] == color and R[ans] < R[i]:
ans = i
print(ans)
改善点
着想面
特になし。
コード面
特になし。
C - Dango
問題ページ
'o' or '-' で構成される文字列Sで、先頭か末尾が '-' 、それ以外が 'o' であるような最長の部分文字列を探す問題。
コンテスト中の考察
一見少し難しそうに見えますが、実は 'o'の長さが最大の区間を探す貪欲法で判定可能です。なぜ貪欲法で判定可能なのでしょうか？
この問題では文字の種類が二つしかないため、 'o' の区間が複数ある場合、必ず間に'-' が含まれるため、前後に'-' が存在するかどうかなどは気にせずに、 'o'が連続する最大数を求めれば良いのです。区間が一つしかない場合（すべての文字列が'o' or '-'である場合）は、条件を満たすことがないのは明らかです。このケースは最初に全文字を見るなりして判定することが可能です（コードを下記に示しますが、コンテスト中は少し特殊な判定をしてACしました)。
コンテスト中のコード
最大区間の左右の端のindexであるma_lとma_rを文字列の左端(0)と右端(N-1)で初期化します。
その後は'o'の連続部分を数えて、ans、及び答えの区間を更新していきます。
ループを抜けた後にma_lもしくはma_rの値が初期値と異なっていれば、区間が複数あったと言えます。考察での証明から、複数区間ある場合は最大区間幅をそのまま出力すればよく、単一区間の場合は-1を出力すれば良いです。
N = int(input())
S = input()
ans = 0
ma_l = 0
ma_r = N-1
cnt = 0
for i in range(N):
if S[i] == 'o':
if cnt == 0:
l = i
cnt += 1
else:
if ans < cnt:
ans = cnt
ma_l = l
ma_r = i-1
cnt = 0
if ans < cnt:
ans = cnt
ma_l = l
ma_r = i
if ma_l != 0 or ma_r != N-1:
print(ans)
exit()
print(-1)
改善点
着想面
'-'でsplitするとかなり短く回答可能なようです。
凄いですね、これ。
コード面
- 最大の区間を求める
- 単一区間文字列の判定
この二つを見事に1行に収めています。
N, S = input(), input()
print(max(map(len, S.split('-'))) if 'o' in S and '-' in S else -1)
D - Find by Query
問題ページ
長さNの0, 1 からなる数列Aに対して、i番目の数字を20回聞くことでA[i] != A[i+1] となるような i を求める問題。
コンテスト中の考察
順序関係が重要だから二分探索とかするためにsortしちゃうこともできないし、これどうやって解くんだ？？？
改善点
着想面
先頭0、末尾が1で固定されているのを見逃していた...。先頭と末尾が0, 1で固定されているのであれば二分探索法によって高速に解を求めることができます。
二分探索法はデータの中心の値を見ることで探索空間を半分にし続けていく手法です。なぜ両端が0と１に固定されるという仮定によって二分探索が可能になるのでしょうか？
それは、問題の構造が線形分離可能になるからです。仮に中心点のデータが '0' であったとします。すると、左端から半分までの数列の中で01のflipが起きるかは不明ですが、半分から右端の数列では必ずどこかで01のflipが起きることがわかります。このように中心のデータを見ることで解空間を半分ずつに減らしていくことができそうです。
E - Nearest Black Vertex
問題ページ
K個の任意の頂点p_iから距離がちょうどd_iのところで初めて黒が存在するように色を塗る方法があるか判定し、ある場合にはその構成を出力する問題。
コンテスト中の考察
p_i からDFSしていって、cost < d の場合にはmust_white , cost == d の場合にはcan_black に保存していって、各can_black 集合から最低1つは黒になってればいいのかなとか思って色々やってみたけど条件めちゃくちゃになってよくわからなくなっちゃった...。
コンテスト中のコード
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
u, v = map(int, input().split())
G[u].append(v)
G[v].append(u)
K = int(input())
white = set()
black = [set() for _ in range(K)]
for i in range(K):
p, d = map(int, input().split())
q = deque([(p, 0)])
visited = set()
while q:
v, cost = q.popleft()
if v in visited:
continue
if 0 < cost < d:
white.add(v)
elif cost == d:
black[i].add(v)
elif cost > d:
break
visited.add(v)
for u in G[v]:
q.append((u, cost+1))
ans_black = set()
for i in range(K):
if black[i] - white:
ans_black.add(black[i].pop())
else:
print('No')
exit()
print('Yes')
for i in range(N):
if i in white:
print(0, end='')
elif i in black:
print(1, end='')
else:
print(1, end='')
print()
改善点
着想面
着想はおおむねあっていました。
各p_i （1<=i<=K） からのcostがちょうどdの時に初めて黒色が出てくるような構成にしなければならないので、逆に言えば、costがd未満の点は必ず白でなければならないという点はコンテスト中の考察通りです。またcostがちょうどdのような頂点候補集合can_blackは複数要素を持つ可能性は十分ありますが、p_iごとに最低一つの要素が黒色に塗られていれば良いのです。これは、各can_blackから、必ず白でなかればいけない集合whiteの差集合によって判定可能です。すべてのca_blackとの差集合が空集合でなければ、白で塗らなければならない頂点以外で条件を満たすことができるということになります。
また、今回の問題ではd以未満は白で塗らなければならないのですが、その他の頂点については特に制限がないので
1つ以上の頂点が黒で塗られていること
にもあるように、特に個数制限のない白よりも黒で塗ったほうが良さそうです。
コンテスコ中のコードで決定的なミスは、if文の中身を
0 < d < cost
にしてしまったことです。明らかにおかしいのですが、デバッグしているうちに変なものをつけたしてしまったのでしょう...。
コード面
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
u, v = map(int, input().split())
G[u].append(v)
G[v].append(u)
K = int(input())
white = set()
black = [set() for _ in range(K)]
for i in range(K):
p, d = map(int, input().split())
q = deque([(p, 0)])
visited = set()
while q:
v, cost = q.popleft()
if v in visited:
continue
if cost == d:
black[i].add(v)
elif cost < d:
white.add(v)
elif cost > d:
break
visited.add(v)
for u in G[v]:
q.append((u, cost+1))
# print(f"{white=}")
for i in range(K):
# print(f"black - white: {black[i]-white}")
if black[i] - white:
pass
else:
print('No')
exit()
print('Yes')
# can_white = {i for i in range(1, N+1)} - ans_black
for i in range(1, N+1):
# if i in can_white:
# print(0, end='')
if i in white:
print(0, end='')
else:
print(1, end='')
print()
参考資料
終わりに
書き始めたばかりで拙い部分も多いですが、みなさんと楽しく盛り上がれたらいいなと思っていますので、今後ともよろしくお願いいたします！
いいね等していただけるととても励みになります！