05/22 AtCoderBeginnerContestのB問題がTLEとなってしまう件について。

Question

お世話になります。

昨日も当該の問題について質問させていただいたGo言語初心者です。

昨日のAtCoderBeginnerContestのB問題について、いただいた回答を元に修正したのですがアルゴリズムは合っているものの、TLEとなってしまいます。原因をご教示いただけますと幸いです。今まで計算量について考えたことがなく、これを機にこちらを読んだのですが、「自分の回答は繰り返し処理を3回行っており、文字列の長さをNとするとオーダはN^3である。」という認識でいます。(自信ありません。)計算量についての基本的な考えなどについてもご指摘いただけましたら幸いです。

問題はこちらをご覧ください。方針としては下記です。

１、reverseで配列を逆順にする。
２、changeで配列の中身を変更する(９を６、６を９に)
３、joinで配列の中身を文字列として結合する。

よろしくお願いいたします。

ご参考
https://play.golang.org/p/QdIX-xJk66o

package main

import (
	"fmt"
	"strings"
)

func main() {
	var a string = "0601889"
	var ans string
	//fmt.Scan(&a)
	str := strings.Split(a, "")
	reverse(str)
	change(str)
	fmt.Println(join(str, ans))

}

func reverse(a []string) {
	for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
		a[i], a[j] = a[j], a[i]
	}
}

func change(st []string) []string {
	for index, value := range st {
		if value == "6" {
			st[index] = "9"
		}
		if value == "9" {
			st[index] = "6"
		}
	}
	return st
}

func join(str []string, ans string) string {
	for _, v := range str {
		ans += v
	}
	return ans
}

Answer 1

まず。

TLEになる原因

1,2,3の処理のうち、3の処理が非常に遅いからです。
文字列を1文字ずつ + で結合していくと、その仕組み上非常に時間とメモリを消費します。
なぜそうなるかは、「文字列結合　速度」で検索していろいろな記事を読んで理解してください。
Java言語が躍進していたころによく話題になっていたので、「Java 文字列結合　速度」で検索したほうがより具体的な解説内容のサイトにあたるかもしれません。Goでも + による文字列結合が遅くなる理由はJavaと同じです。

現実的な解決方法としては、
・配列strの末尾から1文字ずつ fmt.Printで出力する
もしくは
・文字列連結に strings.Join を使用する
のどちらかになるだろうと思います。後者の方が速度的には速いです。

計算量の話

計算量についてはここで概説するにも非常に長くなるので、AtCoderの記事を読んだうえで、アルゴリズムに関する書籍を読んだ方が良いかと思います。一般の書店にはあまりおいていないかもしれません。ある程度大きい図書館に行けば何冊かはあると思います。

質問文の処理では
1,2まではO(N)
3はO(N^2)　（正確には O(N*(1+N)/2)くらいだがN^2が半分になっても実質N^2）

です。ループを3回行ったからO(N^3)になるわけではありません。線形に3回行ったらO(3N) = O(N)です。
ループが2重になるとO(N^2)になります。回数ではなく何重になるかで決まります。

AtCoderによる計算量と問題に登場するデータ量の限界の目安は以下のサイトが参考になるのではないかと思います。（ただしこれはC++の場合で、他の言語では言語によっては限界がガクっと落ちます）
https://illumination-k.dev/posts/atcoder/competitive_memo
O(N^2)での限界はデータ量が3000くらいです。この問題では10^5=100,000なので全く足りません。

計算量はあくまで目安なので、多少超過していてもACになることはあるかもしれません（が、制限時間に余裕のないアルゴリズムで書くべきではない）。AtCoderにはコードテストができますので、提出前に想定される最大値の入力を試して時間切れにならないかどうか確認しておくべきだと思います。

Comments

[Jonathan_Sf]

昨日に引き続きご回答いただきまして、大変ありがとうございます。

問題については、ご指摘の通り修正しましたところACが出ました。また、計算量につきましてもお知恵をいただきありがとうございます。理解はまだ追いついていませんが、今後の学習で注意するべきポイントがわかりました。(問題の制約の10^5などは全く気にしたことがなく、目から鱗です。)

精進します。この度はありがとうございました。