🙆

GoでAtcoder286,287の問題を解く（貪欲法と深優先探索法）

2023/11/14に公開

AtCoder

tech

今回はGo言語でABC286,287のC問題を解いてきます。

286C問題

この問題は、与えられた文字列を回文に変換するための最小のコストを求める問題です。コストは、2つの操作を行うために支払う必要がある金額です。

操作Aは文字列の先頭から1文字を末尾に移動させるもので、操作Bは文字列の任意の位置の文字を別の英小文字に置き換えるものです。

回文の特性を利用して解を見つけることができます。回文は左から読んでも右から読んでも同じになる性質を持っています。この性質を利用すると、文字列を回文にするために必要な操作回数を最小化することができます。

package main

import "fmt"

func main() {
	var n, a, b int
	var s string
	fmt.Scan(&n, &a, &b, &s)
	s += s
	c := 0
	ans := int(1e18)
	for i := 0; i < n; i++ {
		c = 0
		for j := 0; j < n/2; j++ {
			if s[i+j] != s[n+i-1-j] {
				c++
			}
		}
		ans = min(ans, c*b+a*i)
	}
	fmt.Println(ans)
}

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

上のコードは入力として、整数 n、整数 a、整数 b、文字列 s を受け取っています
文字列 s を自身と連結させて s += s とし、文字列を2倍にします。これは、文字列を一巡する際のループ処理を簡略化するためです。
変数 c を用意し、回文に変換するための操作回数を保持します。変数 ans には最小コストを保持するための初期値を設定します（非常に大きな値を初期値として設定しています）。
外側のループでは、文字列 s の各位置を開始位置として見ていきます。
内側のループでは、各位置から中心を挟んで対応する位置にある文字同士を比較します。文字が異なる場合は、変数 c をインクリメントして操作回数をカウントします。
各位置からの操作回数と移動に必要なコストを計算し、最小コストを求めます。
最終的な最小コストを出力します。

287C問題

この問題は、与えられたグラフがパスグラフであるかどうかを判定する問題です。

パスグラフとは、頂点が1からNまでの番号が付けられたN頂点のグラフであり、頂点を1からNまでの順に辺で結んでいるが、1からNまでの番号を並べ替えて得られる数列(v1, v2, ..., vN)で以下の条件を満たすものです：

全てのi=1からN-1までに対して、頂点viとvi+1を結ぶ辺が存在する。
整数i, jが1≤i,j≤Nかつ|i-j|≥2を満たすならば、頂点viとvjを結ぶ辺は存在しない。
数学的なアプローチとしては、与えられたグラフがパスグラフであるかどうかを判定するために、次のような方法が考えられます。

グラフ上で1からNまでの順番に辺が存在しているかどうかを確認する。
各頂点について、その頂点から直接つながっている頂点を探索し、1からNまでの連続した辺が形成されているか確認する。
グラフが連続した辺で構成され、かつ上記の条件を満たしている場合、パスグラフであると判定できます。

package main

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

func dfs(edges [][]int, seen []bool, u int) {
	for _, v := range edges[u] {
		if !seen[v] {
			seen[v] = true
			dfs(edges, seen, v)
		}
	}
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var N, M, u, v int
	fmt.Fscan(in, &N, &M)
	edges := make([][]int, N, N)
	for i := 0; i < N; i++ {
		edges[i] = make([]int, 0, 0)
	}
	for i := 0; i < M; i++ {
		fmt.Fscan(in, &u, &v)
		u--
		v--
		edges[u] = append(edges[u], v)
		edges[v] = append(edges[v], u)
	}
	if M != N-1 {
		fmt.Fprintln(out, "No")
		return
	}
	for i := 0; i < N; i++ {
		if len(edges[i]) > 2 {
			fmt.Fprint(out, "No")
			return
		}
		if len(edges[i]) == 0 {
			fmt.Fprint(out, "No")
			return
		}
	}
	seen := make([]bool, N, N)
	seen[0] = true
	dfs(edges, seen, 0)
	for _, val := range seen {
		if !val {
			fmt.Fprintln(out, "No")
			return
		}
	}
	fmt.Fprintln(out, "Yes")
}

まず、入力されたN頂点とM辺を持つグラフを隣接リストの形式で表現しています。その後、以下の手順でパスグラフかどうかを判定しています。

MがN-1でない場合は、グラフがパスグラフの条件を満たさないため、「No」と出力してプログラムを終了します。
各頂点iに対して、その頂点に接続された頂点の数が2以上の場合や接続された頂点が存在しない場合は、グラフがパスグラフの条件を満たさないため、「No」と出力してプログラムを終了します。
DFS（深さ優先探索）を使用して、グラフが連結かつ連続した辺で構成されているかを確認します。DFSでは、最初の頂点から始めて、その頂点に接続されたすべての頂点を訪れます。すべての頂点を訪れた後、すべての頂点が訪れられているかを確認します。訪れていない頂点が存在する場合は、「No」と出力します。
上記の条件をすべて満たしていれば、「Yes」と出力します。

286C問題

287C問題

Discussion