Break through in 1 minute. Just write.
r = int(input())
print(r * r)
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')
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)
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))
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