Golangでアルゴリズムを学ぶ
Aizu Online Judge を使って、プログラミングコンテストの過去問やアルゴリズムの問題をGolangで解いてみようと思います。
今までプロコンに出場したこともないし、アルゴリズムをしっかり勉強したことも無いので、Golangを覚えがてら一緒に学習してしまおうというのが動機です。
AOJ(Aizu Online Judge)とは
AOJはオンラインジャッジシステムのひとつです。会津大学が運営を行っています。
ICPCやパソコン甲子園などで過去に出題された問題が掲載されている様子。
ユーザーは問題文に書かれている仕様や制限(CPU時間やメモリ使用量)を満たすプログラムを作成します。それをAOJのWebサイトからPOSTすると、仕様に基づいた入力に対して正しい出力を行っているか を自動で判定し即座にフィードバックしてくれます。
組み合わせの問題をやってみた
https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/7/ITP1_7_B
問題
1 から n までの数の中から、重複無しで3つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。
例えば、1 から 5 までの数から3つを選んでそれらの合計が 9 となる組み合わせは、
1 + 3 + 5 = 9
2 + 3 + 4 = 9
の2通りがあります。
Input
複数のデータセットが入力として与えられます。各データセットでは、空白で区切られた n、x が 1 行に与えられます。
n、x がともに 0 のとき入力の終わりとします。
Output
各データセットについて、組み合わせの数を1行に出力して下さい。
↑ こんな感じで出題されるので、Golangでプログラミングしてその結果をサイトからPOSTする感じです。 課題を与えられそれを解くという学生の本分を思い出し、やる気湧いてきちゃいますね。
自分が書いたコードはこちら
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) // 組み合わせの数 func main() { sc := bufio.NewScanner(os.Stdin) for { sc.Scan() ary := strings.Split(sc.Text(), " ") n, _ := strconv.Atoi(ary[0]) x, _ := strconv.Atoi(ary[1]) if n == 0 && x == 0 { break } cnt := 0 for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { if j <= i { continue } for k := 1; k <= n; k++ { if k <= i || k <= j { continue } else if i+j+k == x { cnt++ } } } } fmt.Println(cnt) } }
AOJからのフィードバック
こんな感じです。
コンパイル後、複数のテストケースを走らせてるようですね、CPU時間やメモリ量などもみれて良き良き。
しばらくAOJから問題を抜粋してGolang使って問題解いていこうと思っています。