[PYTHON] AtCoder Beginner Contest 160 Teilnahmebericht

AtCoder Beginner Contest 160 Teilnahmebericht

ABC160A - Coffee

Brechen Sie in anderthalb Minuten durch. Schreiben Sie einfach.

S = input()

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

ABC160B - Golden Coins

Brechen Sie in zweieinhalb Minuten durch. 500 Yen sind besser für Cospa, also sind 500 Yen so viel wie möglich und der Rest ist 5 Yen.

X = int(input())

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

ABC160C - Traveling Salesman around Lake

Brechen Sie in 7 Minuten durch. Die Richter sind verstopft und der Codetest war schwierig durchzuführen. Wenn Sie alle N Häuser umrunden, müssen Sie nicht nur zwischen dem Startpunkt und dem Endpunkt der Bewegung laufen, das ist also das Maximum Suchen Sie einfach nach dem Ort.

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++

Ich ging zu E, ohne es zu lösen, aber hätte ich es lösen sollen?

Nachtrag: Natürlich hätte ich das lösen sollen. Es war sehr einfach. Ich habe es getan. Ich muss etwas gegen die Schwäche des Graphen tun. Der kleinere ist der kürzeste Abstand, wenn ich direkt gehe und mich von X nach Y verziehe Einfach anzeigen.

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

Verloren. Ich dachte, ich sollte es sortieren, addieren und zerschlagen, aber ich konnte 5 WAs nicht löschen.

Nachtrag: Es war ein Off-by-One-Fehler. Ok: = max (0, Y- (C- (X-i))) ―― Das -1 von 1 fehlte orz.

Selbst wenn Sie in absteigender Reihenfolge sortieren und die kumulative Summe addieren, ist TLE unvermeidlich, da der Rechenaufwand 10 ^{10 </ sup> beträgt, wenn Sie X und Y verdoppeln. Daher wird die Anzahl der roten Apfeläpfel wiederholt. , Die Anzahl der verzehrten grünen Äpfel wird durch eine Zweiteilung bestimmt. Wenn Sie die Anzahl der verzehrten grünen Äpfel in einer Schleife angeben, sollte der Gesamtgeschmack monoton zunehmen und dann von irgendwo aus monoton abnehmen. Suchen Sie nach Punkten nach Dichotomie. In diesem Fall gibt es kein Problem, da der Berechnungsaufwand etwa 1,7 * 10 <6> </ sup> beträgt.}

Nun, wie Sie im Kommentar-PDF sehen können, können Sie es lösen, ohne solche nervigen Dinge zu tun, aber als Aufzeichnung, dass Sie es so lösen könnten.

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
}