Posts

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 総和の計算 | レベルアップ問題集 | プログラミング学習サイト【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]) } これで通りました。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 階段の上り方 1 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 ヒントにあるような実装をそのままgoに書き起こしました。 package main import "fmt" func main(){ var n int fmt.Scan(&n) dp := make([]int, n + 1) dp[0] = 1 for i := 1; i <= n; i++ { if i >= 1 { dp[i] += dp[i - 1] } if i >= 2 { dp[i] += dp[i - 2] } } fmt.Println(dp[n]) } この実装、なんとフィボナッチ数列と同じ結果になるんですね。不思議～。 考え方としては、0段は一通り（上らない）として、それ以降の場合の上り方がどのように増えていくかというのを考えるのですが、まず1段ずつ上る場合というのが必ず一通りあるのでdp[i] += dp[i - 1]が成り立ちます。 つまり条件i >= 1の場合、dp[i]は毎回必ず1通りになります。 これに2段で上れる方法が追加されたとき、まず2段のときは2段で上る方法と1段ずつ上る方法の二通りになります。 3段上るときは1段ずつ、2段と1段、1段と2段の三通りになります。 4段になると1段ずつ、1段2段1段、2段1段1段、1段1段2段、2段ずつの5通り…となります。 …確かに並べるとフィボナッチ数列です。 ではなぜそうなるか。 …ちょっと僕では説明できなさそうなので、AIに聞きました。 たとえば、あなたが今「10段目」にたどり着いたとします。その「1歩前」を思い出してみてください。 1歩で1段か2段しかのぼれないなら、10段目に来る直前は、絶対にこの2つのどちらかにいたはずです。 9段目にいて、あと「1段」のぼった 8段目にいて、あと「2段」いっぺんにのぼった これ以外の場所から10段目にワープすることはできませんよね。 確かにそうですね。。 nで考えて難しいなら、n - 1で考えるというアプローチは大切ですね。 ということで今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 【漸化式】 3項間漸化式 2 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 package main import "fmt" func main(){ a := make([]int, 41) a[1] = 1 a[2] = 1 for i := 3; i <= 40; i++ { a[i] = a[i - 2] + a[i - 1] } var q int fmt.Scan(&q) for i := 0; i < q; i++ { var k int fmt.Scan(&k) fmt.Println(a[k]) } } 先にフィボナッチ数列を計算しておけば、出力はそれを参照するだけでよくなるので簡単ですね。 ということで今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 3項間漸化式 1 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 実装は以下の通りです。 フィボナッチ数列の計算ですね。 package main import "fmt" func main(){ a := make([]int, 41) a[1] = 1 a[2] = 1 for i := 3; i <= 40; i++ { a[i] = a[i - 2] + a[i - 1] } var k int fmt.Scan(&k) fmt.Println(a[k]) } 前回からの流れを踏んでいれば簡単ですね。 ということで今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 特殊な2項間漸化式 2 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 package main import "fmt" func main(){ var x, d1, d2, q int fmt.Scan(&x, &d1, &d2, &q) a := make([]int, 1001) a[1] = x for i := 2; i <= 1000; i++ { if i % 2 != 0 { a[i] = a[i - 1] + d1 } else { a[i] = a[i - 1] + d2 } } for i := 0; i < q; i++ { var k int fmt.Scan(&k) fmt.Println(a[k]) } } 前回の応用で実装できました。 ということで今回はこれで👍