コンテスト
A問題
感想
左から順に見て、A,B,Cが全て出現したら終わり
コンテスト中提出コード
import sys
import itertools
import math
import collections
import bisect
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18
def main():
N = int(input())
S = input().strip()
a = False
b = False
c = False
for i,si in enumerate(S):
if si == "A":
a = True
elif si == "B":
b = True
else:
c = True
if a is True and b is True and c is True:
print(i+1)
exit()
main()
B問題
感想
1日目から順に見ていく。
全ての人がoならカウンタを+1,そうでないならカウンタを0にする。
カウンタの最大値を出力する。
コンテスト中提出コード
import sys
import itertools
import math
import collections
import bisect
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18
def main():
N,D = list(map(int, input().split()))
S = [list(input().strip()) for _ in range(N)]
ans = 0
cnt = 0
for i in range(D):
t = True
for j in range(N):
if S[j][i] == 'x':
t = False
if t is True:
cnt +=1
else:
cnt = 0
ans = max(ans,cnt)
print(ans)
main()
C問題
感想
グラフの問題なので、DFSを使って全探索かと思ったが、いつものグラフの形式とは違っていた。
普通DFSでは、ある頂点から行ける頂点をtodoに追加する、といった方法で行う。
今回のグラフは、ある頂点から行ける頂点は1種類と決まっている。
なので、追加する頂点は1つのみで、ある頂点から辺が出てないということはない。
つまり、単純に次に探索する頂点はAの配列のみで決まっている。
したがって、わざわざtodo配列を用意する必要はない。
それ以外は普通のDFSと変わらず探索できる。
閉路が一つ求まればいいのでどこからスタートしてもいいが、0からスタートすることにする。
一度訪れた頂点を記録しておいて、同じ頂点に再び辿り着いた時、そこを閉路の始まりとする。
閉路の始まりから、もう一度そこに辿り着くまでの頂点の番号を出力する。
コンテスト中提出コード
import sys
import itertools
import math
import collections
import bisect
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18
def main():
N = int(input())
A = list(map(lambda x: int(x)-1, input().split()))
done = [False] * N
cur = 0
st = None
while True:
if done[cur] is True:
st = cur
break
done[cur] = True
cur = A[cur]
cur = st
ans = []
while True:
ans.append(cur+1)
cur = A[cur]
if cur == st:
break
print(len(ans))
print(*ans)
main()
D問題
感想
DFSを応用して解けると思った。
少し工夫が必要で、岩にぶつかって止まった場所を覚えておき、一度止まった場所からは再び探索しないようにする。
こうすることで、基本的にはグリッドのDFSで解ける。
止まった場所からは、上下左右に探索する。
この方法では、一度来た方向に戻る探索も行ってしまうので、TLEするかもな〜と思いながらも、提出するとACできなかった。
計算量が見積もれなかったが、解説によると3乗らしい。
止まる可能性のあるマスが全部でNM、止まった場所から岩にぶつかるまでの探索で最大4*Nなので、$O(MN^2)$になる。と思う。
今回はN,Mの最大値は200なので、$610^6$なので間に合う。
コンテスト中提出コード
import sys
import itertools
import math
import collections
import bisect
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18
def main():
N,M = list(map(int, input().split()))
S = [list(input().strip()) for _ in range(N)]
t = [[False]*M for _ in range(N)]
todo = []
todo.append((1,1))
done = set()
while todo:
cur = todo.pop()
if cur in done:
continue
done.add(cur)
t[cur[0]][cur[1]] = True
for i,j in [[0,1],[1,0],[-1,0],[0,-1]]:
cur_i = cur[0]
cur_j = cur[1]
while S[cur_i+i][cur_j+j] != "#":
cur_i += i
cur_j += j
t[cur_i][cur_j] = True
if (cur_i,cur_j) not in done:
todo.append((cur_i,cur_j))
cnt = 0
for i in range(0,N):
for j in range(0,M):
if t[i][j] == True:
cnt +=1
print(cnt)
main()
E問題
感想
ACできなかった。
戦略としては、左上隅を全探索する。
左上隅が決まったとき、穴のない正方形で最大のサイズは、右と下に二分探索すると見つかる。
サイズnの正方形の中に入る正方形は$n*(n+1)(2n+1)//6$でもとまる。
一度求めたところからは探索する必要はないため、そこからは探索しない。
探索しない場所をチェックするやり方がわからなかった。
ワンちゃんにかけて、$i$から$i+n-1$と$j$から$j+n-1$までを二重ループで塗りつぶすことにしてみたがTLEだった。
公式解説を見てみると、dpらしい。
dpなんて1ミリも考えつかなかった。
コメント