こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 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の値定義を変更しました。 ...
こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 010 - Score Sum Queries（★2） 実装 最初は全探索形式で実装しました。 use proconio::input; fn main() { input! { n: usize, cp: [(u8, u16); n], q: usize, lr: [(u32, u32); q], }; for i in 0..q { let (l, r) = lr[i]; let (mut a, mut b) = (0, 0); for j in l - 1..r { let (c, p) = cp[j as usize]; match c { 1 => a += p, _ => b += p, } } println!("{} {}", a, b); } } ですが、Qは10万、Nも10万が上限なので、やろうとしたら100億回の計算が必要なことになってしまいます。 ...
こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ABC049C - Daydream 実装 最初はシンプルに…（と思ったんですが結構行数使ってしまいました） 文字の長さとそれぞれの文字列が一致しているかどうかを見て、一致していたら渡された文字列から文字数だけ削除するという実装になっています。 use proconio::input; fn rmstr(mut s: String, n: usize) -> String { for _ in 0..n { s.remove(0); } s } fn main() { input! { mut s: String, } let c = 0; loop { if s.len() < 5 { println!("NO"); return; } let a = &s[c..c + 5]; if a == "dream" || a == "erase" { s = rmstr(s, 5); } else if s.len() >= 6 && &s[c..c + 6] == "eraser" { s = rmstr(s, 6); } else if s.len() >= 7 && &s[c..c + 7] == "dreamer" { s = rmstr(s, 7); } else { println!("NO"); return; } if s.len() == 0 { println!("YES"); return; } } } これで実装できた！…と思ったんですが、通りませんでした。 ...
こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ABC085C - Otoshidama 実装 まずは愚直に実装しました。 はい、全探索ですね。 use proconio::input; fn main() { input! { n: u32, y: u32, } for i in 0..=n { for j in 0..=n { for k in 0..=n { if i + j + k == n && 10000 * i + 5000 * j + 1000 * k == y { println!("{} {} {}", i, j, k); return; } } } } println!("-1 -1 -1"); } これでも一応一部のテストケースでは通るは通るんですが、nが最大値の2000だった場合、2000^3で実に80億通りも実行しなきゃならないですね。 そうなると実行時間に間に合いません。 というわけで最適化する必要があります。 で、どう最適化するかというところなんですが、、、AIと壁打ちします。 まずは最後のループを消すという方法を試してみます。 これは、つまり10枚のお札があるときに 10000円札が 2枚 5000円札が 3枚 だとわかったら、残りの1000円札は必然的に5枚に決まる、という特徴を活かせば実装できます。 ...
こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ABC085B - Kagami Mochi 実装 要は数列の重複をなくして、数列の長さを出力すればいいですね。 ということで以下のように実装しました。 use proconio::input; fn main() { input! { n: u8, mut d: [u8; n] }; d.sort(); d.dedup(); println!("{}", d.len()) } ということで今回はこれで👍
こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ABC088B - Card Game for Two 実装 以下のように実装しました。 use proconio::input; fn main() { input! { n: u8, mut a: [i16; n], }; a.sort_by(|a, b| b.cmp(a)); let mut a_sum = 0; let mut b_sum = 0; for (i, &v) in a.iter().enumerate() { if i % 2 == 0 { b_sum += v; } else { a_sum += v; } } println!("{}", (a_sum - b_sum).abs()); } 数列を大きい順に並べ替えて、それぞれを交互に足し合わせて最終的にその差を出力するという実装ですが、これでいいみたいですね。 （ぶっちゃけ出力例がなかったらどうすればいいのかわけわからんかった。。。） AIさんに聞いてみましたら、わかりやすい返答が返ってきました。 ケーキの分けっこで考えよう 例えば、目の前に大きさがバラバラのケーキが5個あるとします。 あなたはアリスで、先に1個選べます。友達のボブはあなたの次に選びます。 ケーキのサイズ： 10cm, 8cm, 5cm, 3cm, 2cm ...
こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ABC083B - Some Sums 実装 以下のように実装しました。 use proconio::input; fn to_vec(n: u16) -> Vec<u8> { let mut num = n.clone(); let mut r: Vec<u8> = vec![]; while num > 0 { r.push((num % 10) as u8); num = num / 10; } r } fn main() { input! { n: u16, a: u8, b: u8, }; let mut sum = 0; for i in 1..=n { let s = to_vec(i).into_iter().sum(); if a <= s && s <= b { sum += i; } } println!("{sum}"); } しかし、なぜかこれだとWAになりました。なぜ？ ...