AtCoder Beginner Contest 167 Rapport de participation

AtCoder Beginner Contest 167 Rapport de participation

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

ABC167A - Registration

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 </ sup>. 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 </ sup> donc vous ne pouvez pas tourner K fois, mais N ≤ 2 x 10 5 </ sup> 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 </ sup>. Un seul endroit est adjacent à M × 1 × (M - 1) N - 2 </ sup> × N-1 </ sub> C 1 </ sub> Si vous le considérez comme n endroits, les couleurs sont adjacentes les unes aux autres. M × (M ―― 1) N -1 --n </ sup> × N-1 </ sub> C n </ sub>. 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')

Recommended Posts

AtCoder Beginner Contest 181 Rapport de participation
AtCoder Beginner Contest 161 Rapport de participation
AtCoder Beginner Contest 151 Rapport de participation
AtCoder Débutant Contest 176 Rapport de participation
AtCoder Beginner Contest 154 Rapport de participation
AtCoder Beginner Contest 166 Rapport de participation
AtCoder Beginner Contest 153 Rapport de participation
AtCoder Beginner Contest 145 Rapport de participation
AtCoder Débutant Contest 184 Rapport de participation
AtCoder Beginner Contest 165 Rapport de participation
Rapport de participation au concours AtCoder Débutant 160
AtCoder Beginner Contest 169 Rapport de participation
AtCoder Beginner Contest 178 Rapport de participation
AtCoder Beginner Contest 163 Rapport de participation
AtCoder Beginner Contest 159 Rapport de participation
AtCoder Beginner Contest 168 Rapport de participation
AtCoder Beginner Contest 158 Rapport de participation
Rapport de participation au concours AtCoder Débutant 180
AtCoder Beginner Contest 156 Rapport de participation
AtCoder Beginner Contest 162 Rapport de participation
AtCoder Débutant Contest 157 Rapport de participation
AtCoder Beginner Contest 167 Rapport de participation
AtCoder Débutant Contest 179 Rapport de participation
Concours AtCoder Débutant 182
AtCoder Beginner Contest 146 Rapport de participation
AtCoder Beginner Contest 152 Rapport de participation
AtCoder Débutant Contest 155 Rapport de participation
AtCoder Beginner Contest 174 Rapport de participation
AtCoder Beginner Contest 171 Rapport de participation
AtCoder Beginner Contest 149 Rapport de participation
AtCoder Beginner Contest 148 Rapport de participation
AtCoder Débutant Contest 170 Rapport de participation
AtCoder Débutant Contest 183 Rapport de participation
Note de participation au concours pour débutants AtCoder # 003
AtCoder Grand Contest 041 Rapport de participation
AtCoder Grand Contest 040 Rapport de participation
Rapport de participation au concours régulier AtCoder 105
AtCoder Regular Contest 104 Rapport de participation
Fiche d'inscription au concours ACL pour débutant
Journal de participation Atcoder Beginner Contest 146
AtCoder Chokudai Contest 005 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
Rapport de participation au concours de programmation AtCoder Acing 2020
Rapport de participation au concours de programmation AtCoder Keyence 2020
Rapport de participation au concours de programmation AtCoder Panasonic 2020
Critique du concours AtCoder Beginner Contest 152
Concours AtCoder Débutant 181 Remarque
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Concours AtCoder Débutant 180 Remarque
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation