[PYTHON] Teilnahmebericht des AtCoder HHKB Programmierwettbewerbs 2020

Teilnahmebericht des AtCoder HHKB Programmierwettbewerbs 2020

HHKB2020A - Keyboard

Brechen Sie in 2 Minuten durch. Schreiben Sie einfach.

S = input()
T = input()

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

HHKB2020B - Futon

Brechen Sie in 3 Minuten durch. Schreiben Sie einfach.

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

Es bricht in 6 ½ Minuten durch. Es dauert nicht lange, bis ich mich daran erinnere, dass ich die Methode nicht auf einen Blick sehen konnte Ich hatte nicht das Gefühl, dass es * O * (1) wäre, wenn ich für jede Zeile von 0 überdenken würde, also dachte ich, dass es ein monotoner Anstieg sein würde, vorausgesetzt, dass das Ergebnis der vorherigen Zeile vererbt würde.

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

Ich machte mir ungefähr 30 Minuten Sorgen, konnte es aber nicht lösen, weil es schwierig war, mit den Kanten umzugehen. Ich hatte das Gefühl, dass ich die Problemstellung gelesen hatte, und E schien in der Gesamtwertung einfacher zu sein, also ging ich dorthin.

HHKB2020E - Lamps

Ich machte mir etwa 60 Minuten Sorgen, konnte es aber nicht lösen, da es schwierig war, mit den sich kreuzenden Teilen umzugehen.

Nachtrag: Subtrahieren Sie die Anzahl der nicht beleuchteten Muster für jede Zelle? Ich verstehe. Sobald Sie das wissen, war die Implementierung nicht schwierig.

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