問題解決の宝石箱

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

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

指定区間の最大値/最小値のインデックスを求めるクエリにたくさん答えたい part2

f:id:hama_DU:20161015004003p:plain

hama-du-competitive.hatenablog.com

前回の記事の最後で紹介した練習問題の解答編。問題を整理して再掲する。

長さ  {N} の数列 { a_{1}, a_{2}, ... , a_{N} } が与えられる。クエリに  {Q} 個答えよ。

全ての問題において、制約は以下の通り。

  • 数列の長さ:{ 1 \leq N \leq 10^5 }
  • 要素の値:{ 1 \leq a_{i}, v \leq 10^9 }
  • クエリの数:{ 1 \leq Q \leq 10^5 }

問題1

  • i 番目の値を v に変更する。
  • l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、インデックスの合計 を出力。

問題2

  • i 番目の値を v に変更する。
  • l 番目から r 番目の値の中で、 最も左端で*1 v 以下になるインデックス を求める。存在しない場合はその旨を報告。

問題3

  • l 番目から r 番目の値を v に変更する。
  • l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端の*2インデックスを求めること。

*1:最も l に近い

*2:最も l に近い

続きを読む

Codeforces Goodbye 2015 D. New Year and Ancient Prophecy

f:id:hama_DU:20161012210804p:plain

Codeforces Goodbye 2015 D. New Year and Ancient Prophecy

{ n } 桁の数が与えられる。桁の間にいくつか*1線を引いて分割し、新たな数列を得ることを考えよう。

例えば、数 314159265358979 を 3 | 141 | 592 | 6535 | 8979 のように分割すると、数列

{ \displaystyle
a = \{ 3, 141, 592, 6535, 8979 \}
}

が得られる。

数を分割して数列にした時、要素が真に昇順に並んでいる({ a_{1} \lt a_{2} \lt ... \lt a_{k} })ような分割の仕方は何通りあるだろうか?

制約

  • 桁数:{ 1 \leq n \leq 5000 }

*1:0個でもよい

続きを読む

指定区間の最大値/最小値のインデックスを求めるクエリにたくさん答えたい part1

この問題を以下のように定式化した。効率よく解けるだろうか?

長さ  {N} の数列 { a_{1}, a_{2}, ... , a_{N} } が与えられる。以下のクエリに  {Q} 個答えよ。

  • クエリ1 : i 番目の値を v に変更する。
  • クエリ2 : l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端の*1インデックスを求めること。

制約は以下の通り。

  • 数列の長さ:{ 1 \leq N \leq 10^5 }
  • 要素の値:{ 1 \leq a_{i}, v \leq 10^9 }
  • クエリの数:{ 1 \leq Q \leq 10^5 }

*1:最も l に近い

続きを読む