概要
最近Golangを書くことが多くなりました。普段はWeb開発ばかりやってますがそれ以外にも前から競プロに興味がありました。
なのでせっかくなのでGolangで始めてみようかなと思い立った矢先、いきなり問題にハマったのです。
ただ学びにもなったので備忘録としてこの記事を書いています。
ハマってしまった問題
僕がハマってしまった問題は下記です。
問題としては入力文字列を昇順にソートして出力するだけのものでシンプルなものです。
僕の提出回答は下記でした。
一見ACになりそうなのですが、結果としてはWAでした。
やっていることとしては間違っておらずでして、
受け取った文字列からstring型のsliceを作成して1語ずつ格納します。
その後, sort.Strings([]string)
を使ってsliceを昇順にソートします。
最後はstrings.Join
を用いて文字列を作成して出力で完了です。
でも何が原因でWAになってしまうか分からず、結局時間内にACにすることができませんでした。
package main
import (
"bufio"
"fmt"
"os"
"strings"
"sort"
)
func main() {
sc := bufio.NewScanner(os.Stdin)
sc.Scan()
inputs := strings.Split(sc.Text(), "")
sort.Strings(inputs)
a := strings.Join(inputs, "")
fmt.Printf("%s",a)
}
原因
ACにできなかった原因はscanner
のbuffer sizeにありました。
bufio.NewScannerで作成されるバッファですが、defaultとして4094バイト割り当てられており、最大はMaxScanTokenSize = 64 * 1024
とあるとおり64KBです。
参考
https://cs.opensource.google/go/go/+/refs/tags/go1.17.8:src/bufio/scan.go;l=76-84
今回ハマったAtCoderの問題では最大文字列長が2 x 10^5 です。入力される文字は英小文字のみのため1文字1B、最大2x10^5 B=200KB必要となります。
このことから、僕がWAになってしまったのは、64 x 10^3を超える文字列長の文字のテストケースに落ちてしまったのだと考えられます。
ACできたコード
コンテスト後に再度トライしたコードが下記になります。
最大buffer sizeを200KBに設定してみました。
無事ACできました。
package main
import (
"bufio"
"fmt"
"os"
"strings"
"sort"
)
func main() {
sc := bufio.NewScanner(os.Stdin)
// buffer作成
buf := make([]byte, 4096)
// scannerに最大2*10^5Bでbuffer登録
sc.Buffer(buf, 2000000)
sc.Scan()
inputs := strings.Split(sc.Text(), "")
sort.Strings(inputs)
a := strings.Join(inputs, "")
fmt.Printf("%s",a)
}
別解(fmt.Scan)
fmt.Scanの場合はbuffer sizeなど気にせずACでした。
ただbufio.NewScannerのときよりパフォーマンスは悪かった。
package main
import (
"fmt"
"strings"
"sort"
)
func main() {
// 1行目
var s string
fmt.Scan(&s)
inputs := strings.Split(s, "")
sort.Strings(inputs)
a := strings.Join(inputs, "")
fmt.Printf("%s",a)
}
まとめ
今回の問題からもちろん競プロとして最大値の境界値テストケースに対する考慮など気をつける点が学べましたが、
言語の仕様を理解すること、そして自分が携わっているWebシステムにおいても想定される最大入力値に対して自システムもバグをおこさず正常に動くことが担保できるかなど
普段の意識改革にもなりました。
今後も競プロを趣味程度に頑張りつつ、学んだことは普段の仕事にも還元していきたいと思います。