AtCoder Beginner Contest 145 Rapport de participation

AtCoder Beginner Contest 145 Rapport de participation

ABC145A - Circle

Percer en 1 minute. Il suffit d'écrire.

r = int(input())

print(r * r)

ABC145B - Echo

Percer en trois minutes et demie. Assurez-vous simplement d'avoir une longueur égale.

from sys import exit

N = int(input())
S = input()

if N % 2 == 1:
    print('No')
    exit()

if S[:N // 2] == S[N // 2:]:
    print('Yes')
else:
    print('No')

ABC145C - Average Length

Il a éclaté en 8 minutes. Je pensais que je devrais faire la moyenne de la distance totale de toutes les combinaisons, et quand je l'ai écrit, l'exemple d'entrée est passé, donc quand je l'ai soumis, AC est sorti, mais quand j'ai lu l'explication, il est juste passé par un coup de chance. ..

from math import sqrt

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

result = 0
for i in range(N):
    for j in range(N):
        if i != j:
            result += sqrt((xy[i][0] - xy[j][0]) * (xy[i][0] - xy[j][0]) + (xy[i][1] - xy[j][1]) * (xy[i][1] - xy[j][1]))
print(result / N)

ABC145D - Knight

Pause en 85 minutes. RE4 WA1 mais à peine une minute et demie avant la fin du courant alternatif. La mémoire déborde lors de la première tentative de DP. Le temps de calcul dépasse lors du passage de la matrice en utilisation cyclique. Si vous regardez la table DP quand elle est petite, vous remarquerez qu'il y a trop peu de carrés avec des valeurs, et il n'y a qu'un seul motif pour chacun des deux mouvements à l'arrivée à X, Y. Résolution des équations simultanées ʻa = (2 * Y --X) / 3, b = (2 * X --Y) / 3`, et la solution à obtenir est a + b </ sub> C min (a ,, b) </ sub> est atteint. Dans la vidéo de commentaire lors de la résolution de ABC132D --Blue and Red Balls, M. Sunuke Dit quelque chose comme "le triangle de Pascal peut être utilisé parce que la valeur est petite cette fois", donc quand j'ai cherché sur Google parce qu'il y avait le théorème de Fermat, une implémentation C ++ est sortie, donc je l'ai portée en Python. Cela ne fonctionnait pas du tout en termes de vitesse, donc quand je l'ai rapporté à Go et que je l'ai soumis, c'était un peu plus tard avec deux RE. À ce stade, j'ai essayé 99999 3 et j'ai remarqué que b était négatif, et s'il était négatif, je l'ai corrigé en sortie 0 et l'ai soumis ... Ensuite, la sortie de débogage est restée et WA orz. AC. Donc, la raison pour laquelle les noms de variables sont complètement différents de l'ordinaire est que je n'ai pas eu le temps de corriger le code du port à ma manière ...

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	M = 1000000007
)

var (
	fac  []int
	ifac []int
)

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func mpow(x int, n int) int {
	ans := 1
	for n != 0 {
		if n&1 == 1 {
			ans = ans * x % M
		}
		x = x * x % M
		n = n >> 1
	}
	return ans
}

func comb(a int, b int) int {
	if a == 0 && b == 0 {
		return 1
	}
	if a < b || a < 0 {
		return 0
	}
	tmp := ifac[a-b] * ifac[b] % M
	return tmp * fac[a] % M
}

func main() {
	X := readInt()
	Y := readInt()

	if (X+Y)%3 != 0 {
		fmt.Println(0)
		return
	}

	fac = make([]int, 666667)
	ifac = make([]int, 666667)

	a := (2*Y - X) / 3
	b := (2*X - Y) / 3

	if a < 0 || b < 0 {
		fmt.Println(0)
		return
	}

	fac[0] = 1
	ifac[0] = 1
	for i := 0; i < 666666; i++ {
		fac[i+1] = fac[i] * (i + 1) % M
		ifac[i+1] = ifac[i] * mpow(i+1, M-2) % M
	}

	fmt.Println(comb(a+b, min(a, b)) % M)
}

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
}

PS: réécrit en Python.

p = 1000000007

X, Y = map(int, input().split())

if (X + Y) % 3 != 0:
    print(0)
    exit()

a = (2 * Y - X) // 3
b = (2 * X - Y) // 3

if a < 0 or b < 0:
    print(0)
    exit()

n = a + b
fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % p


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


print(mcomb(n, a))

ABC145E - All-you-can-eat

Je ne peux même pas commencer. C'est un sac à dos, mais il est possible de ne tenir qu'un seul coup. La combinaison qui suit les règles reste conforme aux règles même si celle qui prend le plus de temps est remplacée par la dernière, mais l'inverse n'est pas toujours le cas. Ce n'est pas le cas, il vaut donc mieux différer le temps qu'il faut pour manger, pour pouvoir manger plus. Par conséquent, vous pouvez trier et DP par ordre du temps qu'il faut pour manger. Personnellement, je pense que c'est plus facile que le problème D.

def main():
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]

    dp = [-1] * (T + 3000)
    dp[0] = 0
    for a, b in sorted(AB):
        for i in range(T - 1, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + a] < dp[i] + b:
                dp[i + a] = dp[i] + b
    print(max(dp))


main()

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 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 164 Rapport de participation
AtCoder Beginner Contest 168 Rapport de participation
Rapport de participation au concours AtCoder Débutant 150
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
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 179
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
Rapport de participation au concours de programmation AtCoder HHKB 2020
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
Concours AtCoder Débutant 181 Remarque
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Rapport de participation au concours d'entraînement de la bibliothèque AtCoder (Python)
Concours AtCoder Débutant 182 Remarque
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique