AtCoder Beginner Contest 170 Participation Report

AtCoder Beginner Contest 170 Participation Report

ABC170A - Five Variables

Break through in 2 minutes. Just write. From the beginning I thought what to do if x i </ sub> was 0, but 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

Break through in two and a half minutes. Just write. The area that can not be written with O (1) is weak.

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

Break through in 3 minutes. When there are two items with the same absolute value of difference, just write with the smaller one in mind. I'm going to describe a typical implementation method, but I think that such an explanation is unnecessary for those who can solve problem C, so I will omit it. "

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

It broke through in 56 and a half minutes. RE1, WA3. It took a long time to realize that if you do it like a sieve of Eratosthenes, the amount of calculation will decrease.

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

I couldn't break through. I thought it was a multiset, but Python didn't have a built-in multiset and I didn't have enough time left ... Should I rewrite my Treap to make it a little more versatile?

Postscript: When I wrote it in Python, it became TLE, so I had no choice but to write it in C ++. Well, with multiset, there is nothing particularly difficult ...

#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;
}

I passed it even with 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 Participation Report
AtCoder Beginner Contest 161 Participation Report
AtCoder Beginner Contest 151 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Beginner Contest 154 Participation Report
AtCoder Beginner Contest 166 Participation Report
AtCoder Beginner Contest 145 Participation Report
AtCoder Beginner Contest 184 Participation Report
AtCoder Beginner Contest 165 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Beginner Contest 168 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 158 Participation Report
AtCoder Beginner Contest 180 Participation Report
AtCoder Beginner Contest 156 Participation Report
AtCoder Beginner Contest 162 Participation Report
AtCoder Beginner Contest 157 Participation Report
AtCoder Beginner Contest 167 Participation Report
AtCoder Beginner Contest 179 Participation Report
AtCoder Beginner Contest 182 Participation Report
AtCoder Beginner Contest 146 Participation Report
AtCoder Beginner Contest 152 Participation Report
AtCoder Beginner Contest 171 Participation Report
AtCoder Beginner Contest 149 Participation Report
AtCoder Beginner Contest 148 Participation Report
AtCoder Beginner Contest 188 Participation Report
AtCoder Beginner Contest 170 Participation Report
AtCoder Beginner Contest 187 Participation Report
AtCoder Beginner Contest 183 Participation Report
AtCoder Beginner Contest # 003 Participation Note
AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 040 Participation Report
AtCoder Regular Contest 105 Participation Report
AtCoder Regular Contest 104 Participation Report
ACL Beginner Contest Participation Report
Atcoder Beginner Contest 146 Participation Diary
AtCoder Chokudai Contest 005 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder HHKB Programming Contest 2020 Participation Report
AtCoder Acing Programming Contest 2020 Participation Report
AtCoder Keyence Programming Contest 2020 Participation Report
AtCoder Panasonic Programming Contest 2020 Participation Report
AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 181 Note
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 182 Note
AtCoder Beginner Contest 164 Review