読者です 読者をやめる 読者になる 読者になる

問題解決の宝石箱

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

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

 {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を参照。)

hama-du-competitive.hatenablog.com

続きを読む

ARC #068-F : Solitaire

日本語につき問題文は略。

arc068.contest.atcoder.jp

比較的理解が容易*1な解法を紹介する。

*1:個人の感想

続きを読む

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 }
続きを読む

Wunder Fund 2016-F : Double Knapsack

おそらく今年最後の記事。

問題

Wunder Fund 2016-F : Double Knapsack

【Wunder Fund 2016-F : Double Knapsack】
長さ  {N} の正の数列が 2 つ与えられる( {A, B} とおく)。
数列に含まれる数は 1 以上  {N} 以下の整数である。
 {A, B} から空でない部分列をそれぞれ適当に選択したとき、合計が等しくなるようにできるだろうか?
もしできる場合は、具体的に構成せよ。できなければ、その旨を報告せよ。

  •  {1 \leq N \leq 10^{6} }

ヒント:here

続きを読む

鳩の巣原理特集

Competitive Programming Advent Calendar 2016 23日目の記事です。

鳩の巣原理と、競技プログラミングでの使われ方を紹介します。

鳩の巣原理とは

昔々あるところに、5羽の鳩がおりました。彼らをすべて巣箱に入れたいのですが、あいにく巣は4つしかありませんでした。 すると以下の図のように、どこか1つの巣には2羽以上の鳩が入ってしまいます。

f:id:hama_DU:20161219005149p:plain

f:id:hama_DU:20161219005151p:plain

適当な入れ方をすると、2羽より多い巣があったり、空の巣があるかもしれません。でも、どんな入れ方をしても「どこかの巣には2羽以上」入ることが保証されます

f:id:hama_DU:20161219005134p:plain

一般に n 羽の鳩を m < n 個の巣にいれるとき、どこか 1 つの巣には鳩が2羽以上入ります。

更に一般化。巣に入っている鳩の最大数を最小化しようとすると、各巣になるべく均等に鳩を配る形になります。 このとき、鳩の数の最大値は  { \lceil n / m \rceil } *1 となり、これが最大値の下限になります。 以下の図は n = 10, m = 4 とした例で、最低でも3羽以上の鳩が入っている巣があることを示しています。

f:id:hama_DU:20161219005204p:plain

*1:小数点以下を切り上げる

続きを読む

SRM700 Div1Medium. CrazyFunctions

SRM700 Div1Medium. CrazyFunctions

整数  {n},  {k} が与えられる。以下の条件を満たす関数  {f} を数え上げよ。

  •  {f} の定義域および値域は 1以上n以下の整数である。
  •  {Z(f) = k} を満たす。関数  {Z} の定義は以下の通り。
    •  {Z(f)} {S(f, w)} の最小値を返す関数。 {w} は任意の非負整数。
    •  {S(f, w)} は 集合  {G(f, w)} の要素数
    •  {G(f, w)} {w} 以上の整数  {r} について、関数  { f^{r}(x)} の取りうる値の集合。
      •  { f^{w}(x)} とは、関数  {f}{x}{w} 回適用した値。 {f^{0}(x) = x}、および  {f^{j+1}(x) = f^{j}(f(x))} を満たす。

制約

  •  {1 \leq n \leq 5000}
  •  {1 \leq k \leq n}
続きを読む