みなさんこんにちは、ほむほむです。
今回はAtCoder Beginner Contest 172の問題A～問題Dまでの復習投稿です。
【問題A】
整数aが入力され、値 a + a^2 + a^3 を出力する問題です。
シンプルに a を入力し、
a + a*a + a*a*a
を出力します。
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func main() {
a := getStdinInt()
fmt.Printf("%d\n", a+a*a+a*a*a)
}
var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*1)
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】
文字列S, Tが与えられ、「Sの1文字を選んで別の文字に書き換える」操作を繰り返し、SをTに変更するときの最小回数を求める問題です。
この問題は、Sの1文字とTの1文字が等しいときには書き換える必要がなく、異なる場合にのみ、Sの1文字をTの1文字に書き換えるというものです。すなわち、文字列Sと文字列Tは何文字異なるか？という問題に読み替えることができます。
そのため、Sの1文字とTの1文字を比較した合計が答えになります。比較は下記のように行います。
S[i] != T[i]
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
S := getStdin()
T := getStdin()
ans := 0
for i := 0; i < len(T); i++ {
if S[i] != T[i] {
ans++
}
}
fmt.Printf("%d\n", ans)
}
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)
}
【問題C】
２つの机A, Bがあり、机AにはN冊の本が、机BにはM冊の本が、それぞれ積まれています。机Aの上からi番目の読む速度はA(i)分、机Bの上からi番目の読む速度はB(i)分かかります。本が残っている机から最も上に積まれている本を読んで取り除くとき、合計所要時間がK分を超えないようにする最大の読める本の冊数を求めよ、という問題です。
シンプルに机Aと机Bの一番上に積まれている本の所要時間を比較し、小さい方を選んでいくと、この問題は失敗します。次が一例です。
A : 10, 20, 30, 40, 50
B : 60, 10, 10, 10, 10
K : 90
この場合、上記の方法でピックアップすると
10, 20, 30 < K
の３冊になりますが、実際の答えは
60, 10, 10, 10 <= K
の４冊になります。
机Bに着目すると、60のあとに10が連続するため、１冊さえ読んでしまえばあとは短時間で本を読むことができるというロジックです。
つまり、机Aからn冊読んだときに、机Bからm冊読むことができる、という結果を 0 <= n <= N まで繰り返し、その中から最大の本の数が答えになります。
これを上の例で考えると、
n=0のとき、A : 0 + B : 60, 10, 10, 10（★）
n=1のとき、A : 10 + B : 60, 10, 10（★）
n=2のとき、A : 10, 20 + B : 60
n=3のとき、A : 10, 20, 30 + B : 0
n=4のとき、A : 10, 20, 30 + B : 0
n=5のとき、A : 10, 20, 30 + B : 0
が全てのパターンになり、★の部分が最大になります。
ここで、nが決まったときに、mを求めるために一工夫が必要になります。（実行時間が間に合いません）
C++に用意されているupper_boundテンプレートを使用します。これは、二分探索を行い、指定された値よりも大きい最小のインデックスを返すテンプレートです。二分探索のオーダーはO(log_2 n)であるため、十分間に合いそうです。
二分探索を簡単に述べると次の手順を踏むアルゴリズムです。
１．Left=0, Right=配列のサイズ-1 に設定
２．Mid=LeftとRightの中央値を代入
３．配列のMidの場所と指定された値を比較し、Midが指定された値より
大きい場合 Left=Mid+1 、そうでない場合 Right = Mid – 1 に設定
４．Right < Leftならば、Leftがupper_boundの求める値、そうでない場合
２．へ移行
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
// 二分探索で目的の値より大きいインデックスを返す
func upperBound(list []int64, n int64) int64 {
var l int64 = 0
var r int64 = int64(len(list) - 1)
for l <= r {
var mid int64 = l + (r-l)/2
if list[mid] <= n {
l = mid + 1
} else {
r = mid - 1
}
}
return l
}
func main() {
list := getStdinIntArr64()
N := list[0]
M := list[1]
K := list[2]
A := getStdinIntArr64()
B := getStdinIntArr64()
Asum := make([]int64, N+1)
Bsum := make([]int64, M+1)
var i int64 = 0
var ans int64 = 0
for i = 0; i < N; i++ {
Asum[i+1] = Asum[i] + A[i]
}
for i = 0; i < M; i++ {
Bsum[i+1] = Bsum[i] + B[i]
}
var apos int64 = 0
for ; apos <= N; apos++ {
if Asum[apos] > K {
break
}
if M > 0 {
var bpos int64 = upperBound(Bsum, K-Asum[apos])
if bpos != 0 {
bpos--
}
if apos+bpos > ans {
ans = apos + bpos
}
}
}
fmt.Printf("%d\n", ans)
}
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】
正整数Xに対して、Xの正の約数の個数をf(X)とします。
正整数Nが与えられ、1×f(1) + 2×f(2) + … + N × f(N) を求めよ、という問題です。
ここで、シンプルに実装すると明らかに実行時間が間に合いません。
そのため、約数の個数を求めるハックを行います。約数の性質をみるために、いくつか約数を挙げてみます。
1 : 1
2 : 1, 2
3 : 1, 3
4 : 1, 2, 4
5 : 1, 5
6 : 1, 2, 3, 6
7 : 1, 7
8 : 1, 2, 4, 8
9 : 1, 3, 9
10 : 1, 2, 5, 10
11 : 1, 11
12 : 1, 2, 3, 4, 6, 12
ここで見てとれるのが、１は１の倍数の数の約数になっており、２は２の倍数の数の約数になっており、３は３の倍数の数の約数になっています。
この事実から、１～Nまでの約数の数を保存する配列を用意し、1, 2, 3, … とシークしながら、倍数を +1 していくことにより、各約数の個数が配列に入ります。
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
list := getStdinIntArr64()
N := uint64(list[0])
divitors := make([]uint64, N+1)
var i uint64 = 0
var j uint64 = 0
for i = 1; i <= N; i++ {
for j = i; j <= N; j += i {
divitors[j]++
}
}
var k uint64 = 1
var ans uint64 = 0
for ; k <= N; k++ {
ans += k * divitors[k]
}
fmt.Printf("%d\n", ans)
}
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)
}