1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

AtCoder Beginner Contest 177 参戦記

Last updated at Posted at 2020-08-29

AtCoder Beginner Contest 177 参戦記

レーティングが5回連続下がっていたので、久々に上がって安心した.

ABC177A - Don't be late

2分で突破. 浮動小数点数は誤差が怖いので、T分間で歩ける距離がDメートル以上かでジャッジするようにした.

D, T, S = map(int, input().split())

if D > S * T:
    print('No')
else:
    print('Yes')

ABC177B - Substring

5分で突破、WA1. + 1 を忘れて死亡. ずらしながら違う文字が何文字があるかを調べて、最小値を取れば OK. Sの長さが1000なので、計算量は最大でも2.5×104.

S = input()
T = input()

result = float('inf')
for i in range(len(S) - len(T) + 1):
    t = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            t += 1
    result = min(result, t)
print(result)

ABC177C - Sum of product of pairs

4分で突破. ナイーブに2重ループで計算すると、計算量が2×1010で TLE してしまうので累積和した. 右から順番にやっていけば累積和いらないけど、まあいいでしょ.

from itertools import accumulate

m = 1000000007

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

result = 0
b = list(accumulate(A))
for i in range(N):
    result += A[i] * (b[N - 1] - b[i])
    result %= m
print(result)

追記: 累積和を使わずに解いてみた.

m = 1000000007

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

result = 0
c = 0
for i in range(1, N + 1):
    result += A[N - i] * c
    result %= m
    c += A[N - i]
    c %= m
print(result)

追々記: 右からやる必要もないな.

m = 1000000007

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

result = 0
c = 0
for a in A:
    result += a * c
    result %= m
    c += a
    c %= m
print(result)

ABC177D - Friends

4分で突破. 見るからに Union Find. 一番大きいユニオンに属する人数の数だけグループを作ればいい.

from sys import setrecursionlimit, stdin


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


readline = stdin.readline
setrecursionlimit(10 ** 6)

N, M = map(int, readline().split())

parent = [-1] * N
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, readline().split())
    unite(parent, A, B)

print(-min(parent))

ABC177E - Coprime

23分で突破. 右から素因数分解していけば行けるなと思った. setwise coprime かどうかも一緒に計算できそうな気がしたけど、時間をかけるのはパフォが落ちるので素直に別に計算した.

from math import gcd
from functools import reduce


def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


def is_pairwise_coprime():
    s = set()
    for i in range(N - 1, -1, -1):
        t = prime_factorize(A[i])
        for p, _ in t:
            if p in s:
                return False
            s.add(p)
    return True


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

prime_table = make_prime_table(10 ** 6)
if is_pairwise_coprime():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

追記: 公式解説動画を見たら素因数分解せずに解いてた. なるほどー.

from math import gcd
from functools import reduce

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

def is_pairwise_coprime():
    t = [0] * (10 ** 6 + 1)
    for a in A:
        t[a] += 1

    c = 0
    for j in range(2, 10 ** 6 + 1, 2):
        c += t[j]
    if c > 1:
        return False

    for i in range(3, 10 ** 6 + 1, 2):
        c = 0
        for j in range(i, 10 ** 6 + 1, i):
            c += t[j]
        if c > 1:
            return False

    return True

if is_pairwise_coprime():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

ABC177F - I hate Shortest Path Problem

1時間以上残っていたので初の全完チャンス!?と思ったが突破できず. 開始のX座標と現在のX座標が管理されていれば、移動回数は現在のX座標-開始のX座標+現在のY座標となる. 現在のX座標-開始のX座標の最小値を高速に求めるために二分探索木を用いる. 候補が壁にぶち当たった場合、壁の右端のX座標-開始のX座標が一番小さいの、つまり開始のX座標が最大のものだけ生き残って、他の候補は全部破棄となる. 壁の範囲の候補を高速に列挙するために二分探索木を用いる.

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 {
	key      int
	value    int
	priority uint
	left     *treapNode
	right    *treapNode
}

func newTreapNode(k int, v int) *treapNode {
	return &treapNode{k, v, xorshift(), 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 treapFind(n *treapNode, k int) *treapNode {
	if n == nil {
		return nil
	}
	if n.key == k {
		return n
	}
	if n.key > k {
		return treapFind(n.left, k)
	}
	return treapFind(n.right, k)
}

func treapLowerBound(n *treapNode, k int) *treapNode {
	if n == nil {
		return nil
	}
	if n.key < k {
		return treapLowerBound(n.right, k)
	}
	if t := treapLowerBound(n.left, k); t != nil {
		return t
	}
	return n
}

func treapInsert(n *treapNode, k int, v int) *treapNode {
	if n == nil {
		return newTreapNode(k, v)
	}
	if n.key == k {
		panic("node key is duplicated!")
	}
	if n.key > k {
		n.left = treapInsert(n.left, k, v)
		if n.priority > n.left.priority {
			n = treapRotateRight(n)
		}
	} else {
		n.right = treapInsert(n.right, k, v)
		if n.priority > n.right.priority {
			n = treapRotateLeft(n)
		}
	}
	return n
}

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

	// n.key == k
	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, k)
}

func treapCount(n *treapNode) int {
	if n == nil {
		return 0
	}
	return 1 + 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.key, n.value))
	if n.right != nil {
		result = append(result, treapString(n.right))
	}
	return strings.Join(result, " ")
}

func treapMin(n *treapNode) int {
	if n == nil {
		panic("node is not found!")
	}
	if n.left != nil {
		return treapMin(n.left)
	}
	return n.key
}

func treapMax(n *treapNode) int {
	if n == nil {
		panic("node is not found!")
	}
	if n.right != nil {
		return treapMax(n.right)
	}
	return n.key
}

type treap struct {
	root *treapNode
	size int
}

func (t *treap) Find(k int) *treapNode {
	return treapFind(t.root, k)
}

func (t *treap) LowerBound(k int) *treapNode {
	return treapLowerBound(t.root, k)
}

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

func (t *treap) Delete(k int) {
	t.root = treapDelete(t.root, k)
	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 max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	defer flush()

	H := readInt()
	W := readInt()

	candidates := &treap{}
	moves := &treap{}

	for i := 0; i < W; i++ {
		candidates.Insert(i, i)
	}
	moves.Insert(0, W)

	for i := 0; i < H; i++ {
		A := readInt() - 1
		B := readInt()

		r := -1
		for {
			n := candidates.LowerBound(A)
			if n == nil || n.key > B {
				break
			}
			r = max(r, n.value)
			t := moves.Find(n.key - n.value)
			t.value--
			if t.value == 0 {
				moves.Delete(t.key)
			}
			candidates.Delete(n.key)
		}

		if r != -1 && B != W {
			t := B - r
			n := moves.Find(t)
			if n == nil {
				moves.Insert(t, 1)
			} else {
				n.value++
			}
			candidates.Insert(B, r)
		}

		if moves.Count() == 0 {
			println(-1)
		} else {
			println(moves.Min() + i + 1)
		}
	}
}

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?