【Project Euler】#008

8問目です！

問題

$1000$桁の数において、連続する4桁の数字の積が最大となるのは、$9 × 9 × 8 × 9 = 5832$です。

7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

この$1000$桁の数字の中で、連続する$13$桁の数字の積が最大になるのはどれかを求め、その積の値を答えてください。

他媒体でも見かけるような問題ですね。

純粋に1文字ずつスライドさせるのがいいんですかね。
（0が入ってたら問答無用でスキップとかしたい）

わたしの回答

func solve() {
	target := "..." // 省略

	resultSum := 0

	for i := 0; i < len(target)-12; i++ {
		// 現在の13桁の積を取得
		currentResult := getThirteenDigitProduct(target[i : i+13])
		if resultSum < currentResult {
			resultSum = currentResult
		}
	}
	fmt.Println(resultSum)
}

// 13桁の積を取得(対象の数字は文字列で受け取る)
func getThirteenDigitProduct(target string) int {
	result := 1
	for i := 0; i < len(target); i++ {
		num, _ := strconv.Atoi(target[i : i+1])
		result *= num
	}
	return result
}

13桁の数字分、先頭から試していく方法です。

1. getThirteenDigitProductで$7316717653133$を受け取って、1~13桁の数字の積を算出する。
2. getThirteenDigitProductで$3167176531330$を受け取って、1~13桁の数字の積を算出する。
3. 全パターン試す...。

という感じです。そこまで捻ってない。

GPT-4.1の回答

func solve() {
	num := strings.ReplaceAll(`
... // 省略
`, "\n", "")

	maxProduct := 0
	length := 13

	for i := 0; i <= len(num)-length; i++ {
		product := 1
		for j := 0; j < length; j++ {
			digit := int(num[i+j] - '0')
			product *= digit
		}
		if product > maxProduct {
			maxProduct = product
		}
	}

	fmt.Println("最大の積は:", maxProduct)
}

うーん、文字列→数字変換をstrconv.AtoIでやってたんですが、
int(num[i] - '0')でやってるところが1番速度に差が出てそうですね。
（ベンチマーク、後で記載あります。）

必ず「1文字の数字」が保証されている今回のようなケースだとこういう方法がよさそうですね。

Gemini2.5 Flashの回答

func solve() {
	number := "..." // 省略
	windowSize := 13
	maxProduct := int64(0)

	// 連続する13桁の塊をスライドさせながら積を計算
	for i := 0; i <= len(number)-windowSize; i++ {
		currentProduct := int64(1)
		// 現在の13桁の積を計算
		for j := 0; j < windowSize; j++ {
			digit, err := strconv.Atoi(string(number[i+j]))
			if err != nil {
				fmt.Println("数字への変換エラー:", err)
				return
			}
			currentProduct *= int64(digit)
		}

		// 最大積を更新
		if currentProduct > maxProduct {
			maxProduct = currentProduct
		}
	}

	fmt.Printf("1000桁の数字の中で連続する%d桁の数字の積の最大値は %d です。\n", windowSize, maxProduct)
}

ベンチマーク

今回からベンチマークの測定をしてみました。
Geiminiには圧勝ですね🦖

計測	実行回数 (b.N)	平均実行時間 (ns/op)
わたしの回答	28,819	44,913
GPT4.1	125,053	9,646
Gemini2.5	15,373	80,804

感想

文字列→数字の変換でここまで差が出ると思ってませんでした。
確かに、（APIのバリデーションレイヤー等で）きちんと1文字の数字が担保できているのであれば、GPT4.1のように「部分文字列を作らず、バイト演算で直接数値化」するのがありですね。