[PYTHON] AtCoder Beginner Contest 145 Participation Report

AtCoder Beginner Contest 145 Participation Report

ABC145A - Circle

Break through in 1 minute. Just write.

r = int(input())

print(r * r)

ABC145B - Echo

Break through in three and a half minutes. Just make sure you have an even length.

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

It broke through in 8 minutes. I thought that I should average the total distance of all combinations, and when I wrote it, the input example passed, so when I submitted it, AC came out, but when I read the explanation, it just passed by a fluke. ..

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

Break through in 85 minutes. RE4 WA1 but barely one and a half minutes before the end AC. Memory overflows when trying to DP for the first time. Calculation time overflows when changing the array to circular use. In consideration mode, this is a bad policy. X, Y If you look at the DP table when is small, you will notice that there are too few squares with values, and there is only one pattern for each of the two movements on arrival at X, Y. Solving the simultaneous equations ʻa = (2 * Y --X) / 3, b = (2 * X --Y) / 3`, and the solution to be obtained is a + b </ sub> C min (a,, b) </ sub> is reached. In the commentary video when solving ABC132D --Blue and Red Balls, Mr. Sunuke Said something like "This time the value is small, so you can use Pascal's triangle", so when I googled because there was Fermat's theorem, a C ++ implementation came out, so I ported it to Python. It was completely useless in terms of speed, so when I re-ported it to Go and submitted it, it was a little later with 2 REs. I thought that the index was out of the way, made the slice larger and submitted it 2 more REs and became calm. At that point, I tried 99999 3 and noticed that b was negative, and if it was negative, I corrected it to output 0 and submitted it ... Then, the debug output remained and WA orz. Erase it and output it again. AC. So, the reason why the variable names are completely different from usual is that I didn't have time to fix the port code in my own way ...

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
}

Postscript: Rewritten in 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

I can't even start. It's a knapsack, but it's possible to stick out only one shot. The combination that adheres to the rule remains as per the rule even if the one that takes the longest time is replaced with the last one, but the reverse is not always Since it is not so, you can eat more if you put off the time it takes to eat later. Therefore, you can sort and DP in order of the time it takes to eat. Personally, I feel that it is easier than the D problem.

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 Participation Report
AtCoder Beginner Contest 161 Participation Report
AtCoder Beginner Contest 151 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Beginner Contest 153 Participation Report
AtCoder Beginner Contest 145 Participation Report
AtCoder Beginner Contest 184 Participation Report
AtCoder Beginner Contest 165 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Beginner Contest 168 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 158 Participation Report
AtCoder Beginner Contest 180 Participation Report
AtCoder Beginner Contest 156 Participation Report
AtCoder Beginner Contest 162 Participation Report
AtCoder Beginner Contest 157 Participation Report
AtCoder Beginner Contest 167 Participation Report
AtCoder Beginner Contest 179 Participation Report
AtCoder Beginner Contest 182 Participation Report
AtCoder Beginner Contest 146 Participation Report
AtCoder Beginner Contest 152 Participation Report
AtCoder Beginner Contest 155 Participation Report
AtCoder Beginner Contest 174 Participation Report
AtCoder Beginner Contest 171 Participation Report
AtCoder Beginner Contest 149 Participation Report
AtCoder Beginner Contest 148 Participation Report
AtCoder Beginner Contest 188 Participation Report
AtCoder Beginner Contest 170 Participation Report
AtCoder Beginner Contest 187 Participation Report
AtCoder Beginner Contest 183 Participation Report
AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 040 Participation Report
AtCoder Regular Contest 105 Participation Report
AtCoder Regular Contest 104 Participation Report
ACL Beginner Contest Participation Report
Atcoder Beginner Contest 146 Participation Diary
AtCoder Chokudai Contest 005 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Beginner Contest 179
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder HHKB Programming Contest 2020 Participation Report
AtCoder Acing Programming Contest 2020 Participation Report
AtCoder Keyence Programming Contest 2020 Participation Report
AtCoder Panasonic Programming Contest 2020 Participation Report
AtCoder Beginner Contest 181 Note
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Library Practice Contest Participation Report (Python)
AtCoder Beginner Contest 182 Note
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review