AtCoder ABC 135 D - Digits Parade ※解説AC未遂 (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。今回は解説ACすらできていないという困った状況です。

問題

全探索は途方もない組み合わせ数になり、10進数に対する13で割った剰余なので右何桁かを見てある程度決まるということもないという、かなりアプローチに困る問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const MOD = 1000000007
const DIV = 13
const BASE = 10

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    rs := append([]rune{'0'}, []rune(sc.Text())...)
    n := len(rs) - 1

    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, DIV)
    }
    dp[0][0] = 1

    for i := 1; i <= n; i++ {
        var digit int
        switch {
        case rs[i] == '?':
            digit = -1
        default:
            digit = int(rs[i] - '0')
        }

        for j := 0; j < BASE; j++ {
            if digit != -1 && digit != j {
                continue
            }
            for k := 0; k < DIV; k++ {
                dp[i][(k*BASE+j)%DIV] = (dp[i][(k*BASE+j)%DIV] + dp[i-1][k]) % MOD
            }
        }
    }
    fmt.Println(dp[n][5])
}

ほぼ公式解説のコードをGoに移植しただけなのであまり言えることはなかったりします。そもそもこのコードは8個ほどWAが出ているので移植しきれていないということなんですよね…

方針としては、上 $i$ 桁を13で割ったときの余りを用いて上 $i+1$ 桁を13で割った余りを求めることができることを利用して、桁DP（のようなこと）を行うというものです。これは、剰余の性質より $(10\times A + B) \mod M \equiv (10\times A \mod M) + (B \mod M)$ となることから明らかです。