AtCoder Beginner Contest 167 参戦記
700番台とか初めてなのでイヤッッホォォォオオォオウ!!
ABC167A - Registration
2分で突破. 書くだけ.
S = input()
T = input()
if S == T[:-1]:
print('Yes')
else:
print('No')
ABC167B - Easy Linear Programming
3分半で突破. sum(([0] * A + [1] * B + [-1] * C)[:K]) って書いている途中で K≤2×109 に気づいた. なんという時間の無駄.
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)
ABC167C - Skill Up
8分半で突破. C問題でビット全探索!?ってなった. やっぱりC問題にしては難しいせいか、半分くらい虐殺されていますね(順位表を見て).
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)
ABC167D - Teleporter
13分で突破. K≤1018 なので K 回 for を回すことはできないけど、N≤2×105 なので N 回 for を回せる. 町の数は N 個なので、N 回以内に必ずループするので、1ループの長さがわかる. それさえ分かれば K をその長さで割った余りだけ回せば答えになる.
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)
ABC167E - Colorful Blocks
25分で突破. Python で TLE1. 一つも同じ色が隣り合わない塗り方は M×(M - 1)N - 1 通り. 一箇所だけ隣り合う塗り方は M×1×(M - 1)N - 2×N-1C1 と考えていくと n 箇所色が隣り合う塗り方は M×(M - 1)N - 1 - n×N-1Cn となる. 後はループして積算するだけ. スパッと解けたのは yukicoder の No.1035 Color Box で5時間唸ったおかげだと思う.
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...)
}
追記: 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)
ABC167F - Bracket Sequencing
突破できず.
追記: 概ね解説動画の通り解いてみましたが、正と負でリストを分けるのが面倒だったので、ソートのキー関数で処理してしまいました.
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')