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