マイナビプログラミングコンテスト2021(AtCoder Beginner Contest 201) 参戦記

2週連続でコケてしまった…….

ABC201A - Tiny Arithmetic Sequence

2分で突破. 書くだけ.

A = list(map(int, input().split()))

A.sort()

if A[2] - A[1] == A[1] - A[0]:
    print('Yes')
else:
    print('No')

ABC201B - Do you know the second highest mountain?

4分で突破. 高さがそれぞれ相異なることが保証されているので、何も考えずソートすればいい.

N = int(input())
ST = []
for _ in range(N):
    S, T = input().split()
    ST.append((int(T), S))

ST.sort(reverse=True)
print(ST[1][1])

ABC201C - Secret Number

14分で突破. 最大でも10⁴通りしかないので、全部生成してしまうことにした. Python の itertools がパワフルなので、全生成してよければ簡単.

from itertools import product, permutations

S = input()

if S.count('o') > 4 or S.count('x') == 10:
    print(0)
    exit()

base = []
option = []
for i in range(10):
    if S[i] == 'o':
        base.append(str(i))
    if S[i] != 'x':
        option.append(str(i))

result = set()
for p1 in product(option, repeat=4 - len(base)):
    for p2 in permutations(base + list(p1)):
        result.add(''.join(list(p2)))
print(len(result))

ABC201D - Game in Momotetsu World

73分半で突破. RE3、TLE6. メモ化再帰で素直にシミュレートすればいいかと思いきや、Python / PyPy では TLE となった. Go で書き直しても 457ms だったので、そりゃダメだなあと思った.

package main

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

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

var (
	cache []int
	H, W  int
	A     [][]int
)

const (
	INF = math.MaxInt64
)

func f(y, x int) int {
	key := (y << 12) + x
	if y == H-1 && x == W-1 {
		return 0
	}
	if cache[key] != INF {
		return cache[key]
	}
	result := -INF
	if y < H-1 {
		result = max(result, A[y+1][x]-f(y+1, x))
	}
	if x < W-1 {
		result = max(result, A[y][x+1]-f(y, x+1))
	}
	cache[key] = result
	return result
}

func main() {
	defer flush()

	H = readInt()
	W = readInt()
	A = make([][]int, H)
	for i := 0; i < H; i++ {
		A[i] = make([]int, W)
		s := readString()
		for j := 0; j < W; j++ {
			if s[j] == '-' {
				A[i][j] = -1
			} else if s[j] == '+' {
				A[i][j] = 1
			}
		}
	}

	cache = make([]int, 1<<24)
	for i := 0; i < len(cache); i++ {
		cache[i] = INF
	}

	result := f(0, 0)
	if result == 0 {
		println("Draw")
	} else if result > 0 {
		println("Takahashi")
	} else if result < 0 {
		println("Aoki")
	}
}

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