みなさんこんにちは、ほむほむです。
今回はAtCoder Beginner Contest 167の問題A～問題Dまでの復習投稿です。
【問題A】
文字列S,Tを入力して、ルールに基づいているかという問題です。
ルールは、Sの末尾に１文字追加することで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) // 町１からの距離
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)
}