はじめに
唐突ですがGoで競プロコードはどう書くのかなと気になったのでやります.
Goが好きなので.
競プロ経験者だけれどGoは知らない人がこの記事を読んで「Goってこんな感じなんだ~」って流し見してくれれば嬉しいです.
注意
ぼく自身,競技プログラミングは弱く,かつ普段はC++を使っているので最適でなく助長な記述等になっているかもしれませんがご容赦ください.あくまで雰囲気を感じてもらえたらとおもいます.ちなみにこの問題が初めてのGoでのACになりました.また,DFS自体についての解説,問題の解説は行っていません.
#やる
問題はABC161D - Lunlun Numberを解きます.
この問題の選定理由は特にないです.ここ最近でDFS使って解けるからって所でしょうか(ABC165-Cがありますが...)
早速ですが解答コードを先に見せてから解説(?)していこうと思います.
package main
import (
"fmt"
"sort"
)
var ans []int
func dfs(n int) {
if 3234566667 < n {
return
}
ans = append(ans, n)
d := n % 10
if d != 0 {
dfs(n*10 + d - 1)
}
if d != 9 {
dfs(n*10 + d + 1)
}
dfs(n*10 + d)
}
func main() {
var k int
fmt.Scan(&k)
for i := 0; i < 9; i++ {
dfs(i + 1)
}
sort.Ints(ans)
fmt.Println(ans[k-1])
}
意外と普通ですね(?)
package
package main
import (
"fmt"
"sort"
)
まずは必要パッケージをインポートします.
-
fmt : 標準入出力を使うために用います.
fmt.Scan(&n)
で変数nの標準入力を受け付けます.
fmt.Printf("%d\n",n)
で変数nを出力します.さらにfmt.Println(n)
で改行付きで標準出力します.ここまでは競プロerお馴染みのC++と差異はありません.パッケージから用いる関数の頭文字を大文字にすることを忘れないようにしましょう. -
sort : その名の通りソートの為のパッケージです.配列やスライスはもちろんmapなどにも対応しています.
slice
var ans []int
C++で言うところのvector
で可変長配列です.ここに解候補を入れていきます.
型の宣言は変数名の後に書くことに気を付けます.
DFS
func dfs(n int) {
if 3234566667 < n {
return
}
ans = append(ans, n)
d := n % 10
if d != 0 {
dfs(n*10 + d - 1)
}
if d != 9 {
dfs(n*10 + d + 1)
}
dfs(n*10 + d)
}
- ここがメインとなるDFSです.Goでの関数の書き方は
func 関数名(引数 型) 戻り値型{
処理
}
のように書きます.今回のDFSは整数nを引数にして,戻り値はありません(C++でいうvoid型です)Goのint型は実装のCPUやOSに依存し,int64型かint32型になるみたいです.
- sliceへの要素の追加は
append
を使います.ここで注意するべきなのは
append(ans,n)
ではなく
ans=append(ans,n)
と書くことに気を付けましょう.
-
Goでの
if文
は処理部分には1行の処理でも必ず中括弧{}
を用います. -
再帰の書き方もそのままで分かりやすいですね.
main関数
func main() {
var k int
fmt.Scan(&k)
for i := 0; i < 9; i++ {
dfs(i + 1)
}
sort.Ints(ans)
fmt.Println(ans[k-1])
}
main関数から処理がスタートします.ですので標準入力や具体的な処理,解答の出力はmain関数で行います.
今回の問題では特筆すべきことは無いですが,for文の書き方もC++と同様で分かりやすいですね.
おわりに
初めてGoで競プロの問題を解きましたが,特に困ることもなく書きやすかったです.
今回突発的に本記事の作成をしたため,問題選定が微妙だったかもしれません.(扱う内容的にはstringやデータ構造の利用も無く単なる整数の処理でした)
これを機に僕もGoで問題を解いていきたいと思います.Goでの競プロを取り組む人が増えていったらいいなと思います(^^)/.