【Go言語】AtCoder ABC170 復習(問題A～問題D)

投稿者: | 2020年7月3日
1件のコメント

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

【問題A】
x(1), x(2), x(3), x(4), x(5)が与えられ、これらの中から0を代入します。0を代入した変数はどれか、という問題です。

シンプルに、x(1)～x(5)を比較し、値が0であるもののインデックスを返せば正解です。注意点としては、配列は0スタートであるため、答えとして+1する必要があります。

package main

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

func main() {
	list := getStdinIntArr()
	for idx, val := range list {
		if val == 0 {
			fmt.Printf("%d\n", idx+1)
		}
	}
}

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

func getStdin() string {
	return readLine()
}
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
}
func readLine() string {
	buf := make([]byte, 0, 0)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}


【問題B】
庭に何匹かの動物がいます。2本の足をもつ鶴か4本の足を持つ亀のいずれかです。「庭の動物の総数はX匹で、それらの足の総数はY本である」という条件が成立するか求めよ、という問題です。

これは俗に鶴亀算と呼ばれるものですが、ここでは連立方程式を解くことを考えます。
鶴の総数をn、亀の総数をmとしたときに、次の2式を導くことができます。
$$ n + m = X \\
2n + 4m = Y $$
この連立方程式を解くと、
$$ m = (Y – 2X) / 2 \\
n = -(Y-2X) / 2 $$
となります。ここで、(Y – 2X)は整数ですから、(Y – 2X) % 2 == 0が成立することが題意を満たす条件となります。
整数であることがわかり、m+n=Xを満たす場合、条件を満たすことになります。ここで、m, nは正整数であることに注意してください。

package main

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

func main() {
	list := getStdinIntArr()
	A := list[0]
	B := list[1]

	y := B - 2*A

	if y%2 == 0 {
		y = y / 2
		x := A - y
		if x+y == A && x >= 0 && y >= 0 {
			fmt.Printf("Yes\n")
			return
		}
	}
	fmt.Printf("No\n")
}

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

func getStdin() string {
	return readLine()
}
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
}
func readLine() string {
	buf := make([]byte, 0, 0)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}


【問題C】
整数Xと、長さNの整数列 p(1), p(2), … , p(N) が与えられます。整数列 p(1), … , p(N) に含まれない整数のうちXに最も近いものを求めてください。そのような整数が複数存在する場合には、そのうち最も小さいものを答えてください、という問題です。

Xに最も近いものを求めるために、下準備として整数列 p(1), … , p(N) を昇順にソートします。このうち下記の例のような数値を見つけます。
　例１）X = 4、p = 1, 3, 5, 7, 9 の場合、4は整数列pに含まれないため、
　　　　4が答えになります。
　例２）X = 5、p = 1, 3, 5, 7, 9 の場合、5は整数列pに含まれるため、
　　　　その前後が答えになります。ここで、整数列に含まれない例として
　　　　p’ = 0, 2, 4, 6, 8, 10 となるため、5に近い数は4, 6になります。
　　　　問題から、答えは4になります。
　例３）X = 5、p = 1, 2, 3, 4, 5, 6, 7 の場合、5は整数列pに含まれるため、
　　　　その前後が答えになります。ここで、整数列に含まれない例として
　　　　p’ = 0, 8 となるため、5に近い数は8になります。
これらの例を踏まえて、①Xがpに含まれない、②pに含まれず、Xより小さい数のうち最大の数と比較、③pに含まれず、Xより大きい数のうち最小の数と比較、することにより答えを求めることができます。

package main

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

func main() {
	list1 := getStdinIntArr()
	p := getStdinIntArr()
	X := list1[0]
	N := list1[1]

	sort.Ints(p)

	find := true
	index := 0
	for idx, val := range p {
		if val == X {
			find = false
			index = idx
			break
		}
	}
	if find {
		fmt.Printf("%d\n", X)
		return
	}

	prev := 0
	min1 := -math.MaxInt16
	min2 := math.MaxInt16

	prev = p[index]
	find = false
	for i := index - 1; i >= 0; i-- {
		if prev-1 != p[i] {
			min1 = prev - 1
			find = true
			break
		}
		prev = p[i]
	}
	if !find {
		min1 = p[0] - 1
	}

	prev = p[index]
	find = false
	for i := index + 1; i < N; i++ {
		if prev+1 != p[i] {
			min2 = prev + 1
			find = true
			break
		}
		prev = p[i]
	}
	if !find {
		min2 = p[N-1] + 1
	}

	if min1 == -math.MinInt16 {
		fmt.Printf("%d\n", min2)
		return
	}
	if min2 == math.MinInt16 {
		fmt.Printf("%d\n", min1)
		return
	}

	min1abs := X - min1
	min2abs := min2 - X
	if min1 < 0 {
		min1abs = -min1
	}
	if min2 < 0 {
		min2abs = -min2
	}

	if min1abs == min2abs {
		fmt.Printf("%d\n", min1)
	} else if min1abs < min2abs {
		fmt.Printf("%d\n", min1)
	} else {
		fmt.Printf("%d\n", min2)
	}
}

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

func getStdin() string {
	return readLine()
}
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
}
func readLine() string {
	buf := make([]byte, 0, 0)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}


【問題D】
長さNの数列Aが与えられます。次の性質を満たす整数 i（1 ≦ i ≦ N）の数を答えてください。
　・i≠j である任意の整数 j (1 ≦ j ≦ N) についてA(i)はA(j)で割り切れない

数列Aの各値の個数をmapに保存します。このとき、次は即時に答えがわかります。
　・1の数が1個の場合、条件成立は任意の整数 i ( i ≠ 1 ) , j ( j = 1 )のとき
　　全て割り切れ、i ( i = 1 ) , 任意の整数 j ( j ≠ 1 )のとき条件が成立するため、
　　答えは1
　・1の数が2個以上の場合、任意の整数 i , j ( j = 1 )のとき条件が成立しない
　　ため、答えは0

それ以外に関しては、数列Aの値をループして判定します。
このとき、A(i)の約数を求め、事前に保存していたmapに存在する場合には、その数で割り切れることができることに注意し、数え上げを行います。

package main

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

func main() {
	N := getStdinInt64()
	A := getStdinIntArr64()
	var i int64 = 0
	var max int64 = 0

	// 最大値を求める
	for i = 0; i < N; i++ {
		if A[i] > max {
			max = A[i]
		}
	}

	// 素数を求める
	isPrime := make([]bool, max+1)
	for i := 2; i < len(isPrime); i++ {
		isPrime[i] = true
	}
	isPrime[0] = false
	isPrime[1] = false
	for i := 2; i < len(isPrime); i++ {
		if isPrime[i] {
			for j := i * 2; j < len(isPrime); j += i {
				isPrime[j] = false
			}
		}
	}

	// 個数
	countMap := make(map[int64]int64)
	for _, a := range A {
		countMap[a]++
	}

	// 1が1個、または1が2個以上の場合
	if countMap[1] == 1 {
		// x % 1 == 0のみ
		fmt.Printf("%d\n", 1)
		return
	}
	if countMap[1] >= 2 {
		// 全てが x % 1 == 0 になってしまう
		fmt.Printf("%d\n", 0)
		return
	}

	var ans int64 = 0
	for _, a := range A {
		if countMap[a] >= 2 {
			// x % x == 0 になってしまう
			continue
		}
		if isPrime[a] {
			// 素数なので明らか
			ans++
			continue
		}

		// 約数を求める
		fac := make([]int64, 0)
		for i = 2; i*i <= a; i++ {
			if a%i == 0 {
				fac = append(fac, i) // 因数
				if i*i != a {
					fac = append(fac, a/i) // 因数で割ったもの
				}
			}
		}

		flag := true
		for _, f := range fac {
			if countMap[f] >= 1 {
				flag = false
				break
			}
		}
		if flag {
			ans++
		}
	}

	fmt.Printf("%d\n", ans)
}

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

func getStdin() string {
	return readLine()
}
func getStdinInt64() int64 {
	str := getStdin()
	rtn, _ := strconv.ParseInt(str, 10, 64)
	return rtn
}
func getStdinIntArr64() []int64 {
	str := getStdin()
	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, 0)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

「【Go言語】AtCoder ABC170 復習(問題A～問題D)」への1件のフィードバック

  1. 梅さん

    実行して頂きありがとうございます。今はまだJavaScriptとGo言語をprogateで学習中で、なるべく早く、この２言語で仕事をするつもりです。

    返信 ↓

コメントを残す

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

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