2023-01-11 ABC084 の A, B, C, D を解いた
ABC084 : AtCoder Beginner Contest 084 の A, B, C, D を解いた。
- A - New Year https://atcoder.jp/contests/abc084/tasks/abc084_a
- B - Postal Code
https://atcoder.jp/contests/abc084/tasks/abc084_b
- 提出: https://atcoder.jp/contests/abc084/submissions/37943403
s.into_iter().enumerate().all(|(i, c)| (i == a && c == '-') || (i != a && c.is_ascii_digit()))
- C - Special Trains
https://atcoder.jp/contests/abc084/tasks/abc084_c
- 提出: https://atcoder.jp/contests/abc084/submissions/37943830
- 駅の個数が少ないので各駅ごとに駅 N までほとんど素朴にシミュレーションしても間に合う
- 周期の部分のみ
%
で求める点のみ注意する
- D - 2017-like Number
https://atcoder.jp/contests/abc084/tasks/abc084_d
- 提出: https://atcoder.jp/contests/abc084/submissions/37944132
- 「 2017 に似た数」の判定には N 以下の数について素数判定できれば良い
N <= 10^5
なのでエラトステネスのふるいとして保持しておける- このふるいを使って今度は
N
以下の「 2017 に似た数」を調べる 3..
で順に求めていけば良い- 最後に
0
からx
までの「 2017 に似た数」の個数を持つ累積和を用意する - これは
l..=r
の範囲における個数が必要なことから思いつく - これで準備が終わっているのでクエリに答えていけば良い
count[r] - count[l-1]
use proconio::input;
fn sieve_of_eratosthenes(n: usize) -> Vec<bool> {
let mut p = vec![];
let mut b = vec![true; n + 1];
for i in 2.. {
if i * i > n {
for j in i..=n {
if b[j] {
p.push(j);
}
}
break;
}
if b[i] {
p.push(i);
for j in (i + i..=n).step_by(i) {
b[j] = false;
}
}
}
b
}
fn main() {
input! {
q: usize,
lr: [(usize, usize); q],
};
let max = 100_000;
let sieve = sieve_of_eratosthenes(max);
let mut count = vec![0_usize; max + 1];
for i in 3..=max {
count[i] = if i % 2 != 0 && sieve[i] && sieve[(i + 1) / 2] {
1
} else {
0
};
}
for i in 1..max {
count[i + 1] += count[i];
}
for (l, r) in lr {
println!("{}", count[r] - count[l - 1]);
}
}
昼に https://findy.connpass.com/event/268897/ に参加した。聞いた。
夜に https://forkwell.connpass.com/event/270393/ に参加した。聞いた。
イベント参加もうちょっと増やしてみようかと。
Kindle Oasis が壊れた。画面を誰かに踏まれた (?) くさい。
今日のコミット。
- rust-sandbox 9 commits
- rust-examples 1 commit
- rust-atcoder 1 commit