[PYTHON] Rapport de participation au concours de programmation AtCoder HHKB 2020

Rapport de participation au concours de programmation AtCoder HHKB 2020

HHKB2020A - Keyboard

Percer en 2 minutes. Il suffit d'écrire.

S = input()
T = input()

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

HHKB2020B - Futon

Percer en 3 minutes. Il suffit d'écrire.

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

Cela prend 6 minutes et demie. Cela ne prend pas beaucoup de temps même si je me souviens m'être inquiété de ne pas voir la méthode d'un coup d'œil, pensant que ce serait inutile si je devais la régler sur * O * (* N *) à cause de la limite. Je n'avais pas l'impression que ce serait * O * (1) si je revenais à partir de 0 pour chaque ligne, alors j'ai pensé que ce serait une augmentation monotone, en supposant que le résultat de la ligne précédente serait hérité.

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

J'étais inquiet environ 30 minutes, mais je n'ai pas pu le résoudre car il était difficile de gérer les carres.J'ai senti que j'avais lu l'énoncé du problème, et E semblait être plus facile au classement, alors j'y suis allé.

HHKB2020E - Lamps

J'étais inquiet environ 60 minutes, mais je n'ai pas pu le résoudre car il était difficile de gérer les parties qui se croisaient.

Post-scriptum: soustrayez-vous le nombre de motifs non éclairés pour chaque cellule? Je vois. Une fois que vous savez cela, ce n'était pas difficile à mettre en œuvre.

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