デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239) 参戦記

ABC239A - Horizon

2分で突破. 書くだけ.

from math import sqrt

H = int(input())

print(sqrt(H * (12800000 + H)))

ABC239B - Integer Division

4分半で突破. 試したら Python の除算そのままであれってなった.

X = int(input())

print(X // 10)

ABC239C - Knight Fork

9分で突破. 2点の周辺を全探索すればいいかなと思い、素直にそれをすると TLE するので、2点が近い場合という条件を足した.

x1, y1, x2, y2 = map(int, input().split())

def dist(x1, x2, y1, y2):
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)

if dist(x1, x2, y1, y2) <= 100:
    l = min(x1, x2) - 5
    r = max(x1, x2) + 5
    t = min(y1, y2) - 5
    d = max(y1, y2) + 5
    for y in range(t, d + 1):
        for x in range(l, r + 1):
            if dist(x, x1, y, y1) == 5 and dist(x, x2, y, y2) == 5:
                print('Yes')
                exit()
print('No')

追記: よくよく考えるとある点から距離がルート5の格子点はたかだか8つしか無いので、それらを全部チェックすればいいだけだった.

x1, y1, x2, y2 = map(int, input().split())

for dx, dy in [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]:
    x3, y3 = x1 + dx, y1 + dy
    if (x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2) == 5:
        print('Yes')
        exit()
print('No')

ABC239D - Prime Sum Game

5分半で突破. 全探索しても100×100=10⁴でしかないので、全探索すれば良い. 簡単すぎん?

A, B, C, D = map(int, input().split())

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]

for x in range(A, B + 1):
    for y in range(C, D + 1):
        if x + y in primes:
            break
    else:
        print('Takahashi')
        exit()
print('Aoki')

ABC239E - Subtree K-th Max

86分で突破、TLE1、WA1. 1≤K_i​≤20 と K_i​ の値域が狭いので、全ての K_i について先に計算すれば OK かなと思ったけど、意外と制限時間ギリギリだった.

package main

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

var (
	X     []int
	links [][]int
	lut   [21]map[int]int
)

func f(k int, i int, p int) []int {
	t := make([]int, 0, 20)
	t = append(t, X[i])
	for _, x := range links[i] {
		if x == p {
			continue
		}
		t = append(t, f(k, x, i)...)
	}
	sort.Sort(sort.Reverse(sort.IntSlice(t)))
	if len(t) >= k {
		lut[k][i] = t[k-1]
	}
	return t[:k]
}

func main() {
	defer flush()

	N := readInt()
	Q := readInt()
	X = make([]int, N)
	for i := 0; i < N; i++ {
		X[i] = readInt()
	}

	links = make([][]int, N)

	for i := 0; i < N-1; i++ {
		A := readInt() - 1
		B := readInt() - 1
		links[A] = append(links[A], B)
		links[B] = append(links[B], A)
	}

	for i := 0; i < Q; i++ {
		V := readInt() - 1
		K := readInt()
		if lut[K] == nil {
			lut[K] = make(map[int]int)
			f(K, 0, -1)
		}
		println(lut[K][V])
	}
}

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 println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}

追記: K_i​ の値域が狭いといっても、1回でできることを20回する必要なかったね…….

from sys import setrecursionlimit, stdin

readline = stdin.readline
setrecursionlimit(10 ** 6)

N, Q = map(int, readline().split())
X = list(map(int, readline().split()))

links = [[] for _ in range(N)]

for _ in range(N - 1):
    A, B = map(int, readline().split())
    A, B = A - 1, B - 1
    links[A].append(B)
    links[B].append(A)

t = [None for _ in range(N)]

def f(i, p):
    a = [X[i]]
    for j in links[i]:
        if j == p:
            continue
        a.extend(f(j, i))
    a.sort(reverse=True)
    if len(a) > 20:
        a = a[:20]
    t[i] = a
    return a
f(0, -1)

result = []
for _ in range(Q):
    V, K = map(int, readline().split())
    V, K = V - 1, K - 1
    result.append(t[V][K])
print(*result, sep='\n')