yukicoder contest 241 参戦記

A 1009 面積の求め方

8分半で突破. ヒント通り区分求積法でスパッと解いてみた. 区間をどれくらいの数で割ればいいのかに悩んだが、適当にえいやで4096でやったら一発目で良さげな精度が出たので、提出してみたら無事 AC.

a, b = map(int, input().split())

x = a
result = 0
t = 1 / 4096
while x < b:
    result += abs((x - a) * (x - b) * t)
    x += t
print(result)

B 1010 折って重ねて

41分で突破. 整数で処理するコードを書いて、なんで AC しないんだと延々と悩んでいた. アホすぎる. 縦と横で短い方を限界まで折ってから、長い方を限界まで折ればいい.

x, y, h = map(int, input().split())

if x < y:
    x, y = y, x

x *= 1000
y *= 1000

result = 0

while y > h:
    y /= 2
    h *= 2
    result += 1

while x > h:
    x /= 2
    h *= 2
    result += 1

print(result)

整数で処理することもできる. 相対的に数字が正しく変わればいいのだ.

x, y, h = map(int, input().split())

if x < y:
    x, y = y, x

x *= 1000
y *= 1000

result = 0

while y > h:
    x *= 2
    h *= 4
    result += 1

while x > h:
    y *= 2
    h *= 4
    result += 1

print(result)

C 1011 Infinite Stairs

敗退. 素直に DP すると O(N²d) なので TLE する. よくよく考えると、i 段目にたどり着くのは i-d .. i-1 段目、i + 1 段目にたどり着くのは i - d + 1 .. i と端の2箇所以外は同じである. であれば、O(d) ではなく O(1) で処理できるので O(N²) になり解けた.

package main

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

func main() {
	N := readInt()
	d := readInt()
	K := readInt()

	buf0 := make([]int, d*N+K+1)
	buf1 := make([]int, d*N+K+1)
	buf0[0] = 1
	for i := 0; i < N; i++ {
		t := 0
		for j := 0; j < d; j++ {
			t += buf0[j]
			t %= 1000000007
			buf1[j] = t
		}
		for j := d; j < (i+1)*d; j++ {
			t -= buf0[j-d]
			if t < 0 {
				t += 1000000007
			}
			t += buf0[j]
			t %= 1000000007
			buf1[j] = t
		}
		buf0, buf1 = buf1, buf0
	}
	fmt.Println(buf0[K-N])
}

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
}

# PyPy なら AC
N, d, K = map(int, input().split())

buf0 = [0] * (d * N + K + 1)
buf1 = [0] * (d * N + K + 1)
buf0[0] = 1

for i in range(N):
    t = 0
    for j in range(d):
        t += buf0[j]
        t %= 1000000007
        buf1[j] = t
    for j in range(d, (i + 1) * d):
        t -= buf0[j - d]
        t += buf0[j]
        t %= 1000000007
        buf1[j] = t
    buf0, buf1 = buf1, buf0

print(buf0[K - N])