【Go】【AtCoder】 bufio.NewScannerの標準入力でハマったこと

概要

最近Golangを書くことが多くなりました。普段はWeb開発ばかりやってますがそれ以外にも前から競プロに興味がありました。 なのでせっかくなのでGolangで始めてみようかなと思い立った矢先、いきなり問題にハマったのです。

ただ学びにもなったので備忘録としてこの記事を書いています。

ハマってしまった問題

僕がハマってしまった問題は下記です。

問題としては入力文字列を昇順にソートして出力するだけのものでシンプルなものです。

atcoder.jp

僕の提出回答は下記でした。

一見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⁵ です。入力される文字は英小文字のみのため1文字1B、最大2x10⁵ B=200KB必要となります。

このことから、僕がWAになってしまったのは、64 x 10³を超える文字列長の文字のテストケースに落ちてしまったのだと考えられます。

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システムにおいても想定される最大入力値に対して自システムもバグをおこさず正常に動くことが担保できるかなど 普段の意識改革にもなりました。

今後も競プロを趣味程度に頑張りつつ、学んだことは普段の仕事にも還元していきたいと思います。