競技プログラミング

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 構造体の作成 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 package main import "fmt" type User struct { nickname string old int birth string state string } func (u *User) Scan() { fmt.Scan(&u.nickname, &u.old, &u.birth, &u.state) } func (u *User) Printf() { fmt.Printf(`User{ nickname : %s old : %d birth : %s state : %s } `, u.nickname, u.old, u.birth, u.state) } func main(){ var n int fmt.Scan(&n) users := make([]User, n) for i := 0; i < n; i++ { users[i].Scan() } for _, u := range users { u.Printf() } } ScanとPrintfをUserのメソッドとして定義しました。 これですっきり実装できましたね。 ということで今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 数の並び替え | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 “sort"パッケージを使えば楽に実装できます。 package main import ( "fmt" "sort" ) func main(){ var n int fmt.Scan(&n) a := make([]int, n) for i := 0; i < n; i++ { fmt.Scan(&a[i]) } sort.Ints(a) for _, v := range a { fmt.Println(v) } } ソートアルゴリズム、いろいろありますが、最初から実装することないですからね。。 では今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 【最安値】最安値を達成するには 4 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 package main import "fmt" func main(){ var n, x, a, y, b, z, c int fmt.Scan(&n, &x, &a, &y, &b, &z, &c) dp := make([]int, n + z) min := func(a, b int) int { if a < b { return a } else { return b } } for i := 1; i < n + z; i++ { dp[i] = 1000000 } for i := 0; i < n + z; i++ { if i >= x { dp[i] = min(dp[i], dp[i - x] + a) } if i >= y { dp[i] = min(dp[i], dp[i - y] + b) } if i >= z { dp[i] = min(dp[i], dp[i - z] + c) } } for i := n + z- 2; i > 0; i-- { dp[i] = min(dp[i], dp[i + 1]) } fmt.Println(dp[n]) } ただまだなぜこれで動くのかをちゃんと理解できていないので、繰り返しで学習しようと思います。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ifを使いますか？三項演算子を使いますか？ | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 実装は以下の通りです。 package main import ( "fmt" "strings" ) func main(){ var a int var b, c, d, e string fmt.Scan(&a, &b, &c, &d, &e) if a > 0 { fmt.Println("plus") } else { fmt.Println(a) } if b == "hoge" { fmt.Println("yes") } else { fmt.Println(b) } if len(c) == 10 { fmt.Println("ten") } else { fmt.Println(c) } i := strings.Index(d, "x") if i != -1 { fmt.Println(i) } else { fmt.Println("nothing") } if len(e) == 5 { fmt.Println("five") } else { fmt.Println(string(e[0])) } } Goは三項演算子がないので、普通にif文で実装しました。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 総和の計算 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 シンプルに実装するとこうです。 package main import "fmt" func main(){ var a, b int fmt.Scan(&a, &b) r := 0 for i := a; i <= b; i++ { r += i } fmt.Println(r) } ですがこれだと実行時間制約に間に合いません。 ということで解説を見ます。 1 - Nまでの総和はN(N + 1) / 2で求めることができるようです。 ということでAからBまでの総和は(1からBまでの総和) - (1からA - 1までの総和)ということになります。 この法則に従って実装を修正します。 package main import "fmt" func main(){ var a, b uint64 fmt.Scan(&a, &b) r := ((b * (b + 1)) / 2) - ((a * (a - 1)) / 2) fmt.Println(r) } と、修正しましたが、うまく値が出力されません。 どうやらこの問題の解答の最大値がGoだとオーバーフローしてしまうようです。 AIと壁打ちしたところ、math/bigパッケージを使えば解決するようです。 package main import ( "fmt" "math/big" ) func main(){ a := new(big.Int) b := new(big.Int) fmt.Scan(a, b) one := big.NewInt(1) two := big.NewInt(2) // b * (b + 1) / 2 t1 := new(big.Int).Div(new(big.Int).Mul(b, new(big.Int).Add(b, one)), two) // a * (a - 1) / 2 t2 := new(big.Int).Div(new(big.Int).Mul(a, new(big.Int).Sub(a, one)), two) r := new(big.Int).Sub(t1, t2) fmt.Println(r.String()) } 相当冗長なコードになりました。が、まぁ一応解決したのでいいでしょう。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 最安値を達成するには 3 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 package main import "fmt" func main(){ var n, x, a, y, b int fmt.Scan(&n, &x, &a, &y, &b) dp := make([]int, n + y) min := func(a, b int) int { if a < b { return a } else { return b } } for i := 1; i < n + y; i++ { dp[i] = 10000000 } for i := 1; i < n + y; i++ { if i >= x { dp[i] = min(dp[i], dp[i - x] + a) } if i >= y { dp[i] = min(dp[i], dp[i - y] + b) } } for i := n + y - 2; i > 0; i-- { dp[i] = min(dp[i], dp[i + 1]) } fmt.Println(dp[n]) } 正直よくわかってないんですよね。よくない。繰り返しやるしかない。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 最安値を達成するには 2 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 package main import "fmt" func main(){ var n, a, b int fmt.Scan(&n, &a, &b) dp := make([]int, n + 4) min := func(a, b int) int { if a < b { return a } else { return b } } dp[1] = a dp[2] = a dp[3] = min(a * 2, b) dp[4] = min(a * 2, b) for i := 5; i <= n + 3; i++ { dp[i] = min(dp[i - 2] + a, dp[i - 5] + b) } r := 0 for i := 1; i < 5; i++ { r = min(dp[i - 1], dp[i]) } fmt.Println(r) } ただ、これだと通りませんでした。 ということで解説を見てコードを修正しました。 package main import "fmt" func main(){ var n, a, b int fmt.Scan(&n, &a, &b) dp := make([]int, n + 5) min := func(a, b int) int { if a < b { return a } else { return b } } for i := 1; i < n + 5; i++ { dp[i] = 100000 } for i := 5; i < n + 5; i++ { if i >= 2 { dp[i] = min(dp[i], dp[i - 2] + a) } if i >= 5 { dp[i] = min(dp[i], dp[i - 5] + b) } } dp2 := make([]int, n + 5) for i := n + 4; i >= 1; i-- { dp2[i] = dp[i] for j := i + 1; j < n + 5; j++ { dp2[i] = min(dp2[i], dp[j]) } } fmt.Println(dp2[n]) } しかし、これも通らず。。。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 最安値を達成するには 1 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 議事コードをGoで書き起こしたのが以下の通りです。 package main import "fmt" func main(){ var n, a, b int fmt.Scan(&n, &a, &b) min := func(a, b int) int { if a < b { return a } else { return b } } dp := make([]int, n + 1) dp[1] = a for i := 2; i <= n; i++ { dp[i] = min(dp[i - 1] + a, dp[i - 2] + b) } fmt.Println(dp[n]) } これで解決しました。 部分式に書き起こすというのがDPのポイントですね。 （そこが難しい…） ということで今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 【階段の上り方】階段の上り方 3 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 前回の条件式に一つ追加しただけですね。 package main import "fmt" func main(){ var n, a, b, c int fmt.Scan(&n, &a, &b, &c) dp := make([]int, n + 1) dp[0] = 1 for i := 1; i <= n; i++ { if i >= a { dp[i] += dp[i - a] } if i >= b { dp[i] += dp[i - b] } if i >= c { dp[i] += dp[i - c] } } fmt.Println(dp[n]) } ということで今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 階段の上り方 2 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 package main import "fmt" func main(){ var n, a, b int fmt.Scan(&n, &a, &b) dp := make([]int, n + 1) dp[0] = 1 dp[a] = 1 dp[b] = 1 for i := 0; i <= n; i++ { if i > a { dp[i] += dp[i - a] } if i > b { dp[i] += dp[i - b] } } fmt.Println(dp[n]) } まず0段の場合は必ず一通り（上らない）となります。 そしてa段目のときとb段目のときにそれぞれ一通りとなるようにします。 これで提出してみましたが、不正解になりました。 考えてみれば、これだとa, b = 2, 4のときにおかしいことになりますね。 また、for文内の条件式がちょっとおかしいかったですね。 ということで修正しました。 package main import "fmt" func main(){ var n, a, b int fmt.Scan(&n, &a, &b) dp := make([]int, n + 1) dp[0] = 1 for i := 1; i <= n; i++ { if i >= a { dp[i] += dp[i - a] } if i >= b { dp[i] += dp[i - b] } } fmt.Println(dp[n]) } これで通りました。 ...