yukicoder contest 245 entry record

yukicoder contest 245 entry record

A 1033 Random Number Sai

The moment I saw the problem, I wondered what K was for, but I didn't need it (laughs). The average value of 0 to N was the sum of 0 to N divided by N + 1. Since it is a thing, (0 + N) * (N + 1) ÷ 2 ÷ (N + 1), so N ÷ 2.

N, K = map(int, input().split())

print(N / 2)

D 1036 Make One With GCD 2

I had a GCD version of SegmentTree, so it was an instant kill (laughs). Basically, it's a scale method. When GCD becomes 1, it's 1 no matter how far you go from there, so GCD (A i </ sub> >, A i + 1 </ sub>, ..., A j </ sub>) If it becomes 1 for the first time, A i </ sub> is the left end The number of subsequences whose GCD is 1 is N --j + 1. Next, we consider a subsequence with A i + 1 </ sub> at the left end, but of course the right end is j. This is the number above. Here, SegmentTree was used to calculate GCD (A i + 1 </ sub>, ..., A j </ sub>) at high speed. If j becomes N but GCD does not become 1, then GCD does not become 1 in the subsequence to the right of it, so the calculation can be stopped there.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b > 0 {
		a, b = b, a%b
	}
	return a
}

type segmentTree struct {
	data   []int
	offset int
}

func newSegmentTree(n int) segmentTree {
	var result segmentTree
	t := 1
	for t < n {
		t *= 2
	}
	result.offset = t - 1
	result.data = make([]int, 2*t-1)
	return result
}

func (st segmentTree) updateAll(a []int) {
	for i, v := range a {
		st.data[st.offset+i] = v
	}
	for i := st.offset - 1; i > -1; i-- {
		st.data[i] = gcd(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] = gcd(st.data[i*2+1], st.data[i*2+2])
	}
}

func (st segmentTree) query(start, stop int) int {
	result := 0
	l := start + st.offset
	r := stop + st.offset
	for l < r {
		if l&1 == 0 {
			result = gcd(result, st.data[l])
		}
		if r&1 == 0 {
			result = gcd(result, st.data[r-1])
		}
		l = l / 2
		r = (r - 1) / 2
	}
	return result
}

func main() {
	defer flush()

	N := readInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = readInt()
	}

	st := newSegmentTree(N)
	st.updateAll(A)

	result := 0
	j := 1
	for i := 0; i < N; i++ {
		v := st.query(i, j)
		for v != 1 && j < N {
			v = gcd(v, A[j])
			j++
		}
		if v != 1 {
			break
		}
		result += N - j + 1
	}
	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
}

func readInts(n int) []int {
	result := make([]int, n)
	for i := 0; i < n; i++ {
		result[i] = readInt()
	}
	return result
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdoutWriter, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}

B 1034 Tester Fuppy

It goes in a clockwise vortex, but first think about what volume (I, J) is. It turns out that it is the minimum value of I, J, N -1 --I, N -1 --J. When the minimum value is l, the number of movements before entering the lth volume is the total number of movements N * N minus the number of movements after the lth volume (N − 2 * l) * (N − 2 * l). After that, you can answer by checking the movement taken by advancing only one roll and adding it to the number of movements until entering the lth roll.

Q = int(input())

for i in range(Q):
    N, I, J = map(int, input().split())
    l = min(I, J, N - 1 - I, N - 1 - J)
    result = N * N - (N - 2 * l) * (N - 2 * l)
    N, I, J = N - 2 * l, I - l, J - l
    if I == 0:
        result += J
    elif J == N - 1:
        result += N - 1 + I
    elif I == N - 1:
        result += 2 * (N - 1) + (N - 1) - J
    elif J == 0:
        result += 3 * (N - 1) + (N - 1) - I
    print(result)

E 1037 exhausted

I wrote println (result) as print (result) and couldn't answer during the contest orz. When I wrote it in Python with the exact same algorithm, WA did not come out, but it was TLE, so I rewrote it in Go language. ing.

Every time I arrive at a gas station, I only do a DP with a pattern that puts fuel in and a pattern that does not put fuel in, so I think it's not particularly difficult. If the cost is high with the same amount of fuel, discard that pattern.

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	defer flush()

	N := readInt()
	V := readInt()
	L := readInt()

	cx := 0
	d := map[int]int{}
	d[V] = 0
	for i := 0; i < N; i++ {
		x := readInt()
		v := readInt()
		w := readInt()
		nd := map[int]int{}

		for k := range d {
			t := k - (x - cx)
			if t < 0 {
				continue
			}
			_, ok := nd[t]
			if !ok || nd[t] > d[k] {
				nd[t] = d[k]
			}
			t = min(t+v, V)
			_, ok = nd[t]
			if !ok || nd[t] > d[k]+w {
				nd[t] = d[k] + w
			}
		}

		if len(nd) == 0 {
			println(-1)
			return
		}
		d = nd
		cx = x
	}

	result := math.MaxInt64
	for k := range d {
		if k-(L-cx) >= 0 {
			result = min(result, d[k])
		}
	}
	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
}

func readInts(n int) []int {
	result := make([]int, n)
	for i := 0; i < n; i++ {
		result[i] = readInt()
	}
	return result
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdoutWriter, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}

C 1035 Color Box

If the total number of painting methods using i types of paint is f (i), then f (i) = M </ sub> C i </ sub> * i N </ sup> --f (i -1). Also, f (0) = 0.

It took more than 5 hours to get to this, orz. ★ 2 or lie.

from sys import setrecursionlimit

setrecursionlimit(1000000)

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

fac = [0] * (M + 1)
fac[0] = 1
for i in range(M):
    fac[i + 1] = fac[i] * (i + 1) % 1000000007


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], 1000000005, 1000000007) * pow(fac[k], 1000000005, 1000000007) % 1000000007


def f(i):
    if i == 0:
        return 0
    return (mcomb(M, i) * pow(i, N, 1000000007) - f(i - 1)) % 1000000007


print(f(M))

Recommended Posts

yukicoder contest 267 entry record
yukicoder contest 264 entry record
yukicoder contest 245 entry record
yukicoder contest 250 entry record
yukicoder contest 262 entry record
yukicoder contest 265 Participation record
yukicoder contest 266 Participation record
yukicoder contest 263 Participation record
yukicoder contest 273 Participation record
yukicoder contest 252 Participation record
yukicoder contest 259 Participation record
yukicoder contest 271 Participation record
yukicoder contest 251 Participation record
yukicoder contest 242 Participation record
yukicoder contest 241 Participation record
yukicoder contest 277 Participation record
yukicoder contest 257 Participation record
yukicoder contest 254 Participation record
yukicoder contest 246 Participation record
yukicoder contest 275 Participation record
yukicoder contest 274 Participation record
yukicoder contest 247 Participation record
yukicoder contest 261 Participation record
yukicoder contest 278 Participation record
yukicoder contest 248 Participation record
yukicoder contest 270 (mathematics contest) Participation record
yukicoder contest 272 (Weird math contest) Participation record
yukicoder contest 259 Review
yukicoder contest 264 Review
yukicoder contest 261 Review
yukicoder contest 267 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 175 Virtual entry