AtCoder Library Practice Contest 参戦記 (Go)
ACL Contest は 1200 から rated なので rated で出場できるかどうしようと考えつつ、AtCoder Library Practice Contest を解いてみるテスト.
PRACTICE2A - Disjoint Set Union
ACL に Union Find 入ってないような、見落としてる??? あ、DSU = Disjoint Set Union = Union Find か.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func find(parent []int, i int) int {
if parent[i] < 0 {
return i
}
parent[i] = find(parent, parent[i])
return parent[i]
}
func unite(parent []int, i, j int) {
i = find(parent, i)
j = find(parent, j)
if i == j {
return
}
parent[j] += parent[i]
parent[i] = j
}
func main() {
defer flush()
N := readInt()
Q := readInt()
parent := make([]int, N)
for i := 0; i < N; i++ {
parent[i] = -1
}
for i := 0; i < Q; i++ {
t := readInt()
u := readInt()
v := readInt()
if t == 0 {
unite(parent, u, v)
} else if t == 1 {
if find(parent, u) == find(parent, v) {
println(1)
} else {
println(0)
}
}
}
}
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...)
}
PRACTICE2B - Fenwick Tree
3度目の登板.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
// BIT stands for binary indexed tree.
type BIT []int
func newBIT(n int) BIT {
return make([]int, n)
}
func (bit BIT) add(i, v int) {
for i++; i <= len(bit); i += i & -i {
bit[i-1] += v
}
}
func (bit BIT) sum(i int) int {
result := 0
for i++; i > 0; i -= i & -i {
result += bit[i-1]
}
return result
}
func (bit BIT) query(start int, stop int) int {
return bit.sum(stop-1) - bit.sum(start-1)
}
func main() {
defer flush()
N := readInt()
Q := readInt()
a := make([]int, N)
for i := 0; i < N; i++ {
a[i] = readInt()
}
bit := newBIT(N)
for i := 0; i < N; i++ {
bit.add(i, a[i])
}
for i := 0; i < Q; i++ {
t := readInt()
if t == 0 {
p := readInt()
x := readInt()
bit.add(p, x)
} else if t == 1 {
l := readInt()
r := readInt()
println(bit.query(l, r))
}
}
}
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...)
}
PRACTICE2C - Floor Sum
これの応用が想像できない.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func floorSum(n, m, a, b int) int {
result := 0
if a >= m {
result += (n - 1) * n * (a / m) / 2
a %= m
}
if b >= m {
result += n * (b / m)
b %= m
}
yMax := (a*n + b) / m
xMax := yMax*m - b
if yMax == 0 {
return result
}
result += (n - (xMax+a-1)/a) * yMax
result += floorSum(yMax, a, m, (a-xMax%a)%a)
return result
}
func main() {
defer flush()
T := readInt()
for i := 0; i < T; i++ {
N := readInt()
M := readInt()
A := readInt()
B := readInt()
println(floorSum(N, M, A, B))
}
}
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...)
}
PRACTICE2I - Number of Substrings
Go 言語のソートは癖があるなあと改めて思った.
package main
import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
)
func makeSuffixArray(s string) []int {
n := len(s)
sa := make([]int, n)
for i := 0; i < n; i++ {
sa[i] = i
}
rnk := make([]int, n)
for i, b := range []byte(s) {
rnk[i] = int(b)
}
tmp := make([]int, n)
for k := 1; k < n; k *= 2 {
cmp := func(x, y int) bool {
if rnk[sa[x]] != rnk[sa[y]] {
return rnk[sa[x]] < rnk[sa[y]]
}
rx, ry := -1, -1
if sa[x]+k < n {
rx = rnk[sa[x]+k]
}
if sa[y]+k < n {
ry = rnk[sa[y]+k]
}
return rx < ry
}
sort.Slice(sa, cmp)
tmp[sa[0]] = 0
for i := 1; i < n; i++ {
tmp[sa[i]] = tmp[sa[i-1]]
if cmp(i-1, i) {
tmp[sa[i]]++
}
}
tmp, rnk = rnk, tmp
}
return sa
}
func makeLcpArray(s string, sa []int) []int {
b := []byte(s)
n := len(s)
rnk := make([]int, n)
for i := 0; i < n; i++ {
rnk[sa[i]] = i
}
lcp := make([]int, n-1)
h := 0
for i := 0; i < n; i++ {
if h > 0 {
h--
}
if rnk[i] == 0 {
continue
}
j := sa[rnk[i]-1]
for j+h < n && i+h < n {
if b[j+h] != b[i+h] {
break
}
h++
}
lcp[rnk[i]-1] = h
}
return lcp
}
func main() {
defer flush()
S := readString()
sa := makeSuffixArray(S)
result := len(S) * (len(S) + 1) / 2
for _, x := range makeLcpArray(S, sa) {
result -= x
}
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
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
PRACTICE2J - Segment Tree
min_left もメソッドにするべきかな.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func max(x, y int) int {
if x > y {
return x
}
return y
}
type segmentTree struct {
offset int
data []int
op func(x, y int) int
e int
}
func newSegmentTree(n int, op func(x, y int) int, e int) segmentTree {
var result segmentTree
t := 1
for t < n {
t *= 2
}
result.offset = t - 1
result.data = make([]int, 2*t-1)
for i := 0; i < len(result.data); i++ {
result.data[i] = e
}
result.op = op
result.e = e
return result
}
func (st segmentTree) build(a []int) {
for i, v := range a {
st.data[st.offset+i] = v
}
for i := st.offset - 1; i > -1; i-- {
st.data[i] = st.op(st.data[i*2+1], st.data[i*2+2])
}
}
func (st segmentTree) update(index, value int) {
i := st.offset + index
st.data[i] = value
for i >= 1 {
i = (i - 1) / 2
st.data[i] = st.op(st.data[i*2+1], st.data[i*2+2])
}
}
func (st segmentTree) query(start, stop int) int {
result := st.e
l := start + st.offset
r := stop + st.offset
for l < r {
if l&1 == 0 {
result = st.op(result, st.data[l])
}
if r&1 == 0 {
result = st.op(result, st.data[r-1])
}
l = l / 2
r = (r - 1) / 2
}
return result
}
func main() {
defer flush()
N := readInt()
Q := readInt()
A := make([]int, N)
for i := 0; i < N; i++ {
A[i] = readInt()
}
st := newSegmentTree(N, max, -1)
st.build(A)
for i := 0; i < Q; i++ {
T := readInt()
if T == 1 || T == 3 {
X := readInt()
V := readInt()
if T == 1 {
st.update(X-1, V)
} else if T == 3 {
ok := N + 1
ng := X - 1
for ok-ng > 1 {
m := ng + (ok-ng)/2
if st.query(X-1, m) >= V {
ok = m
} else {
ng = m
}
}
println(ok)
}
} else if T == 2 {
L := readInt()
R := readInt()
println(st.query(L-1, R))
}
}
}
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...)
}