AtCoder Débutant Contest 170 Rapport de participation

AtCoder Débutant Contest 170 Rapport de participation

ABC170A - Five Variables

Percer en 2 minutes. Il suffit d'écrire. Dès le début, je me suis demandé quoi faire si x i </ sub> était égal à 0, mais x i </ sub> = i, haha.

x = list(map(int, input().split()))

for i in range(5):
    if x[i] == 0:
        print(i + 1)
        break

ABC170B - Crane and Turtle

Percer en deux minutes et demie. Il suffit d'écrire. La zone qui ne peut pas être écrite avec O (1) est faible.

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

for i in range(X + 1):
    if i * 2 + (X - i) * 4 == Y:
        print('Yes')
        break
else:
    print('No')

ABC170C - Forbidden List

Percer en 3 minutes. S'il y a deux éléments avec la même différence absolue, écrivez simplement en gardant à l'esprit le plus petit. Explication PDF "Si cette question a été posée comme problème B, précisez ci-dessous. Je vais décrire une méthode de mise en œuvre typique, mais je pense qu'une telle explication n'est pas nécessaire pour ceux qui peuvent résoudre le problème C, je vais donc l'omettre. "

X, N = map(int, input().split())
p = list(map(int, input().split()))

p = set(p)
for i in range(200):
    if X - i not in p:
        print(X - i)
        break
    if X + i not in p:
        print(X + i)
        break

ABC170D - Not Divisible

Il a éclaté en 56 minutes et demie RE1, WA3 Il a fallu beaucoup de temps pour se rendre compte que la quantité de calcul diminuerait s'il était fait comme un tamis d'Elatostines.

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

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

A = sorted(set(A))
t = [True] * (10 ** 6 + 1)
for a in A:
    if d[a] > 1:
        t[a] = False
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

ABC170E - Count Median

Je ne pouvais pas percer. Je pensais que c'était un multiset, mais Python n'avait pas de multiset intégré et je n'avais pas assez de temps ... Dois-je réécrire mon Treap pour le rendre un peu plus polyvalent?

Addendum: Quand je l'ai écrit en Python, il est devenu TLE, donc je n'avais pas d'autre choix que de l'écrire en C ++. Bon, avec le multiset, il n'y a rien de particulièrement difficile ...

#include <bits/stdc++.h>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
using namespace std;

int main()
{
    int N, Q;
    cin >> N >> Q;

    multiset<int> max_ratings;
    vector<multiset<int>> kindergartens(2 * pow(10, 5) + 1);
    vector<int> ratings(N + 1), belongs(N + 1);

    rep(i, N) {
        int A, B;
        cin >> A >> B;
        ratings[i + 1] = A;
        belongs[i + 1] = B;
        kindergartens[B].insert(A);
    }

    rep(i, 2 * pow(10, 5) + 1) {
        if (kindergartens[i].size() != 0) {
            max_ratings.insert(*kindergartens[i].rbegin());
        }
    }

    rep(_, Q) {
        int C, D;
        cin >> C >> D;
        int b = belongs[C];
        belongs[C] = D;
        max_ratings.erase(max_ratings.find(*kindergartens[b].rbegin()));
        kindergartens[b].erase(ratings[C]);
        if (kindergartens[b].size() != 0) {
            max_ratings.insert(*kindergartens[b].rbegin());
        }
        if (kindergartens[D].size() != 0) {
            max_ratings.erase(max_ratings.find(*kindergartens[D].rbegin()));
        }
        kindergartens[D].insert(ratings[C]);
        max_ratings.insert(*kindergartens[D].rbegin());
        cout << *max_ratings.begin() << endl;
    }

    return 0;
}

Je l'ai passé même avec go.

package main

import (
	"bufio"
	"fmt"
	"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 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 main() {
	defer flush()

	N := readInt()
	Q := readInt()

	maxRatings := &treap{}
	kindergartens := make([]*treap, 200001)
	for i := 0; i < 200001; i++ {
		kindergartens[i] = &treap{}
	}
	ratings := make([]int, N+1)
	belongs := make([]int, N+1)

	for i := 1; i < N+1; i++ {
		A := readInt()
		B := readInt()
		ratings[i] = A
		belongs[i] = B
		kindergartens[B].Insert(A)
	}

	for i := 1; i < 200001; i++ {
		if kindergartens[i].Count() != 0 {
			maxRatings.Insert(kindergartens[i].Max())
		}
	}

	for i := 0; i < Q; i++ {
		C := readInt()
		D := readInt()

		from := kindergartens[belongs[C]]
		to := kindergartens[D]
		rating := ratings[C]
		belongs[C] = D

		maxRatings.Delete(from.Max())
		from.Delete(rating)
		if from.Count() != 0 {
			maxRatings.Insert(from.Max())
		}

		if to.Count() != 0 {
			maxRatings.Delete(to.Max())
		}
		to.Insert(rating)
		maxRatings.Insert(to.Max())

		println(maxRatings.Min())
	}
}

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

Recommended Posts

AtCoder Beginner Contest 181 Rapport de participation
AtCoder Beginner Contest 161 Rapport de participation
AtCoder Beginner Contest 151 Rapport de participation
AtCoder Débutant Contest 176 Rapport de participation
AtCoder Beginner Contest 154 Rapport de participation
AtCoder Beginner Contest 166 Rapport de participation
AtCoder Beginner Contest 145 Rapport de participation
AtCoder Débutant Contest 184 Rapport de participation
AtCoder Beginner Contest 165 Rapport de participation
Rapport de participation au concours AtCoder Débutant 160
AtCoder Beginner Contest 169 Rapport de participation
AtCoder Beginner Contest 159 Rapport de participation
AtCoder Beginner Contest 164 Rapport de participation
AtCoder Beginner Contest 168 Rapport de participation
Rapport de participation au concours AtCoder Débutant 150
AtCoder Beginner Contest 158 Rapport de participation
Rapport de participation au concours AtCoder Débutant 180
AtCoder Beginner Contest 156 Rapport de participation
AtCoder Beginner Contest 162 Rapport de participation
AtCoder Débutant Contest 157 Rapport de participation
AtCoder Beginner Contest 167 Rapport de participation
AtCoder Débutant Contest 179 Rapport de participation
Concours AtCoder Débutant 182
AtCoder Beginner Contest 146 Rapport de participation
AtCoder Beginner Contest 152 Rapport de participation
AtCoder Beginner Contest 171 Rapport de participation
AtCoder Beginner Contest 149 Rapport de participation
AtCoder Beginner Contest 148 Rapport de participation
AtCoder Débutant Contest 170 Rapport de participation
AtCoder Débutant Contest 183 Rapport de participation
Note de participation au concours pour débutants AtCoder # 003
AtCoder Grand Contest 041 Rapport de participation
AtCoder Grand Contest 040 Rapport de participation
Rapport de participation au concours régulier AtCoder 105
AtCoder Regular Contest 104 Rapport de participation
Fiche d'inscription au concours ACL pour débutant
Journal de participation Atcoder Beginner Contest 146
AtCoder Chokudai Contest 005 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
Rapport de participation au concours de programmation AtCoder HHKB 2020
Rapport de participation au concours de programmation AtCoder Acing 2020
Rapport de participation au concours de programmation AtCoder Keyence 2020
Rapport de participation au concours de programmation AtCoder Panasonic 2020
Critique du concours AtCoder Beginner Contest 152
Concours AtCoder Débutant 181 Remarque
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Concours AtCoder Débutant 180 Remarque
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Concours AtCoder Débutant 182 Remarque
Critique du concours AtCoder