diverta 2019 Programming Contest C - AB Substrings / D - DivRem Number 失敗例と嘘解法(Go)

irisruneです。久々にコンテストに参加したらUnratedになったなんとも言い難いお話。

C - AB Substrings

atcoder.jp

全探索は（かかるため）できないとして、計算で求めるための場合分けが難しかったです。まずは失敗例を。

package main

import "fmt"

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    var n int
    fmt.Scan(&n)
    sArr := make([]string, n)
    for i := range sArr {
        fmt.Scan(&sArr[i])
    }

    cntA, cntB, cntAB := 0, 0, 0
    for _, s := range sArr {
        if s[0:1] == "B" {
            cntB++
        }
        for i := 0; i < len(s)-1; i++ {
            if s[i:i+2] == "AB" {
                cntAB++
            }
        }
        if s[len(s)-1:len(s)] == "A" {
            cntA++
        }
    }

    fmt.Println(cntAB + minInt(n-1, minInt(cntA, cntB)))
}

見ればわかるかもしれませんが、Bで始まってAで終わる文字列の数というものをカウントしていません。 すべての文字列がBで始まってAで終わる場合は（と文字列中の"AB"の数の和）を返すようにしていましたがそれでは不十分でしたね。

解説読んだ後ですら3WAしましたが解説ACしたコードがこちらになります。

package main

import "fmt"

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    var n int
    fmt.Scan(&n)
    sArr := make([]string, n)
    for i := range sArr {
        fmt.Scan(&sArr[i])
    }

    cntBtoA, cntToA, cntBto, cntAB := 0, 0, 0, 0
    for _, s := range sArr {
        switch {
        case s[0:1] == "B" && s[len(s)-1:len(s)] == "A":
            cntBtoA++
        case s[0:1] == "B":
            cntBto++
        case s[len(s)-1:len(s)] == "A":
            cntToA++
        }
        for i := 0; i < len(s)-1; i++ {
            if s[i:i+2] == "AB" {
                cntAB++
            }
        }
    }

    var ans int
    switch {
    case cntToA+cntBto == 0:
        ans = cntAB + maxInt(0, cntBtoA-1)
    default:
        ans = cntAB + cntBtoA + minInt(cntToA, cntBto)
    }
    fmt.Println(ans)
}

思いの外場合分けがややこしくて解説ACするのも少し苦労しました。

コードレビュー - C

• Bで始まる文字列、Aで終わる文字列、Bで始まってAで終わる文字列それぞれの数をカウントする変数の名前をもう少しうまく付けたい。

D - DivRem Number

atcoder.jp

最初の方針から嘘解法でそのまま貫き通してしまった感じです。こちらも失敗例から。

package main

import (
    "fmt"
)

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

    ans := 0
    for i := 1; i*i < n; i++ {
        if (n-i)%i == 0 {
            ans += (n - i) / i
        }
    }
    fmt.Println(ans)
}

少し解説をすると、のときはをで割った商がより小さくなることはなく、 一方であまりはより必ず小さくなるためお気に入りの数になることはありません。 そのためお気に入りの数はに絞り込むことができますが、このままでは計算量は全探索とあまり変わりません（のため）。 しかしのとき商は必ずより小さくなるので商に対して全探索をかけることでお気に入りの数を列挙することができます。 あとはから商の候補である値を引いた数がその値で割り切れれば、割った後の数がお気に入りの数になります。

…と言いたいところですが、例えばに対して商をとおいてしまうとお気に入りの数としてが求められてしまいこれは明らかに題意を満たしません。要するに商の候補である値がそのものの約数である場合お気に入りの数を誤判定してしまいます。

そんなわけで、判定部分を問題文により忠実にしたのが以下のコードになります。

package main

import (
    "fmt"
)

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

    ans := 0
    for i := 1; i*i < n; i++ {
        if (n-i)%i == 0 {
            div := (n - i) / i
            if n/div == n%div {
                ans += div
            }
        }
    }
    fmt.Println(ans)
}

判定部分は少しだけ複雑になりましたが、関数minIntが不要になったためコード長自体は短くなりました。初めから不要でしたね。

コードレビュー - D

• お気に入りの数（の候補）として変数divを使っているが、mにした方がより明確。

雑記

• 想定パフォは1224でレートは1上昇だったらしいです。Ratedでもあまり変わりませんでしたね。
  • Cが解けていれば時間によっては青パフォどころか黄パフォがあり得たと考えるとUnratedとはいえ少し悔しいですね。