Zenn
🐶

【競プロ】Goの標準入力でTLEを防ぐコツ

2023/06/16に公開
Go
AtCoder
競プロ
paiza
tech

TLEの原因の1つ、標準入力方法

AtCoderで問題を解いていると、プログラムの処理自体は間違っていないのに、処理が重すぎて制限時間内に処理が終わらない、といったことがよく起こります。
AtCoderでは、この状況をTLE（Time Limit Exceeded）と表します。

このTLEの原因の1つとして、Goでは、「標準入力が重すぎる」といった場合があります。
Goでは標準入力の方法が大きく2つに分かれており、記述が簡単な方を選んでしまうとTLEになってしまいがちです。

そこで本記事では、TLEになりやすい書き方と、TLEを回避しやすい書き方の紹介を行います。
「競プロでよく使われるC++だったら問題なく解けるのに、Goを使ったばっかりに解けない…！」といった状況を少しでも減らす手助けになれたら幸いです。

この記事の対象者

  • Goで競技プログラミングをやってみようと思っている方
  • GoでのTLEの解決方法を探している方
  • Goでの基本的な標準入力はできるが、もう少し詳しくなりたい方

もし、Goでの標準入力自体に不慣れであれば、こちらの記事も参考になるかもしれません。↓
Goの標準入力チートシート

標準入力方法の紹介

以下の2つの標準入力方法をご紹介します。

  • fmt.Scan
  • bufio.Scan

fmt.Scan

fmt.Scanで標準入力する方法は、基本的に少ない行数で書くことができ、比較的簡単です。
型を指定した入力も可能です。

一方で、大容量のデータを読み込む場合は処理時間がかかるという欠点があります。

fmt.Scanfを書くだけで、以下のサンプルコードのように、1行ずつ入力を変数に格納することができて便利です。

入力パターン
A B C
S
入力例
12 34 56
hello
入力例を受け取るコード
package main

import (
	"fmt"
)

func main() {
	// 1文字ずつデータ型を指定して受け取る
	var a, b, c int                   // int型の変数を宣言
	var s string                      // string型の変数を宣言
	fmt.Scanf("%d %d %d", &a, &b, &c) // %dでint型を代入
	fmt.Scanf("%s", &s)               // %sでstring型を代入
}

bufio.Scan

bufio.Scanで標準入力する方法は、fmt.Scanの書き方よりも行数が多くなりがちです。
また、基本的にstring型で入力を行うため、入力後に型変換の一手間が必要になります。

一方で、大容量のデータを読み込む場合でも処理時間が増えにくいという利点があります。

以下のサンプルコードのように、一度bufio.NewScanner(os.Stdin)でスキャナを作成した後、
sc.Scan()で読み込みます。
int型として読み込みたい場合などは、読み込み後に型変換の処理をする必要があります。

入力パターン
P1 P2 P3 ... Pn
入力例
12 34 56 78 90
入力例を受け取るコード
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)        // 標準入力を受け付けるスキャナ
	sc.Scan()                               // １行分の入力を取得する
	inputs := strings.Split(sc.Text(), " ") // 半角スペース区切りでstring型として配列inputsに格納

	// 配列inputsの中身をstring→intに変換してリストに格納
	var ps []int                   // Pnを格納する配列を宣言
	for _, input := range inputs { // 配列inputsの全ての要素について実行
		p, _ := strconv.Atoi(input) // string→intに型変換
		ps = append(ps, p)          // intに型変換した値を、Pnを格納する配列に追加
	}
}

読み込み速度比較

こちらの記事によると、
10万データ以上読み込みたい場合は、bufio.Scanの方が読み込み速度が速いそうです。

AtCoderでは10の5乗以上のデータを読み込むこともあります。
TLEを防ぐためにも、ぜひbufioを使った標準入力も試してみてください。

おわりに

本記事では、GoでTLEの原因になりうる、標準入力の書き方について紹介しました。

競技プログラミングではどうしてもC++がメジャーなため、Goだと書き方にひと工夫が必要という場面も出てきます。
本記事が、Goで競技プログラミングにチャレンジする際の手助けになれば幸いです。

お読みいただきありがとうございました！

Discussion