If you put out exactly the same move as TopCoDeer, the score will be 0 points, so the maximum score will be 0 points or more. For the time being, I decided to put out exactly the same move as TopCoDeer, and gave the number of pars and goo. If you count the number of times and change from the last goo to par as many times as you meet the conditions, you will get the highest score.
s = input()
print(max((s.count('g') * 2 - len(s)) // 2, 0))
If 1 and 2 can be swapped, and 2 and 3 can be swapped, then 1 and 3 can also be swapped. That is, the same union can be swapped. Union Find tree. I can't prove that you can arrange them as you want within the same union. But I've never heard that there are times when bubble sort isn't possible, so it's probably okay. Intuitively, you should sort them in order from the end. So, for all p i </ sub>, the same Check if there is i in the union, and the sum of the numbers is the answer.
from sys import setrecursionlimit
def find(parent, i):
t = parent[i]
if t < 0:
return i
t = find(parent, t)
parent[i] = t
return t
def unite(parent, i, j):
i = find(parent, i)
j = find(parent, j)
if i == j:
return
parent[j] += parent[i]
parent[i] = j
setrecursionlimit(10 ** 5)
N, M = map(int, input().split())
p = list(map(int, input().split()))
parent = [-1] * N
for _ in range(M):
x, y = map(int, input().split())
unite(parent, x - 1, y - 1)
result = 0
for i in range(N):
if find(parent, i) == find(parent, p[i] - 1):
result += 1
print(result)
If you check if the majority of all substrings are the same character, it will be * O * (* N * 2 </ sup>), so TLE is inevitable. By the way, if the majority are the same character, it is the same. The same character appears with two consecutive characters or one space between them. This can be seen immediately by actually making a character with the same majority. * O * (* N *) can be used to check if this exists. You can check it, so you can solve it.
s = input()
for i in range(len(s) - 1):
if s[i] == s[i + 1]:
print(*[i + 1, i + 2])
exit()
for i in range(len(s) - 2):
if s[i] == s[i + 2]:
print(*[i + 1, i + 3])
exit()
print(*[-1, -1])
If you write it in naive, * O * (* N * 3 </ sup>), even if it is relaxed by the cumulative sum, * O * (* N * 2 </ sup>) and what to do with TLE. ? First, instead of counting "the sum is a multiple of M", count "the sum of the remainders divided by M is 0". Then A 1 </ sub>, A 1 </ sub> + A 2 </ sub>, ..., A 1 </ sub> + A 2 </ sub> ... A N Count the number of </ sub> divided by M. If t m </ sub> is the number of occurrences of the remainder m, the number to be counted when l = 1, r = 1..N Is t 0 </ sub>. Next, l = 2, r = 1..N should be counted, but the number of A 1 </ sub> divided by M is reduced from each. So, I think for a moment that t A 1 </ sub>% M </ sub>, but since l = 1 and r = 1 were only A 1 </ sub>, this Must be omitted, which is t A 1 </ sub>% M </ sub> -1 and this one must be omitted even when calculating after l = 3. Don't. Then loop to l = N for the answer.
N, M = map(int, input().split())
A = list(map(int, input().split()))
t = {}
c = 0
for a in A:
c += a
c %= M
if c in t:
t[c] += 1
else:
t[c] = 1
result = 0
if 0 in t:
result += t[0]
c = 0
for a in A:
c += a
c %= M
t[c] -= 1
result += t[c]
print(result)
Since we are looking for the smallest lexicographical order, we want to insert'(' to the left as much as possible and')' to the right as much as possible. So'(' is on the far left and')' is Suppose that you insert only at the right end. I wonder how many will be inserted after that, but since the length of the character string is at most 100, it will not become TLE even if it is actually transformed. Just add parentheses to the left or right edge until the string is empty.
N = int(input())
S = input()
result = S
while True:
while True:
t = S.replace('()', '')
if t == S:
break
S = t
if S == '':
break
elif S[0] == ')':
S = '(' + S
result = '(' + result
elif S[0] == '(':
S = S + ')'
result = result + ')'
print(result)
The maximum score is to find the shortest path from (1, 1) to (H, W) in a breadth-first search and change all the white cells that did not pass on the shortest path to black. The answer is the number of white cells. --The number of squares on the shortest path.
H, W = map(int, input().split())
s = [input() for _ in range(H)]
dp = [[2501] * W for _ in range(H)]
dp[0][0] = 1
q = [(0, 0)]
while q:
nq = []
while q:
y, x = q.pop()
t = dp[y][x] + 1
if y < H - 1:
if s[y + 1][x] == '.' and dp[y + 1][x] > t:
dp[y + 1][x] = t
nq.append((y + 1, x))
if y > 0:
if s[y - 1][x] == '.' and dp[y - 1][x] > t:
dp[y - 1][x] = t
nq.append((y - 1, x))
if x < W - 1:
if s[y][x + 1] == '.' and dp[y][x + 1] > t:
dp[y][x + 1] = t
nq.append((y, x + 1))
if x > 0:
if s[y][x - 1] == '.' and dp[y][x - 1] > t:
dp[y][x - 1] = t
nq.append((y, x - 1))
q = nq
if dp[H - 1][W - 1] == 2501:
print(-1)
else:
print(sum(s[y].count('.') for y in range(H)) - dp[H - 1][W - 1])
Recommended Posts