問題解決の宝石箱

競技プログラミング/数学ネタ置き場

Educational Codeforces Round #10-F : Ants on a Circle

問題

Educational Codeforces Round #10-F : Ants on a Circle

【Educational Codeforces Round #10-F : Ants on a Circle】
\(N\) 匹の蟻が長さ \(M\) cm の円周上に乗っている。
蟻は1秒に付き1cm、円周上を一定の向きに動き続ける。
蟻が円周上でぶつかると、お互いに向きを変えて反対方向に動き出す。
各アリの初期位置 \( s_{i} \) と向き \( d_{i} \) が与えられるので、\(T\) 秒後の蟻の位置を答えよ。

  • $1 \leq n \leq 3 \times 10^5 $
  • $1 \leq m \leq 10^9 $
  • $0 \leq T \leq 10^{18} $

f:id:hama_DU:20170107142435p:plain

続きを読む

区間に含まれる区間の数をカウントするクエリにたくさん答えたい

$N$ 個の数区間 $R_i = [F_i,T_i) $ が与えられる。それに加え、クエリが $Q$ 個飛んでくる。それぞれついて答えよ。

  • 数区間 $ [A_j, B_j ) $が与えられる。$R$ のうち、$ [A_j, B_j ) $ に含まれるものはいくつあるか。

制約

  • $ 1 \leq N \leq 10^{5} $
  • $ 1 \leq F_i \lt T_i \leq 10^{5} $
  • $ 1 \leq Q \leq 10^{5} $
  • $ 1 \leq A_j \lt B_j \leq 10^{5} $

以降、カウント対象の数区間 $[F_j, T_j)$ のことを 対象区間、クエリで与えられる区間 $[A_j, B_j)$ のことを クエリ区間 と呼ぶ。

ちなみに、この問題が解けると 数列の区間中の種類数を求めるクエリ にも答えることができる。(以下の記事の解法3を参照。)

competitive.hamadu.net

続きを読む

SRM691 Div1Medium : Moneymanager

問題

SRM691 Div1Medium : Moneymanager

【SRM691 Div1Medium : Moneymanager】
$N$ 個のタスクがある。各タスクには数値 $ a_{i}, b_{i} $が決められている。
$i$番目のタスクを完了すると以下のことが順番に起こる。

- 経験値(以下、EXPと表記)が $ a_{i} $ 増える。
- お金を $ b_{i} \times EXP $ 円もらえる。

ただし、同じタスクは一度しかできないものとする。
また、タスクをちょうど N/2 個完了したとき、合宿に参加する。
合宿ではお金はもらえないがEXPが X 増える。
タスクをこなす順番をうまく選んだときの、もらえるお金の最大値を答えよ。

  • $1 \leq N \leq 50 $、{N}は偶数
  • $1 \leq a_{i} \leq 10^5 $
  • $1 \leq b_{i} \leq 10 $
  • $0 \leq X \leq 10^5 $
続きを読む

JOI春合宿 2012年 Day3-B カンガルー

今度こそ*1 今年最後の記事。

問題

JOI春合宿 2012年 Day3(PDF)

【JOI春合宿 2012年 Day3-B : カンガルー】
$N$ 匹のカンガルーがいる。それぞれの体の大きさは { A_{i} }、ポケットの大きさは $B_{i}$ である。
カンガルーたちは、以下の条件を満たす限り、カンガルーが他のポケットに入るという操作を繰り返す。

- $A_{i} < B_{j}$ を満たすカンガルーの組である
- カンガルー $i$ が他のカンガルーのポケットに入っていない
- カンガルー $j$ のポケットにカンガルーがいない

最終的なカンガルーたちの状態は何通りあるだろうか。

  • $1 \leq N \leq 300 $
  • $1 \leq B_{i} < A_{i} \leq 10^9 $
続きを読む