[PYTHON] AtCoder Beginner Contest 160 Participation Report

AtCoder Beginner Contest 160 Participation Report

ABC160A - Coffee

Break through in one and a half minutes. Just write.

S = input()

if S[2] == S[3] and S[4] == S[5]:
    print('Yes')
else:
    print('No')

ABC160B - Golden Coins

Break through in two and a half minutes. 500 yen is better for cospa, so 500 yen is as much as possible, and the remainder is 5 yen.

X = int(input())

result = (X // 500) * 1000
X -= (X // 500) * 500
result += (X // 5) * 5
print(result)

ABC160C - Traveling Salesman around Lake

Break through in 7 minutes. Judges are clogged and the code test has been difficult to execute. Going around all N houses means that you do not have to walk only between the start point and the end point of the move, so that is the maximum Just look for the place.

K, N = map(int, input().split())
A = list(map(int, input().split()))

result = A[0] - A[N - 1] + K
for i in range(N - 1):
    result = max(result, A[i + 1] - A[i])
print(K - result)

ABC160D - Line++

I went to E without solving it, but should I have solved it?

Addendum: Obviously I should have solved this. It was very easy. I did it. I have to do something about my weakness in the graph. The smaller one is the shortest distance when going directly and when warping from X to Y, so aggregate Just display.

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

t = [0] * (N - 1)
for i in range(1, N):
    for j in range(i + 1, N + 1):
        t[min(j - i, abs(X - i) + 1 + abs(Y - j)) - 1] += 1
print('\n'.join(map(str, t)))

ABC160E - Red and Green Apples

Lost. I thought I should sort it, add it up, and smash it, but I couldn't erase 5 WAs.

Addendum: Off-by-one error. ʻOk: = max (0, Y- (C- (X-i))) --1 -1` was missing orz.

Even if you sort in descending order and add up the cumulative sum, TLE is inevitable because the amount of calculation is 10 ^{10 </ sup> if you do a double loop of X and Y. , The number of green apples eaten will be determined by a binary search. If you loop the number of green apples eaten, the total taste should increase monotonically and then decrease monotonically from somewhere. Search for points by binary search. In this case, there is no problem because the amount of calculation is about 1.7 * 10 6 </ sup>.}

Well, as you can see in the commentary PDF, you can solve it without doing such annoying things, but as a record that you could solve it like this.

package main

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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	X := readInt()
	Y := readInt()
	A := readInt()
	B := readInt()
	C := readInt()

	p := make([]int, A+1)
	q := make([]int, B+1)
	r := make([]int, C+1)

	for i := 0; i < A; i++ {
		p[i+1] = readInt()
	}
	for i := 0; i < B; i++ {
		q[i+1] = readInt()
	}
	for i := 0; i < C; i++ {
		r[i+1] = readInt()
	}

	sort.Sort(sort.Reverse(sort.IntSlice(p[1:])))
	sort.Sort(sort.Reverse(sort.IntSlice(q[1:])))
	sort.Sort(sort.Reverse(sort.IntSlice(r[1:])))

	for i := 1; i < A; i++ {
		p[i+1] += p[i]
	}
	for i := 1; i < B; i++ {
		q[i+1] += q[i]
	}
	for i := 1; i < C; i++ {
		r[i+1] += r[i]
	}

	result := 0
	for i := max(0, X-C); i <= X; i++ {
		ok := max(0, Y-(C-(X-i))) - 1
		ng := Y
		for ng-ok != 1 {
			m := ok + (ng-ok)/2
			t0 := q[m] + r[(X-i)+(Y-m)]
			t1 := q[m+1] + r[(X-i)+(Y-(m+1))]
			if t0 < t1 {
				ok = m
			} else {
				ng = m
			}
		}
		j := ok + 1
		result = max(result, p[i]+q[j]+r[(X-i)+(Y-j)])
	}

	fmt.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
}