AtCoder HHKB プログラミングコンテスト 2020 参戦記

HHKB2020A - Keyboard

2分で突破. 書くだけ.

S = input()
T = input()

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

HHKB2020B - Futon

3分で突破. 書くだけ.

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

6分半で突破. 制限からして O(N) にしないとダメそうだなあと思いつつ、一目でその方法が見えなくて悩んだ記憶がある割にそれほど時間がかかってないのが不思議. 毎行0から考え直していたらO(1)になる気がしなかったので、前の行の結果は受け継ぐとして、単調増加だからと考えた辺りでわかった.

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

30分くらい悩んだけど、端の処理が難しくてどうにも解けなかった. 問題文を読んだ感触でも、順位表でもEのほうが簡単そうだったのでそっちへ.

HHKB2020E - Lamps

60分くらい悩んだけど、交差している部分の処理が難しくてどうにも解けなかった.

追記: 各マスごとに灯りがついていないパターン数を引いていくのか. なるほどなあ. それが分かれば実装は難しくなかった.

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