(競プロ)Goで挑戦するAtcoder Beginner Contest 243の復習(A~F)

# 初めに
　なんとなく競技プログラミングを再開することにしたのでその復習をここに残しておきます。ちなみに私は茶色コーダーなのでE以降は解けていないです。
　今回はバーチャル参加しましたが、今後も余裕があれば時間を測って昔のコンテストでも解いてみようと思います。

# A - Shampoo
[A - Shampoo](https://atcoder.jp/contests/abc243/tasks/abc243_a)
これは最初そのままvをaやbと比較したものを提出しましたが、普通にWAで(a+b+c)との剰余をとるのを忘れていました。
以下ACだった実装です。

```
package main

import (
	"fmt"
)

func main() {
	var v, a, b, c int
	fmt.Scan(&v, &a, &b, &c)
	v = v % (a + b + c)
	if v < a {
		fmt.Println("F")
	} else if v < a+b {
		fmt.Println("M")
	} else {
		fmt.Println("T")
	}
}

```

# B - Hit and Blow
[B - Hit and Blow](https://atcoder.jp/contests/abc243/tasks/abc243_b)
　整数列の比較を行う問題です。問題文通りに実装すればクリアできました。$N<=1000$なので全探索でいけます。実装は条件1と条件2で別でカウントする必要があります。

```golang
package main

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

func main() {
	var n int
	r := bufio.NewReader(os.Stdin)
	fmt.Fscan(r, &n)
	a := make([]int, n)
	b := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &a[i])
	}
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &b[i])
	}
	counti := 0
	countj := 0
	for i := 0; i < n; i++ {
		if a[i] == b[i] {
			counti++
		}
		for j := 0; j < n; j++ {
			if j == i {
				continue
			}
			if a[i] == b[j] {
				countj++
			}
		}
	}
	fmt.Println(counti)
	fmt.Println(countj)
}

```

# C - Collision 2
[C - Collision 2](https://atcoder.jp/contests/abc243/tasks/abc243_c)
ここらへんから実装の際に工夫が必要になってきました。衝突は同じY座標にいる人同士でしか起こらないので初めはY座標をキーにもつ辞書を実装し同じY座標の人を全て比較しようとしましたが、もし全ての人が同じY座標であれば計算量は$O(n^2)$で厳しそうでした。
そこでY座標順でソートし、特定のY座標について左を向いている人の中で最もx座標が大きい人と、右を向いている人の中で最もx座標が小さい人のx座標を比較するような実装をしました。これによって比較にかかる時間は$O(n)$で収まるため全体の計算量はソートの$O(n\log n)$で済みます。

データは全てスライスで格納しましたが、人のデータは構造体で管理したほうがよさそうです。

```golang
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	var n int
	var s string
	r := bufio.NewReader(os.Stdin)
	fmt.Fscan(r, &n)
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		b := make([]int, 3)
		fmt.Fscan(r, &b[0], &b[1])
		a[i] = b
	}
	// y軸が小さい順に並ぶ
	fmt.Fscan(r, &s)

	for i := 0; i < n; i++ {
		if s[i] == 'R' {
			a[i][2] = 1
		} else {
			a[i][2] = -1
		}
	}
	sort.Slice(a, func(i, j int) bool { return a[i][1] < a[j][1] })

	y := -1
	var min, max []int
	minset := false
	maxset := false
	for i := 0; i < n; i++ {
		if a[i][1] != y {
			y = a[i][1]
			minset = false
			maxset = false
		}
		if a[i][2] == 1 {
			if !minset {
				minset = true
				min = a[i]
			} else if min[0] > a[i][0] {
				min = a[i]
			}
		} else {
			if !maxset {
				maxset = true
				max = a[i]
			} else if max[0] < a[i][0] {
				max = a[i]
			}
		}
		if minset && maxset && min[0] < max[0] {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
}

```

# D - Moves on Binary Tree
[D - Moves on Binary Tree](https://atcoder.jp/contests/abc243/tasks/abc243_d)
文字列の指示に従って数字のついた二分木の頂点を移動する問題です。頂点数は2のグーゴル乗($10^{100}$)なので一瞬ビビりますが上限に意味はないです。
これ、グラフの問題ではなくただ指示に従って数字を操作するだけの問題でした。
以下の三つの指示が文字列で与えられます。

* 'U' : 親のノードに行く。-> 2で割る
* 'L' : 左の子ノードに行く。-> 2をかける 
* 'R' : 右の子ノードに行く。-> 2をかけて1を足す。

ここで問題となるのが、途中でオーバーフローとなってしまうことです。
そこで'L'や'R'の後に'U'が来た場合を考えました。
もし'LU'が来た場合には子ノードに移動した後親ノードに移動することになるので元のノードに戻ることになります。'RU'も同様に元のノードに戻るので、'U'の前に来る'L'と'R'を消去していいことになり、与えられる指示"UUU...U[LとRの列]"にすることができます。

```golang
package main

import (
	"fmt"
)

func reverse(chs []byte) []byte {
	l := len(chs)
	new_chs := make([]byte, l)
	for i := 0; i < l; i++ {
		new_chs[i] = chs[l-i-1]
	}
	return new_chs
}

func main() {
	var n, x int64
	var s string
	fmt.Scan(&n, &x, &s)
	var ch []byte
	ch = make([]byte, 0)
	// buf = make([]byte, 0)
	count := 0
	for i := len(s); i > 0; i-- {
		c := s[i-1]
		if c == 'U' {
			count++
		} else {
			if count == 0 {
				ch = append(ch, c)
			} else {
				count--
			}
		}
	}
	for i := 0; i < count; i++ {
		x = x / 2
	}
	ch = reverse(ch)
	for _, c := range ch {
		if c == 'L' {
			x *= 2
		} else {
			x = x*2 + 1
		}
	}
	fmt.Println(x)
}

```

# E - Edge Deletion
[E - Edge Deletion](https://atcoder.jp/contests/abc243/tasks/abc243_e)
これは時間内に解けなかったため解説を見た問題です。
要約すると単純連結無向グラフからできるだけ多くの辺を取り除く問題です。
これは、ワーシャルフロイド法によって各頂点間の最短距離を求めたのちに、それぞれの辺について同じ距離の迂回路が存在するか判定することで取り除いて良い辺かを確認することでクリアできます。

```golang
package main

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

type Edge struct {
	s int
	e int
	c int
}

func main() {
	var n, m int
	r := bufio.NewReader(os.Stdin)
	fmt.Fscan(r, &n, &m)

	edges := make([]Edge, m)

	dp := make([][]int, n)
	for j := 0; j < n; j++ {
		dp[j] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		var a, b, c int
		fmt.Fscan(r, &a, &b, &c)
		dp[a-1][b-1] = c
		dp[b-1][a-1] = c
		if a < b {
			edges[i] = Edge{s: a - 1, e: b - 1, c: c}
		} else {
			edges[i] = Edge{s: b - 1, e: a - 1, c: c}
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			for k := 0; k < n; k++ {
				if dp[j][i] == 0 || dp[i][k] == 0 {
					continue
				}
				if dp[j][k] == 0 || dp[j][k] > dp[j][i]+dp[i][k] {
					dp[j][k] = dp[j][i] + dp[i][k]
				}
			}
		}
	}
	count := 0
	for _, edge := range edges {
		c := edge.c
		for i := 0; i < n; i++ {
			if dp[edge.s][i]+dp[i][edge.e] <= c {
				count++
				break
			}
		}
	}
	fmt.Println(count)
}

```

# F - Lottery
[F - Lottery](https://atcoder.jp/contests/abc243/tasks/abc243_f)
これは確率を求める問題ですが、剰余における逆元を求めることで答えを整数で出力するというものです。

## 逆元について
適当な整数$x$の逆元$x^{-1}$は素数を$p$とするとフェルマーの小定理より

$$
x^{p-1}\equiv 1 \quad (mod\hspace{2pt}p)
$$

なので

$$
x^{-1}=x^{p-2}
$$

今回の答えは分母の逆元と分子の積で表せば良いことになります。これの面白いところとして約分する前と後でこの値は同じになるという性質があります。そのため計算途中でmodをとっても良いことになります。ただ実装の際に面倒になりそうだったのでmodをとりながら計算する関数を別で実装しました。

```golang
const mod int64 = 998244353

// 足し算
func add(a, b int64) int64 {
	return (a + b) % mod
}
// 引き算
func sub(a, b int64) int64 {
	x := (a - b) % mod
	if x < 0 {
		return x + mod
	} else {
		return x
	}
}
// 掛け算
func mul(a, b int64) int64 {
	return (a * b) % mod
}
// 割り算
func dev(a, b int64) int64 {
	return mul(a, inverse(b))
}
// 累乗
func qpow(a, n int64) int64 {
	var r int64 = 1
	if n == 1 {
		return a
	}
	if n%2 == 1 {
		r = a
	}
	return mul(r, qpow(mul(a, a), n/2))
}
// 逆元
func inverse(a int64) int64 {
	return qpow(a, mod-2)
}
// 階乗
func fac(n int64) int64 {
	if n == 1 {
		return 1
	}
	return mul(n, fac(n-1))
}
```

問題の解決はdpによって行いました。計算の方向は解説とは異なり集約する形で実装しました。

$$
DP[i][j][k] = DP[i-1][j][k] +\sum_{l=1}^{k}DP[i-1][j-1][k-l]\times \frac{p[i-1]}{l!}
$$

```golang

func main() {
	var k, m, n int64
	var sum int64 = 0
	var i, j, l, o int64
	fmt.Scan(&n, &m, &k)
	w := make([]int64, n)
	for i = 0; i < n; i++ {
		fmt.Scan(&w[i])
		sum = add(sum, w[i])
	}
	i_sum := inverse(sum)
	for i = 0; i < n; i++ {
		// 剰余内での確率をとる
		w[i] = mul(i_sum, w[i])
	}

	dp := make([][][]int64, n+1)
	for i = 0; i < n+1; i++ {
		dp[i] = make([][]int64, m+1)
		for j = 0; j < m+1; j++ {
			dp[i][j] = make([]int64, k+1)
		}
	}
	// 初期化
	dp[0][0][0] = 1
	for i = 1; i <= n; i++ {
		for j = 0; j <= m; j++ {
			for l = 0; l <= k; l++ {
				// i - 1種類の中からl個取り出してj種類だった時を足す
				dp[i][j][l] = dp[i-1][j][l]
				if j == 0 {
					continue
				}
				for o = 1; l-o >= 0; o++ {
					dp[i][j][l] = add(dp[i][j][l], mul(dp[i-1][j-1][l-o], dev(qpow(w[i-1], o), fac(o))))
				}
			}
		}
	}
	ans := mul(dp[n][m][k], fac(k))

	fmt.Println(ans)
}
```

# 終わり
　今の実力だと時間内に問題に触れたのはここまででした。Gについてもまとめ次第上げて行きます。