E - Safety Journey

2023年苦手なジャンルを克服しよう数え上げ編です。

問題

頂点の完全グラフが与えられる。このうち、本の辺は使えない。
個のパスのうち、始点と終点が1で終わるパスの数を答えよ。

atcoder.jp

解法/ 考えてたこと

解説ACしたが思いつけそうな問題だった。反省。

• 総当りは当然不可能なので、番目のときに頂点にいるときの総数を管理する方針を考えた。ただし、これは更新がかかる。具体的には、 番目のに対して個の更新を考える必要があり、できない。

• ならば余事象で攻めるか？となるが、できない。使えない辺を使っているパスを重複なく列挙するのは難しい。これを実装するまで気づかなかったのが本当に良くない。

• 最初の方針で攻めるしかないかなとなりつつ、計算量を減らせない。おそらく更新をサボるんだろうなぁ(つまり、使わない辺だけを使って更新するんだろうなぁ）と考えていたが、思いつけなかった。

• ここから解法。3番目の方針で解ける。テーブルは以下の通り

番目のパスのときに頂点にいるときの総数　で解ける。

更新は、使わない辺だけを使うのではなく、すべての辺を使った結果から、使わない辺を使っている結果を引く で更新すれば良い。イメージ的には累積和みたいな感じ。

うーん確かに。式にしてみればあっさりしている。列挙となった時かなり頭が固くなっている気がするので、慣れていきたいところ。

提出したコード

特に理由は無いけどGoで書きました

package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func main() {
	sc.Split(bufio.ScanWords)

	N, M, K := nextInt(), nextInt(), nextInt()

	edge := make([][]int, N)
	dp := make([][]int64, K+1)
	mod := int64(998244353)

	for i := range dp {
		dp[i] = make([]int64, N)
	}

	for i := 0; i < M; i += 1 {
		u, v := nextInt()-1, nextInt()-1
		edge[u] = append(edge[u], v)
		edge[v] = append(edge[v], u)
	}
	dp[0][0] = 1
	prev := int64(1)
	for i := range dp {

		if i == 0 {
			continue
		}

		for j := range dp[i] {
			tmp := prev

			tmp -= dp[i-1][j]
			tmp += mod
			tmp %= mod

			for k := range edge[j] {
				nxt := edge[j][k]
				tmp -= dp[i-1][nxt]
				tmp += mod
				tmp %= mod
			}
			dp[i][j] = tmp
		}

		tmp := int64(0)
		for j := range dp[i] {
			tmp += dp[i][j]
			tmp %= mod
		}
		prev = tmp
	}
	fmt.Println(dp[K][0])
}