ABC 084

Atcoder Beginner Contest 084

• $N$ 個の駅が一直線に並ぶ
• $i$ 番目の駅 $(1 \le i \le N-1)$ から、次の駅に向かって時刻 $S_i$ から $F_i$ ごとに列車が発車する（列車は次の駅で止まる）
• 次の駅まではそれぞれ $C_i$ かかる
• $i$ 番目の駅 $(1 \le i \le N)$ のそれぞれから、$N$ 番目の駅までにかかる所要時間を求めよ

$1 \le N \le 500$ なので、各駅からそのままシミュレーションすればいい。

ある駅 $i$ に時刻 $t$ に着いた時、次の駅に到着する時間は、

• まだ最初の運行時刻でない（$S_i \lt t$）場合、$S_i + C_i$
• そうでなければ、次の発車時刻は
  • 「整数 $m$ の倍数で、ある整数 $n$ 以上の最小のもの」は、$math.ceil(n/m) \times m$ で求められる
  • よって、次の駅に到着する時刻は $math.ceil(t/F_i) \times F_i + C_i$

• 「$N$ も、$(N+1)/2$ も素数」である整数を、「2017に似た数」と呼ぶことにする
• $Q$ 個のクエリが与えられる
• 各クエリでは、2つの整数 $l_i,r_i$ が与えられる
• 各クエリについて、「$l_i$ 以上 $r_i$ 以下の『2017に似た数』の個数」を求めよ

制約 $1 \le l,r \le 10^5$ なので、とりあえず $10^5$ までの「2017に似た数」をすべて求める。

$10^5$ までの素数をすべて求め、$\frac{10^5}{2}$ までの素数 $p$ について、$2p-1$ も素数ならば、$2p-1$ が「2017に似た数」である。

すべて求めたら、小さい順にソートしておく。各クエリの答えは、二分探索で求められる。

二分探索で、「$r_i$ が挿入される位置 ー $l_i$ が挿入される位置」が、答えとなる。ただし、

• $l_i$ が「2017に似た数」だった場合、挿入位置は $l_i$ の位置
• $r_i$ が「2017に似た数」だった場合、挿入位置は $r_i$ の次の位置

とする。これは、Python の bisect ライブラリでは、bisect_left()とbisect()で使い分けられる。