Tenka1 Programmer Beginner Contest 4/20/2019

はじめに

今までは時差（日本とシアトルは現時点で16時間の時差があります）のせいで、朝5時起きを強いられるAtCoderに手を付けていなかったのですが、goの練習がてらコンテストに参加することにしました。

結局、6時に起きてC問題まで解いて二度寝しましたが、せっかくA~Cまで解いたからには感想でも書いておくことにしました。

A問題

大小比較するだけです。O(1)

package main

import "fmt"

func main() {
    var a int
    var b int
    var c int
    fmt.Scan(&a, &b, &c)
    if a >= c && b <= c || a <= c && c <= b {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}

B問題

文字操作するだけです。O(n)

package main

import (
    "fmt"
)

func main() {
    var N int
    var S string
    var K int
    fmt.Scan(&N, &S, &K)
    s := S[K-1]
    ans := ""
    for i := 0; i < N; i++ {
        if s == S[i] {
            ans += string(S[i])
        } else {
            ans += "*"
        }
    }
    fmt.Println(ans)
}

C問題

今回感想を書いた理由はこの問題が累乗和を使って解く問題だったからです。

問題文の条件は、左端から連続するいくつかの石を白に、それ以外の石を黒にするという条件です。求めたいものは、各境目に対してそれより左にある黒い石の個数とそれより右にある白い石の個数の和を求めたときの、一番小さい値です。単純にループしてしまうとO(N²)になってしまいますが、これを累乗和で解決したいと思います。

累乗和に関しては、以下の記事を参考にしていただければと思います。

累積和を何も考えずに書けるようにする！ - Qiita

この問題を図解してみると、以下のようになります。 各境界において、白を何個、黒を何個ひっくり返せばよいのかということが配列（rightWhite, leftBlack）に格納されています。各配列の要素の和が一番小さくなるものが解となります。オーダーもO(N)なのでいい感じです。

図で理解する

package main

import (
    "fmt"
)

func main() {
    var n int
    var s string
    fmt.Scan(&n)
    fmt.Scan(&s)

    if n == 1 {
        fmt.Println(0)
        return
    }

    leftBlacks := make([]int, n+1)
    rightWhites := make([]int, n+1)
    for i := 0; i < n; i++ {
        if s[i] == '.' {
            rightWhites[0]++
        }
    }

    for i := 0; i < n; i++ {
        if s[i] == '.' {
            rightWhites[i+1] = rightWhites[i] - 1
            leftBlacks[i+1] = leftBlacks[i]
        } else {
            rightWhites[i+1] = rightWhites[i]
            leftBlacks[i+1] = leftBlacks[i] + 1
        }
    }

    min := rightWhites[0] + leftBlacks[0]
    for i := 1; i < n+1; i++ {
        if rightWhites[i]+leftBlacks[i] < min {
            min = rightWhites[i] + leftBlacks[i]
        }
    }

    fmt.Println(min)
}

おわりに

競プロ用アルゴリズムをgithubにストックしておこうと思つつ忘れていたのを思い出しました。