[PYTHON] Yukicoder-Wettbewerb 254 Teilnehmerrekord

Yukicoder-Wettbewerb 254 Teilnehmerrekord

A 1095 Smallest Kadomatsu Subsequence

Wenn Sie es naiv schreiben, ist es * O * (* N * 2 </ sup>). Zuerst dachte ich, es sei ein Seg-Baum, aber ich hatte nicht das Gefühl, nach dem Mindestwert über dem angegebenen Wert suchen zu können. Daher wurde es zu einem ausgeglichenen Dichotomiebaum. Während der Suchbaum für die Gleichgewichtshalbierung auf der linken und rechten Seite des zentralen Kadomatsu beibehalten wird, finden Sie den Mindestwert für konvex und den Mindestwert größer als die mittlere Größe für konkav. Sie müssen lediglich die Mindestgröße der Kadomatsu-Zeile ermitteln. * O * ( N </ i> log N </ i>).

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

var (
	y uint = 88172645463325252
)

func xorshift() uint {
	y ^= y << 7
	y ^= y >> 9
	return y
}

type treapNode struct {
	value    int
	priority uint
	count    int
	left     *treapNode
	right    *treapNode
}

func newTreapNode(v int) *treapNode {
	return &treapNode{v, xorshift(), 1, nil, nil}
}

func treapRotateRight(n *treapNode) *treapNode {
	l := n.left
	n.left = l.right
	l.right = n
	return l
}

func treapRotateLeft(n *treapNode) *treapNode {
	r := n.right
	n.right = r.left
	r.left = n
	return r
}

func treapInsert(n *treapNode, v int) *treapNode {
	if n == nil {
		return newTreapNode(v)
	}
	if n.value == v {
		n.count++
		return n
	}
	if n.value > v {
		n.left = treapInsert(n.left, v)
		if n.priority > n.left.priority {
			n = treapRotateRight(n)
		}
	} else {
		n.right = treapInsert(n.right, v)
		if n.priority > n.right.priority {
			n = treapRotateLeft(n)
		}
	}
	return n
}

func treapDelete(n *treapNode, v int) *treapNode {
	if n == nil {
		panic("node is not found!")
	}
	if n.value > v {
		n.left = treapDelete(n.left, v)
		return n
	}
	if n.value < v {
		n.right = treapDelete(n.right, v)
		return n
	}

	// n.value == v
	if n.count > 1 {
		n.count--
		return n
	}

	if n.left == nil && n.right == nil {
		return nil
	}

	if n.left == nil {
		n = treapRotateLeft(n)
	} else if n.right == nil {
		n = treapRotateRight(n)
	} else {
		// n.left != nil && n.right != nil
		if n.left.priority < n.right.priority {
			n = treapRotateRight(n)
		} else {
			n = treapRotateLeft(n)
		}
	}
	return treapDelete(n, v)
}

func treapCount(n *treapNode) int {
	if n == nil {
		return 0
	}
	return n.count + treapCount(n.left) + treapCount(n.right)
}

func treapString(n *treapNode) string {
	if n == nil {
		return ""
	}
	result := make([]string, 0)
	if n.left != nil {
		result = append(result, treapString(n.left))
	}
	result = append(result, fmt.Sprintf("%d:%d", n.value, n.count))
	if n.right != nil {
		result = append(result, treapString(n.right))
	}
	return strings.Join(result, " ")
}

func treapMin(n *treapNode) int {
	if n.left != nil {
		return treapMin(n.left)
	}
	return n.value
}

func treapGEMin(n *treapNode, v int) int {
	if n.value == v {
		return v
	}
	if n.value > v {
		if n.left != nil {
			return treapGEMin(n.left, v)
		}
		return n.value
	}
	// n.value < v
	if n.right != nil {
		return treapGEMin(n.right, v)
	}
	return math.MaxInt64
}

func treapMax(n *treapNode) int {
	if n.right != nil {
		return treapMax(n.right)
	}
	return n.value
}

type treap struct {
	root *treapNode
	size int
}

func (t *treap) Insert(v int) {
	t.root = treapInsert(t.root, v)
	t.size++
}

func (t *treap) Delete(v int) {
	t.root = treapDelete(t.root, v)
	t.size--
}

func (t *treap) String() string {
	return treapString(t.root)
}

func (t *treap) Count() int {
	return t.size
}

func (t *treap) Min() int {
	return treapMin(t.root)
}

func (t *treap) Max() int {
	return treapMax(t.root)
}

func (t *treap) GEMin(v int) int {
	return treapGEMin(t.root, v)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	defer flush()

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

	lt := &treap{}
	rt := &treap{}
	lt.Insert(A[0])
	for i := 2; i < N; i++ {
		rt.Insert(A[i])
	}

	result := math.MaxInt64
	for i := 1; i < N-1; i++ {
		a := lt.Min()
		b := rt.Min()
		if a <= A[i] && b <= A[i] {
			// printf("Konvex%d %d %d\n", a, A[i], b)
			result = min(result, a+A[i]+b)
		}

		c := lt.GEMin(A[i])
		d := rt.GEMin(A[i])
		if c != math.MaxInt64 && d != math.MaxInt64 && c >= A[i] && d >= A[i] {
			// printf("Konkav%d %d %d\n", c, A[i], d)
			result = min(result, c+A[i]+d)
		}

		lt.Insert(A[i])
		rt.Delete(A[i+1])
	}
	if result == math.MaxInt64 {
		println(-1)
	} else {
		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
}

func readInts(n int) []int {
	result := make([]int, n)
	for i := 0; i < n; i++ {
		result[i] = readInt()
	}
	return result
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdoutWriter, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}

Nachtrag: Es wird auch unten übergeben. Das kumulative Min von links und rechts wird verwendet. Da der Minimalwert über dem angegebenen Wert nicht durchsucht werden kann, wird die konkave Kadomatsu-Zeile vom Typ A i </ sub> auf B gesetzt Selbst wenn es erstellt werden kann, ist es möglicherweise nicht möglich, es zu erstellen. Ich denke, dass es eine falsche Lösung ist, aber ich denke an ein Gegenbeispiel, aber ich kann nicht daran denken. * O * (* N *).

from itertools import accumulate

INF = float('inf')

N, *A = map(int, open(0).read().split())

l = list(accumulate(A, min))
r = list(accumulate(A[::-1], min))[::-1]

result = INF

#Im Fall einer konvexen Kadomatsu-Reihe
for i in range(1, N - 1):
    a = l[i - 1]
    b = A[i]
    c = r[i + 1]
    if a <= b and c <= b:
        result = min(result, a + b + c)

#Im Fall einer konkaven Kadomatsu-Reihe
for i in range(1, N - 1):
    a = l[i - 1]
    b = A[i]
    c = r[i + 1]
    if b <= a and b <= c:
        result = min(result, a + b + c)

if result == INF:
    print(-1)
else:
    print(result)

B 1096 Range Sums

Wenn Sie es in Naiv schreiben, ist es * O * (* N * 3 </ sup>). Auch wenn Sie es addieren, * O * (* N * 2 </ sup>). Durch Eingabe wurde es * O * ( N </ i> log N </ i>) und gelöst.

from operator import add
from itertools import accumulate


class SegmentTree:
    _f = None
    _size = None
    _offset = None
    _data = None

    def __init__(self, size, f):
        self._f = f
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        f = self._f
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        f = self._f
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = next(it)
        for e in it:
            result = f(result, e)
        return result


N, *A = map(int, open(0).read().split())

a = list(accumulate(A))

st = SegmentTree(N, add)
st.build(a)

result = 0
result += st.query(0, N)
for i in range(1, N):
    result += st.query(i, N) - a[i - 1] * (N - i)
print(result)

Nachtrag: Ein i </ sub> wird zur Antwort hinzugefügt, wenn l = 1, .., i und r = i, ..., N, also ist die Häufigkeit, mit der es zur Antwort hinzugefügt wird, (i) + 1) × (N - i) Es war leicht zu glauben, dass dies der Fall sein würde. * O * (* N *).

N, *A = map(int, open(0).read().split())

result = 0
for i in range(N):
    # l = 0 .. i, r = i .. N - 1
    result += A[i] * (i + 1) * (N - i)
print(result)

Nachtrag: Einige Leute sagten, dass sie es mit Sparse-Tabelle anstelle von Seg-Baum gelöst haben. Ist es falsch mit Disjoint-Sparse-Tabelle? Sparse-Tabelle erfordert Gleichheit bei der Berechnung, aber im Gegensatz zu Min nicht Sum. Disjoint Ich hatte keine Implementierung einer Sparse-Tabelle, daher konnte ich sie nicht ausprobieren.

Nachtrag: Disjunkte Sparse-Tabelle implementiert.

from itertools import accumulate
from operator import add


class DisjointSparseTable:
    _f = None
    _data = None
    _lookup = None

    def __init__(self, a, f):
        self._f = f
        b = 0
        while (1 << b) <= len(a):
            b += 1
        _data = [[0] * len(a) for _ in range(b)]
        _data[0] = a[:]
        for i in range(1, b):
            shift = 1 << i
            for j in range(0, len(a), shift << 1):
                t = min(j + shift, len(a))
                _data[i][t - 1] = a[t - 1]
                for k in range(t - 2, j - 1, -1):
                    _data[i][k] = f(a[k], _data[i][k + 1])
                if t >= len(a):
                    break
                _data[i][t] = a[t]
                r = min(t + shift, len(a))
                for k in range(t + 1, r):
                    _data[i][k] = f(_data[i][k - 1], a[k])
        self._data = _data
        _lookup = [0] * (1 << b)
        for i in range(2, len(_lookup)):
            _lookup[i] = _lookup[i >> 1] + 1
        self._lookup = _lookup

    def query(self, start, stop):
        stop -= 1
        if start >= stop:
            return self._data[0][start]
        p = self._lookup[start ^ stop]
        return self._f(self._data[p][start], self._data[p][stop])


N, *A = map(int, open(0).read().split())

a = list(accumulate(A))

st = DisjointSparseTable(a, add)

result = 0
result += st.query(0, N)
for i in range(1, N):
    result += st.query(i, N) - a[i - 1] * (N - i)
print(result)

C 1097 Remainder Operation

Ich war glücklich, es 2 Minuten vor dem Ende zu lösen. Der gleiche Rest erscheint innerhalb von N-mal und Schleifen. Wenn Sie die Schleife erkennen und die Länge eines Zyklus und das Inkrement in einer Schleife finden, * O * (1) ) Um zu antworten, habe ich es mit * O * (* N * + * Q *) gelöst. Ich erinnerte mich an ABC167D - Teleporter.

from sys import stdin
readline = stdin.readline

N = int(readline())
A = list(map(int, readline().split()))

X = 0
b = [-1]
c = [X]
used = set()
while True:
    r = X % N
    X += A[r]
    if r in used:
        break
    used.add(r)
    b.append(r)
    c.append(X)
b.append(r)
c.append(X)
loop_start = b.index(b[-1])
loop_len = len(b) - loop_start - 1

Q = int(readline())
for _ in range(Q):
    K = int(readline())
    if K < len(b):
        print(c[K])
    else:
        K -= loop_start
        a = K // loop_len
        K %= loop_len
        K += loop_start
        print(c[K] + a * (c[-1] - c[loop_start]))

Recommended Posts