こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 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になりました。なぜ？ ...
こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ABC087B - Coins 実装 以下のような実装を行いました。制約が緩いので全探索ですね。 use proconio::input; fn main() { input! { a: u16, b: u16, c: u16, x: u16, }; let mut cnt = 0; for i in 0..a + 1 { for j in 0..b + 1 { for k in 0..c + 1 { if 500 * i + 100 * j + 50 * k == x { cnt += 1; } } } } println!("{}", cnt); } これで通りました。 ちょっと物足りなかったので、AIと壁打ちしてもうちょっと早い方法にしました。 考え方としては以下の通りです。 「余り物」計算作戦（計算量：O(AB)） 500円玉と100円玉の枚数を決めた時点で、「あと何円足りないか」は計算で出せます。 その足りない分を50円玉でピッタリ埋められるかチェックします。 手順は以下の通りです。 500円玉を $i$ 枚、100円玉を $j$ 枚選ぶ（ここはループ）。 残りの金額を計算する： Rem = X - (500i + 100j) 判定： Rem が 0 以上か？（払いすぎてないか） Rem が 50円玉の合計（50 \ C）以下か？（足りるか） Rem は 50円で割り切れるか？（ピッタリいけるか） これだけで、50円玉の枚数を1枚ずつ試すループ（レバーC）を丸ごとカットできます！ ...
こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ABC081B - Shift only 実装 以下のように実装しました。 use proconio::input; fn main() { input! { n: u8, mut a: [u32; n], } let mut cnt = 0; loop { if !a.iter().find(|&&a| a % 2 != 0).is_some() { a = a.into_iter().map(|a| a / 2).collect(); } else { break; } cnt += 1; } println!("{cnt}"); } まぁまぁすっきり実装できたんじゃないでしょうか。 では今回はこれで👍
こんにちは、ナナオです。 昨日は急に中華バイキングを食べに行きたくなり、夕方から横浜中華街まで行ってきました。 言ってきた店はこちらです。 Google Maps エビチリとか麻婆茄子とか春巻きとか豆苗とかいろいろ食べてきました。 北京ダックは特に美味しかった。。。 エビの紹興酒漬けとか豚足とか珍しいのもありました。（豚足は撮るの忘れました） あとパクチーサラダとか牛筋とパクチー和えみたいなのがあったので、パクチー好きとして見逃すわけにはいかず注文しました。 しかし期待していたパクチーの癖の強さが抑えられていたように感じました。 その後もチャーハンや堅焼きそばなどドカ食いしました。 が、店を出た後に異変が！！ 食べすぎたせいかわかりませんが、お腹があまりにも苦しく、歩くと吐き気がするように。。 休み休みで帰りましたが、結構辛くてしんどかったです。 二人で6000円とかなりコスパは良かったんですが、もしかしたら使っている油の質が良くなかった可能性はありますね。。 まぁでも全体的においしかったので満足です。 ということで今回はこれで👍
こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 ABC081A - Placing Marbles 実装 以下のようにすっきり実装できました。 use proconio::{input, marker::Chars}; fn main() { input! { s: Chars, } let cnt = s.into_iter().filter(|c| c == &'1').count(); println!("{cnt}"); } proconio、マジで最高すぎる。。。 では今回はこれで👍