AtCoder Beginner Contest 167 Rapport de participation

C'est la première fois dans les années 700, donc je n'aime pas ça !!

Percer en 2 minutes. Il suffit d'écrire.

S = input()
T = input()

if S == T[:-1]:
    print('Yes')
else:
    print('No')

ABC167B - Easy Linear Programming

Percer en 3 minutes et demie. Sum (([0] * A + [1] * B + [-1] * C) [: K]) K ≤ 2 × 10 ^{J'ai remarqué 9 . Quelle perte de temps.}

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

Il a percé en 8 minutes et demie. Il s'est avéré être une recherche un peu complète avec le problème 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

Percer en 13 minutes. K ≤ 10 ^{18 donc vous ne pouvez pas tourner K fois, mais N ≤ 2 x 10 ^{5 donc vous pouvez tourner N fois pour. Nombre de villes Puisqu'il y a N pièces, il boucle toujours en N fois, vous pouvez donc connaître la longueur d'une boucle. Une fois que vous savez cela, vous pouvez répondre en divisant K par cette longueur et en la tournant.}}

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

Pénétrez dans 25 minutes. TLE1 en Python. Personne de la même couleur n'est adjacent à une autre rue M × (M -1) ^{N -1 . Un seul endroit est adjacent à M × 1 × (M - 1) ^{N - 2 × _{N-1 C _{1 Si vous le considérez comme n endroits, les couleurs sont adjacentes les unes aux autres. M × (M ―― 1) ^{N -1 --n × _{N-1 C _{n . Après cela, bouclez simplement et additionnez. Je pense que c'est parce que j'ai gémi pendant 5 heures à No.1035 Color Box de yukicoder que j'ai pu le résoudre rapidement.}}}}}}}

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: je l'ai également passé en 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

Je n'ai pas pu percer.

Addendum: J'ai essayé de le résoudre comme indiqué dans la vidéo d'explication, mais il était difficile de diviser la liste en positif et en négatif, donc je l'ai traitée avec la fonction de clé de tri.

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')