[PYTHON] AtCoder HHKB Programming Contest 2020 Participation Report

AtCoder HHKB Programming Contest 2020 Participation Report

HHKB2020A - Keyboard

Break through in 2 minutes. Just write.

S = input()
T = input()

if S == 'Y':
    print(T.upper())
elif S == 'N':
    print(T)

HHKB2020B - Futon

Break through in 3 minutes. Just write.

H, W = map(int, input().split())
S = [input() for _ in range(H)]

result = 0
for h in range(H):
    for w in range(W - 1):
        if S[h][w] == '.' and S[h][w + 1] == '.':
            result += 1
for h in range(H - 1):
    for w in range(W):
        if S[h][w] == '.' and S[h + 1][w] == '.':
            result += 1
print(result)

HHKB2020C - Neq Min

It breaks through in 6 and a half minutes. It doesn't take much time even though I remember worrying that I couldn't see the method at a glance, thinking that it would be useless to set it to * O * (* N *) due to the limit. It's strange. I didn't feel like it would be * O * (1) if I reconsidered from 0 for each line, so I thought that it would be a monotonous increase, assuming that the result of the previous line would be inherited.

N, *p = map(int, open(0).read().split())

result = []
t = 0
s = set()
for x in p:
    s.add(x)
    while t in s:
        t += 1
    result.append(t)
print(*result, sep='\n')

HHKB2020D - Squares

I was worried about 30 minutes, but I couldn't solve it because it was difficult to handle the edges. I felt that I read the problem statement and E seemed to be easier in the standings, so I went there.

HHKB2020E - Lamps

I was worried about 60 minutes, but I couldn't solve it because it was difficult to handle the intersecting parts.

Postscript: Do you subtract the number of unlit patterns for each square? I see. Once you know that, it wasn't difficult to implement.

package main

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

const (
	m = 1000000007
)

func main() {
	defer flush()

	H := readInt()
	W := readInt()
	S := make([]string, H)
	for i := 0; i < H; i++ {
		S[i] = readString()
	}

	K := H * W
	for i := 0; i < H; i++ {
		for j := 0; j < W; j++ {
			if S[i][j] == '#' {
				K--
			}
		}
	}

	yoko := make([][]int, H)
	tate := make([][]int, H)
	for i := 0; i < H; i++ {
		yoko[i] = make([]int, W)
		tate[i] = make([]int, W)
	}

	for i := 0; i < H; i++ {
		s := 0
		l := 0
		for j := 0; j < W; j++ {
			if S[i][j] == '#' {
				for k := s; k < j; k++ {
					yoko[i][k] = l
				}
				s = j + 1
				l = 0
			} else if S[i][j] == '.' {
				l++
			}
		}
		for k := s; k < W; k++ {
			yoko[i][k] = l
		}
	}

	for i := 0; i < W; i++ {
		s := 0
		l := 0
		for j := 0; j < H; j++ {
			if S[j][i] == '#' {
				for k := s; k < j; k++ {
					tate[k][i] = l
				}
				s = j + 1
				l = 0
			} else if S[j][i] == '.' {
				l++
			}
		}
		for k := s; k < H; k++ {
			tate[k][i] = l
		}
	}

	t := make([]int, K+1)
	t[0] = 1
	for i := 1; i < K+1; i++ {
		t[i] = t[i-1] * 2
		t[i] %= m
	}

	c := 0
	for i := 0; i < H; i++ {
		for j := 0; j < W; j++ {
			if S[i][j] == '#' {
				continue
			}
			c += t[K-tate[i][j]-yoko[i][j]+1]
			c %= m
		}
	}

	result := K * t[K]
	result %= m
	result -= c
	result += m
	result %= m
	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...)
}