おそらく今年最後の記事。
問題
Wunder Fund 2016-F : Double Knapsack
数列に含まれる数は 1 以上 $N$ 以下の整数である。
$A, B$ から空でない部分列をそれぞれ適当に選択したとき、合計が等しくなるようにできるだろうか?
もしできる場合は、具体的に構成せよ。できなければ、その旨を報告せよ。
- $1 \leq N \leq 10^{6} $
ヒント:here
続きを読むおそらく今年最後の記事。
Wunder Fund 2016-F : Double Knapsack
ヒント:here
続きを読むCompetitive Programming Advent Calendar 2016 23日目の記事です。
鳩の巣原理と、競技プログラミングでの使われ方を紹介します。
昔々あるところに、5羽の鳩がおりました。彼らをすべて巣箱に入れたいのですが、あいにく巣は4つしかありませんでした。 すると以下の図のように、どこか1つの巣には2羽以上の鳩が入ってしまいます。
適当な入れ方をすると、2羽より多い巣があったり、空の巣があるかもしれません。でも、どんな入れ方をしても「どこかの巣には2羽以上」入ることが保証されます 。
一般に n 羽の鳩を m < n 個の巣にいれるとき、どこか 1 つの巣には鳩が2羽以上入ります。
更に一般化。巣に入っている鳩の最大数を最小化しようとすると、各巣になるべく均等に鳩を配る形になります。 このとき、鳩の数の最大値は *1 となり、これが最大値の下限になります。 以下の図は n = 10, m = 4 とした例で、最低でも3羽以上の鳩が入っている巣があることを示しています。
*1:小数点以下を切り上げる
SRM700 Div1Medium. CrazyFunctions
整数 , が与えられる。以下の条件を満たす関数 を数え上げよ。
hama-du-competitive.hatenablog.com
前回の記事の最後で紹介した練習問題の解答編。問題を整理して再掲する。
長さ の数列 が与えられる。クエリに 個答えよ。
全ての問題において、制約は以下の通り。
i
番目の値を v
に変更する。l
番目から r
番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、インデックスの合計 を出力。i
番目の値を v
に変更する。l
番目から r
番目の値の中で、 最も左端で*1 v
以下になるインデックス を求める。存在しない場合はその旨を報告。l
番目から r
番目の値を v
に変更する。l
番目から r
番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端の*2インデックスを求めること。
Codeforces Goodbye 2015 D. New Year and Ancient Prophecy
桁の数が与えられる。桁の間にいくつか*1線を引いて分割し、新たな数列を得ることを考えよう。
例えば、数 314159265358979 を 3 | 141 | 592 | 6535 | 8979 のように分割すると、数列
が得られる。
数を分割して数列にした時、要素が真に昇順に並んでいる()ような分割の仕方は何通りあるだろうか?
*1:0個でもよい
区間内の最大値/最小値のインデックスを求めるRMQの実装を求めています。
— tookunn (@tookunn_1213) October 6, 2016
この問題を以下のように定式化した。効率よく解けるだろうか?
長さ の数列 が与えられる。以下のクエリに 個答えよ。
i
番目の値を v
に変更する。l
番目から r
番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端の*1インデックスを求めること。制約は以下の通り。
*1:最も l に近い