2023-11-29 不穏 / PAST #12 I
不穏。
PAST #12 第12回 アルゴリズム実技検定 過去問
- I - 毎日のリンゴ
https://atcoder.jp/contests/past202209-open/tasks/past202209_i
- 提出: https://atcoder.jp/contests/past202209-open/submissions/48019674
- テストケースごとに
O(N)
で「悲しさ」の総和を求めるとO(NT)
になり間に合わない - 「悲しさ」の総和を見ると M で周期性がある
- M 個分の総和を取って、それが N に何回出てくるかを N / M で求める
N / M * (M個分の総和) + (N の後ろ N % M 分の総和)
で求める- これならテストケースごとに
O(M)
になるのでO(MT)
になり間に合う
use proconio::input;
fn main() {
input! {
t: usize,
case: [(usize, usize, usize); t],
};
for (n, a, m) in case {
let mut sum_head = 0_usize;
for i in 1..=n.min(m) {
sum_head += (a * i * m - a * i) % m;
}
if n < m {
println!("{}", sum_head);
continue;
}
let times = n / m;
let tail = n - (times * m);
let mut tail_sum = 0_usize;
for i in n - tail + 1..=n {
tail_sum += (a * i * m - a * i) % m;
}
let ans = sum_head * times + tail_sum;
println!("{}", ans);
}
}
今日のコミット。
- kireta 1 commit
- rust-atcoder 1 commit