[[ABC 084]]

ABC 084

C - Special Trains

問題

  • $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$

D - 2017-like Number

問題

  • 「$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()で使い分けられる。

programming_algorithm/contest_history/atcoder/2017/1230_abc084.txt · 最終更新: 2018/07/25 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0