【Go言語】AtCoder ABC167 復習(問題A~問題D)

投稿者: | 2020年7月3日

みなさんこんにちは、ほむほむです。
今回はAtCoder Beginner Contest 167の問題A~問題Dまでの復習投稿です。

【問題A】
文字列S,Tを入力して、ルールに基づいているかという問題です。
ルールは、Sの末尾に1文字追加することでTにするというもの。
長さS+1がTであるため、この問題は
「文字列Sと長さSの部分文字列Tが等しいか?」
という問題に帰ることができます。
Go言語では文字列にSliceを使用することができるため、比較部分は

if S == T[:len(S)] {
}

と表現することができます。
これを踏まえて、コードの全景を掲載します。

package main

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

func main() {
	S := getStdin() // 文字列入力
	T := getStdin() // 文字列入力

	if S == T[:len(S)] {
		fmt.Printf("Yes\n")
	} else {
		fmt.Printf("No\n")
	}
}

var sc = bufio.NewScanner(os.Stdin)

func getStdin() string {
	sc.Scan()
	return sc.Text()
}


【問題B】
後ほど説明文を掲載します。

package main

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

func main() {
	A, B, C, K := getStdinInt()

	if A >= K {
		fmt.Printf("%d\n", K)
		return
	}
	K = K - A

	if B >= K {
		fmt.Printf("%d\n", A)
		return
	}
	K = K - B

	if C >= K {
		fmt.Printf("%d\n", A-K)
		return
	}
	fmt.Printf("%d\n", A-C)
}

var sc = bufio.NewScanner(os.Stdin)

func getStdin() string {
	sc.Scan()
	return sc.Text()
}
func getStdinInt() (int, int, int, int) {
	str := getStdin()
	list := strings.Split(str, " ")
	A, _ := strconv.Atoi(list[0])
	B, _ := strconv.Atoi(list[1])
	C, _ := strconv.Atoi(list[2])
	D, _ := strconv.Atoi(list[3])
	return A, B, C, D
}


【問題C】
後ほど説明文を掲載します。

package main

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

func main() {
	list := getStdinIntArr()
	N := list[0]
	M := list[1]
	X := list[2]
	C := make([]int, N)
	A := make([][]int, N)
	for i := 0; i < N; i++ {
		A[i] = make([]int, M)
	}

	for i := 0; i < N; i++ {
		list2 := getStdinIntArr()
		C[i] = list2[0]
		for j := 0; j < M; j++ {
			A[i][j] = list2[j+1]
		}
	}

	maxBit := (1 << N) - 1
	moneyMin := math.MaxInt32
	for bit := 1; bit <= maxBit; bit++ {
		money := 0
		AC := make([]int, M)
		for i := 0; i < N; i++ {
			mask := 0
			if i == 0 {
				mask = 1
			} else {
				mask = 1 << i
			}
			if (bit & mask) != 0 {
				money += C[i]
				for n := 0; n < M; n++ {
					AC[n] += A[i][n]
				}
			}
		}
		flag := true
		for i := 0; i < M; i++ {
			if AC[i] < X {
				flag = false
				break
			}
		}
		if flag && money < moneyMin {
			moneyMin = money
		}
	}

	if moneyMin == math.MaxInt32 {
		fmt.Printf("%d\n", -1)
	} else {
		fmt.Printf("%d\n", moneyMin)
	}
}

var sc = bufio.NewScanner(os.Stdin)

func getStdin() string {
	sc.Scan()
	return sc.Text()
}
func getStdinIntArr() []int {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.Atoi(val)
	}
	return rtn
}


【問題D】
後ほど説明文を掲載します。

package main

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

func main() {
	list := getStdinIntArr64()
	N := list[0]
	K := list[1]
	A := getStdinIntArr64()
	var i int64
	var j int64

	for idx, val := range A {
		A[idx] = val - 1
	}
	Mati := make([]int64, N) // 町1からの距離
	for i = 0; i < N; i++ {
		Mati[i] = -1
	}

	// 町探索
	var prev int64 = 0
	var now int64 = 0
	for i = 0; i < K; i++ {
		prev = now
		now = A[now]
		if Mati[now] == -1 {
			Mati[now] = i
		} else {
			// ループした
			loop := Mati[prev] - Mati[now] + 1
			if loop <= 1 {
				break
			}
			var rem int64 = (K - (i + 1)) % loop
			if (K - (i + 1)) < 0 {
				rem = (K - (i + 1)) + loop%loop
			}
			for j = 0; j < rem; j++ {
				now = A[now]
			}
			break
		}
	}

	fmt.Printf("%d\n", now+1)
}

var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)

func getStdinIntArr64() []int64 {
	str := readLine()
	list := strings.Split(str, " ")
	rtn := make([]int64, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.ParseInt(val, 10, 64)
	}
	return rtn
}

func readLine() string {
	buf := make([]byte, 0, 1024*1024*10)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

コメントを残す

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください