Posts

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 階段の上り方 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]) } } 前回の応用で実装できました。 ということで今回はこれで👍

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

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 2項間漸化式 2 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 このように実装しました。s package main import "fmt" func main(){ var x, d, q int fmt.Scan(&x, &d, &q) k := make([]int, q) max := 0 for i := 0; i < q; i++ { fmt.Scan(&k[i]) if i == q - 1 { max = k[i] } } a := make([]int, max) a[0] = x for i := 1; i < max; i++ { a[i] = a[i - 1] + d } for i := 0; i < q; i++ { fmt.Println(a[k[i] - 1]) } } ですがこれだと通りませんでした。。 k_Qが必ずmaxになるわけではないようです。 ということで少し修正しました。 package main import "fmt" func main(){ var x, d, q int fmt.Scan(&x, &d, &q) k := make([]int, q) max := 0 for i := 0; i < q; i++ { fmt.Scan(&k[i]) if max < k[i] { max = k[i] } } a := make([]int, max) a[0] = x for i := 1; i < max; i++ { a[i] = a[i - 1] + d } for i := 0; i < q; i++ { fmt.Println(a[k[i] - 1]) } } これでうまく動作しました。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 2項間漸化式 1 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 DP（動的計画法）についてはなんとな～く理解はしているものの、実装となるととんと出来ないのでここで極めておきます。 実装 実装は以下の通りです。 package main import "fmt" func main(){ var x, d, k int fmt.Scan(&x, &d, &k) a := make([]int, k) a[0] = x for i := 1; i < k; i++ { a[i] = a[i - 1] + d } fmt.Println(a[k - 1]) } これが一番簡単なDPのコードか… このくらいならシンプルで理解しやすいですね。 ということで今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 024 - Select +／- One（★2） 実装 まずは以下のように実装しました。 use proconio::input; fn main() { input! { n: usize, k: u32, a: [i32; n], b: [i32; n], } let d = (0..n).fold(0, |acc, i| acc + (a[i] - b[i]).abs()) as u32; if k >= d && d % 2 == k % 2 { println!("Yes"); } else { println!("No"); } } なんとこれで解けてしまいました。 なんか似てる問題あったな～と思ったらこれでした。 Atcoder ABS ABC086C Traveling fold使ってすっきり実装できましたし、満足です。 というわけで今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 022 - Cubic Cake（★2） 実装 正方形にするという要件がそもそも結構むずい気がするんですが、本当に星2か？ まず、a = b = cの場合は0回でいいです。 また、2 1 1や1 2 1の場合は1回でいいです。 3 1 1の場合は2回です。4 1 1の場合は3回です。4 2 2の場合は1回です。 というように、二辺が同じ場合は公約数に沿った法則性がありそうですね。 つまり、「（abcの最大）/（abcの公約数）-（abcの最小）/（abcの公約数）」みたいな… 三辺とも違う場合はどうでしょうか？ 9 6 3の場合、333にすればいいですね。 イメージがつかなかったのでちょっと図を描いてみました。 …図に書いてみたらわかりました。3回切る必要があります。 二辺が同じ場合の法則を適用すると「3 - 1 = 2」になるので、3辺になるとちょっと法則が変わるっぽい…？ ここで問題の例を見ると、3 2 2の場合は4回切る必要があるようですね。となると先ほど私が立てた法則も間違っていることがわかりますね。これもうわかんねぇなぁ… ただ、公約数が絡んでいそうなことはわかります。 3 2 2の場合の公約数は1で4回切る必要がある…ということで、以下のような方程式ならどうでしょうか？ a / (abcの公約数) - 1 + b / (abcの公約数) - 1 + c / (abcの公約数) - 1 これならすべてのユースケースに合っていそうですね。 ということで実装していきます。 ポイントは公約数を出力する実装です。 use proconio::input; fn gcd(a: u32, b: u32, c: u32) -> u32 { let min = a.min(b).min(c); for i in (1..=min).rev() { if a % i == 0 && b % i == 0 && c % i == 0 { return i; } } 1 } fn main() { input! { a: u32, b: u32, c: u32, } let gcd = gcd(a, b, c); let r = a / gcd - 1 + b / gcd - 1 + c / gcd - 1; println!("{}", r); } オーバーフローしてしまったので、数値型をより余裕のある形に変更しました。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ABC086C - Traveling 実装 まずは単純に考えてみます。 まず条件のひとつ目として、時間内に移動できる距離は時間内に収まっている必要があります。 移動距離は「移動前のx座標と移動後のx座標の差」と「移動前のy座標と移動後のy座標の差」を足し合わせれば計算できます。 この「移動距離」が「移動前の時間と移動後の時間の差」の中に収まっているかどうかを判定する必要があります。 次に条件の二つ目として、先ほどの「移動距離」と「移動前の時間と移動後の時間の差」の奇数偶数判定が一致している必要があります。 これは単純で、例えば以下のようなケースを考えてみます。 2 1 1 0 3 1 0 このケースでは時間が1のときと時間が3のときの場所が全く同じです。 この場合条件の一つ目は満たしていますが、動き方としてはどうなるでしょうか？ …一回違う場所に行って戻ればこの動きは実現しそうですね。 ということは、条件1を満たしている場合で時間に余りがある場合は「行って」「戻る」という挙動ができるのであればよさそうですね。 さて、論よりコードということで以下のように実装しました。 use proconio::input; fn main() { input! { n: usize, data: [(i16, i16, i16); n], }; let (mut c, mut sy, mut sx) = (0, 0, 0); for i in 0..n { let (t, x, y) = data[i]; let dd = (x - sx).abs() + (y - sy).abs(); let dt = t - c; if dd > dt || dt % 2 != dd % 2 { println!("No"); return; } sy = y; sx = x; c = t; } println!("Yes"); } これだとうまく通りませんでした。なんだかまた値のオーバーフローが起こってしまったようなので、dataの値定義を変更しました。 ...