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

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

【問題A】
与えられた金額に対して、最小の1,000円札のみで支払ったときのお釣り計算の問題です。

方針としては、剰余を使用して場合分けします。
与えられた金額Nが1,000で割り切れる、すなわちN%1000==0の場合、お釣りがないため、この場合はお釣り0になります。

そうでない場合、N%1000を求めます。これは1,000円で払った場合の割り切れない金額(1～999）になるため、1000 – (N%1000)とすることによりお釣りを求めることができます。

package main

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

func main() {
	N := getStdinInt()
	if N%1000 == 0 {
		fmt.Printf("%d\n", 0)
	} else {
		fmt.Printf("%d\n", 1000-(N%1000))
	}
}

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

func getStdin() string {
	return readLine()
}
func getStdinInt() int {
	str := getStdin()
	rtn, _ := strconv.Atoi(str)
	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】
N個の文字列sが入力され、sの内容によってAC, WA, TLE, REの数を数えるという問題です。

素直に変数AC, WA, TLE, REを用意し、sが “AC” の場合 AC++、sが “WA” の場合 WA++とし数え上げ、結果を表示します。

package main

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

func main() {
	N := getStdinInt()
	AC := 0
	WA := 0
	TLE := 0
	RE := 0
	for i := 0; i < N; i++ {
		s := getStdin()
		if s == "AC" {
			AC++
		} else if s == "WA" {
			WA++
		} else if s == "TLE" {
			TLE++
		} else if s == "RE" {
			RE++
		}
	}
	fmt.Printf("AC x %d\n", AC)
	fmt.Printf("WA x %d\n", WA)
	fmt.Printf("TLE x %d\n", TLE)
	fmt.Printf("RE x %d\n", RE)
}

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

func getStdin() string {
	return readLine()
}
func getStdinInt() int {
	str := getStdin()
	rtn, _ := strconv.Atoi(str)
	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】
H行W列に白のマス、黒のマスが存在します。このとき行をいくつか選び（0行でもよい）、列をいくつか選び（0列でもよい）、選ばれた行と列を赤く塗りつぶします。正整数Kが与えられたとき、上記の操作を行ったあとに残る黒のマスがKと等しい行と列の選び方は何通りか、という問題です。
制限が、1 <= H, W <= 6 なので、黒の数え上げはシンプルな２重ループで十分間に合いそうです。

また、行と列の選び方の全パターンを出すために、bit全探索という手法を使います。bit全探索とは、「選択している」「選択していない」をそれぞれ1, 0と置き換え、２進数で判定を行うというものです。

例えば３列の選び方のパターンを考えます。（1が選ばれている、0が選ばれていないと考える）
左が10進数、右が2進数として
　0 : 000
　1 : 001
　2 : 010
　3 : 011
　4 : 100
　5 : 101
　6 : 110
　7 : 111
とすると、３列の選び方全パターンを洗い出すことができます。
現在シークしている列xと選択の仕方Xとするときに、
　(1 << x) & X != 0
と条件を設定すれば、trueのときは赤く塗られていることがわかります。

package main

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

func main() {
	H, W, K := getStdinInt3()
	C := make([][]string, H)

	for i := 0; i < H; i++ {
		C[i] = make([]string, W)
		c := getStdin()
		for j := 0; j < len(c); j++ {
			C[i][j] = string(c[j])
		}
	}

	ans := 0
	for y := 0; y < (1<<H)-1; y++ {
		for x := 0; x < (1<<W)-1; x++ {
			sum := 0
			for n := 0; n < H; n++ {
				if ((1 << n) & y) != 0 {
					continue
				}
				for m := 0; m < W; m++ {
					if ((1 << m) & x) != 0 {
						continue
					}
					if C[n][m] == "#" {
						sum++
					}
				}
			}
			if sum == K {
				ans++
			}
		}
	}
	fmt.Printf("%d\n", ans)
}

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

func getStdin() string {
	return readLine()
}
func getStdinInt3() (int, int, int) {
	list := getStdinIntArr()
	return list[0], list[1], list[2]
}
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)というフレンドリーさが割り当てられています。別の場所へ移動することを考え、順不同に一人ずつ移動を行います。このとき、円になるように割り込みます。到着した人の「時計回りで最も近い人」「反時計回りで最も近い人」のフレンドリーさのうち小さい方に等しい心地よさを感じます。移動の順番、割り込む箇所を適切にしたときの最大の心地よさはいくつか、という問題です。

この問題での厳密な証明は避け、ある程度のパターンを考え、法則性を見つけることによりそれを正しいと予想するに留めます。

まず移動の順番について考えます。
ここで、「フレンドリーさが大きい人順に移動する」「フレンドリーさが小さい人順に移動する」の２つの極端なケースを考えます。
4, 3, 2, 1の場合、0→4→3→3の順番の心地よさになり、合計10になります。
1, 2, 3, 4の場合、0→1→1→2の順番の心地よさになり、合計4になります。
よって、移動順番はフレンドリーさが大きい人順に移動するのが最大になると予想できます。

次に心地よさの遷移について考えます。
　9, 8, 7, 6, 5 , 4, 3, 2, 1　：　0→9→8→8→7→7→6→6→5
　9, 9, 7, 6, 5, 4, 3, 2, 1　：　0→9→9→9→7→7→6→6→5
　9, 8, 7, 7, 5, 4, 3, 2, 1　：　0→9→8→8→7→7→7→7→5
　・・・
このように列挙していくと次のような法則性があることに気づきます。
　a, b, c, d, e, f, g, h, i　：　0→a→b→b→c→c→d→d→e
冒頭のaは１つ、以後２つずつ心地よさが出現します。

以上２つの事実を元にプログラムしたものが下記になります。

package main

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

func main() {
	N := getStdinInt64()
	A := getStdinIntArr64()
	Apush := make([]int64, 0)

	var i int64 = 0
	var ans int64 = 0

	sort.Slice(A, func(i, j int) bool { return A[i] > A[j] })
	Apush = append(Apush, A[0])
	for i = 1; i < N; i++ {
		Apush = append(Apush, A[i])
		Apush = append(Apush, A[i])
	}
	for i = 0; i < N-1; i++ {
		ans += Apush[i]
	}

	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)
}

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル