It's the first time in the 700s, so I don't like it !!
Break through in 2 minutes. Just write.
S = input()
T = input()
if S == T[:-1]:
print('Yes')
else:
print('No')
ABC167B - Easy Linear Programming
Break through in 3 and a half minutes. sum (([0] * A + [1] * B + [-1] * C) [: K]) K ≤ 2 × 10 I noticed 9 </ sup>. What a waste of time.
A, B, C, K = map(int, input().split())
result = 0
t = min(A, K)
result += t
K -= t
t = min(B, K)
K -= t
t = min(C, K)
result -= t
print(result)
It broke through in 8 and a half minutes. It turned out to be a bit full search with the C problem !?
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
t = list(map(int, input().split()))
C.append(t[0])
A.append(t[1:])
result = -1
for i in range(1 << N):
t = [0] * M
c = 0
for j in range(N):
if (i >> j) & 1 == 0:
continue
c += C[j]
for k in range(M):
t[k] += A[j][k]
if all(x >= X for x in t):
if result == -1:
result = c
else:
result = min(result, c)
print(result)
Break through in 13 minutes. K ≤ 10 18 </ sup> so you can't turn for K times, but N ≤ 2 x 10 5 </ sup> so you can turn N times for. Number of towns Since there are N, it always loops within N times, so you know the length of one loop. Once you know that, you can answer by dividing K by that length and turning it.
N, K = map(int, input().split())
A = [int(a) - 1 for a in input().split()]
if K <= N:
p = 0
for i in range(K):
p = A[p]
print(p + 1)
exit()
p = 0
t = [-1] * N
t[0] = 0
for i in range(1, N):
p = A[p]
if t[p] != -1:
break
t[p] = i
d = i - t[p]
K -= i
K %= d
for i in range(K):
p = A[p]
print(p + 1)
Break through in 25 minutes. TLE1 in Python. No one of the same color is adjacent to each other M × (M -1) N -1 </ sup> Street. Only one place is adjacent to M × 1 × (M ―― 1) N − 2 </ sup> × N-1 </ sub> C 1 </ sub> If you think about it, the way to paint with n adjacent colors M × (M ―― 1) N -1 --n </ sup> × N-1 </ sub> C n </ sub>. After that, just loop and add up. I think it was because I groaned for 5 hours at No.1035 Color Box of yukicoder that I was able to solve it quickly.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
const (
p = 998244353
)
var (
fac []int
)
func mpow(x int, n int) int {
result := 1
for n != 0 {
if n&1 == 1 {
result = result * x % p
}
x = x * x % p
n >>= 1
}
return result
}
func mcomb(n int, k int) int {
if n == 0 && k == 0 {
return 1
}
if n < k || k < 0 {
return 0
}
return (fac[n] * mpow(fac[n-k], p-2) % p) * mpow(fac[k], p-2) % p
}
func main() {
defer flush()
N := readInt()
M := readInt()
K := readInt()
fac = make([]int, N+1)
fac[0] = 1
for i := 0; i < N; i++ {
fac[i+1] = fac[i] * (i + 1) % p
}
result := 0
for i := 0; i < K+1; i++ {
t := M * mcomb(N-1, i)
t %= p
t *= mpow(M-1, N-1-i)
t %= p
result += t
result %= p
}
println(result)
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func printf(f string, args ...interface{}) (int, error) {
return fmt.Fprintf(stdoutWriter, f, args...)
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
Postscript: I also passed it in Python.
N, M, K = map(int, input().split())
result = 0
n = 1
k = 1
for i in range(K + 1):
result += n * pow(k, 998244353 - 2, 998244353) * pow(M - 1, N - 1 - i, 998244353)
result %= 998244353
n *= N - 1 - i
n %= 998244353
k *= i + 1
k %= 998244353
result *= M
result %= 998244353
print(result)
I couldn't break through.
Addendum: I tried to solve it as shown in the explanation video, but it was troublesome to divide the list into positive and negative, so I processed it with the sort key function.
def scan(s):
m = 0
a = 0
for c in s:
if c == '(':
a += 1
elif c == ')':
a -= 1
m = min(m, a)
return m, a
def custom_key(v):
m, a = v
if a >= 0:
return 1, m, a
else:
return -1, a - m, a
N = int(input())
S = [input() for _ in range(N)]
c = 0
for m, a in sorted([scan(s) for s in S], reverse=True, key=custom_key):
if c + m < 0:
c += m
break
c += a
if c == 0:
print('Yes')
else:
print('No')
Recommended Posts