みなさんこんにちは、ほむほむです。
今回はAtCoder Beginner Contest 171の問題A～問題Dまでの復習投稿です。
【問題A】
文字αが与えられ、英大文字ならば ‘A’ 、英小文字ならば ‘a’ と出力する問題です。
言語によっては、islower()関数などが用意されていることがほとんどですが、関数を用いずベーシックに求めることもできます。
その場合、A, B, C, … , Z の文字コードが 65, 66, 67, … , 90 、a, b, c, … , z の文字コードが 97, 98, 99, … , 122 と連番になっていることを知っていれば解くことができます。
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
a := getStdin()
if 'a' <= a[0] && a[0] <= 'z' {
fmt.Printf("a\n")
} else {
fmt.Printf("A\n")
}
}
var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*1)
func getStdin() string {
return readLine()
}
func readLine() string {
buf := make([]byte, 0, 0)
for {
l, p, _ := sc.ReadLine()
buf = append(buf, l...)
if !p {
break
}
}
return string(buf)
}
【問題B】
果物 1, 2, … , N がそれぞれ p(1), p(2), … , p(N) 円で売られています。K種類の果物を一個ずつ買うとき、それらの合計価格として考えられる最小の金額を求めよ、という問題です。
シンプルに K種類を選び出す組み合わせを列挙していくと実行時間が間に合いません。そこで、価格の配列を昇順でソートし、そこからK個持ってきて足し合わせることにより、結果として最小の金額になります。
package main
import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
"strings"
)
func main() {
_, K := getStdinInt2()
p := getStdinIntArr()
sort.Ints(p)
sum := 0
for i := 0; i < K; i++ {
sum += p[i]
}
fmt.Printf("%d\n", sum)
}
var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)
func getStdin() string {
return readLine()
}
func getStdinInt2() (int, int) {
list := getStdinIntArr()
return list[0], list[1]
}
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】
1～10^15+1まで番号が振られた犬に名前をつけます。
1, 2, … , 26 : a, b, … , z
27, 28, … , 702 : aa, ab, … , zz
703, 704, … , 18278 : aaa, aab, … , zzz
のような規則でつけます。番号Nの犬の名前を答えよ、という問題です。
命名規則が a～z で表現された 26進数として扱うことがファーストインプレッションです。しかし、単純に26進数では表現できません。以下に例を示します。
16進数の場合、0～9, A～Fを用います。これを a～p と置き換えてみます。
0 : a 1 : b 2 : c 3 : d 4 : e 5 : f 6 : g 7 : h 8 : i 9 : j 10 : k
11 : l 12 : m 13 : n 14 : o 15 : p 16 : ba 17 : bb
このとき、16に着目すると aa になってほしいところが ba になってしまいます。（ 0x10 で 1 : b , 0 : a のため）
すなわち、桁が上がった場合、上がった桁を -1 する必要があります。この点を留意して実装する必要があります。
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
list := getStdinIntArr64()
N := list[0]
var base int64 = 'z' - 'a' + 1
n := N - 1
str := ""
for {
mod := n % base
str2 := fmt.Sprintf("%c", 'a'+mod)
str = str2 + str
n /= base
if n == 0 {
break
}
n--
}
fmt.Printf("%s\n", str)
}
var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)
func getStdin() string {
return readLine()
}
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)
}
【問題D】
正整数 A(1), A(2), … , A(N)からなる数列Aが与えられます。
「i回目の操作では、値がB(i)である要素全てをC(i)に置き換える」という操作をQ回行うとき、i回目の操作が行われたあとの数列Aの全ての要素の和、S(i)を求める、という問題です。
シンプルに置き換えた数列Aの和を毎回求めていると実行時間が間に合いません。そのため、事前に数列Aの和を求め、操作が行われることにより変化する和のみ着目します。
具体的には、ハッシュ（map）を用意し、A(1), A(2), … , A(N)の登場する数の個数をカウントします。また、その合計値も保存しておきます。
値B(i)からC(i)へ変化するとき、ハッシュからB(i)にあたる個数を取り出し、合計から減算します。そして合計へC(i)×[B(i)の個数]を加算します。その後、ハッシュからB(i)の値の個数は0へ、C(i)の値の個数を新たに登録します。
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
list1 := getStdinIntArr64()
N := list1[0]
A := getStdinIntArr64()
list2 := getStdinIntArr64()
Q := list2[0]
AMap := make(map[int64]int64, N+Q)
var ASum int64 = 0
for _, val := range A {
AMap[val]++
ASum += val
}
var i int64 = 0
sumlist := make([]int64, 0)
for ; i < Q; i++ {
list3 := getStdinIntArr64()
B := list3[0]
C := list3[1]
sum := ASum
num := AMap[B]
sum -= num * B
sum += num * C
ASum = sum
AMap[B] = 0
AMap[C] += num
sumlist = append(sumlist, sum)
}
for i = 0; i < Q; i++ {
fmt.Printf("%d\n", sumlist[i])
}
}
var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)
func getStdin() string {
return readLine()
}
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)
}