今年の8月、カザンは学童向けの国際プログラミングオリンピック-IOI 2016を開催しました。ロシアのチームは、総合ランキングで2番目になりました 。
銀メダリストの一人、MytishchiのDenis Solonkovは、 「分子の検出」タスクの分析を行いました。これは、オリンピアードの参加者に提供されました。
デニス・ソロンコフは、オールロシアンプログラミングオリンピックの複数勝者であり、現在はHSEの学生であるプログラマースクールの卒業生であるモスクワCTFスクールです。
デニスの教師の一人として、私は彼にIOI 2016でタスク分析を行うように頼みました。
タスク条件
ピーターは、分子を検出するデバイスを作成した会社で働いています。 各分子は、全体的に正の重量を持っています。 デバイスは、検出間隔[l、u]によって特徴付けられます。ここで、lとuは正の整数です。 このセットに含まれる分子の総重量がデバイスの検出間隔に属するサブセットが含まれている場合にのみ、デバイスは多くの分子を検出できます。
完全に見る
より正式には、重みがw0、...、wn − 1のn個の分子を考えます。 l≤wi1 + ... + wim≤uとなるような多くの異なるインデックスI = {i1、...、im}がある場合、検出は成功したと見なされます。
デバイスの機能により、lとuの差は、最も重い分子と最も軽い分子の重量の差以上であることが保証されています。 より正式には、u-l≥wmax-wmin、ここでwmax = max（w0、...、wn − 1）およびwmin = min（w0、...、wn − 1）。
デバイスの検出間隔に属する総重量を持つ分子のサブセットを見つけるか、そのようなサブセットが存在しないと判断するプログラムを作成する必要があります。
1つの関数（メソッド）を実装する必要があります。
int [] solve（int l、int u、int [] w）
必要なサブセットが存在する場合、関数はそのようなサブセットを形成する分子のインデックスの配列を返す必要があります。 正解が複数ある場合は、いずれかを返します。
必要なサブセットが存在しない場合、関数は空の配列を返す必要があります。
Cプログラミング言語の場合、関数のシグネチャはわずかに異なります。
int solve（int l、int u、int [] w、int n、int []結果）
n：wの要素数（分子の数）、
他のパラメーターは上記と同じです。
（上記のように）m個のインデックスの配列を返す代わりに、関数は結果配列の最初のm個のセルにインデックスを書き込み、mを返す必要があります。
必要なサブセットが存在しない場合、関数は結果配列に何も書き込まずに0を返す必要があります。
プログラムは、返された配列（またはC言語の結果配列）に任意の順序でインデックスを書き込むことができます。
提供されたファイルテンプレートを使用して、選択したプログラミング言語での実装を明確にしてください。
例1
解決（15、17、[6、8、8、7]）
この例では、重量が6、8、8、および7の4つの分子があります。デバイスは、合計重量が15〜17の分子のサブセットを検出できます。 17-15≥8-6であることに注意してください。分子1と3の合計重量はw1 + w3 = 8 + 7 = 15なので、関数は[1、3]を返すことができます。 その他の可能な正解は、[1、2]（w1 + w3 = 8 + 8 = 16）および[2、3]（w1 + w3 = 8 + 7 = 15）です。
例2
解決（14、15、[5、5、6、6]）
この例では、重みが5、5、6、および6の4つの分子があります。合計重量が14〜15のサブセットを見つける必要があります。 繰り返しますが、15-14≥6-5であることに注意してください。この例では、総重量が14〜15の分子のサブセットがないため、関数は空の配列を返す必要があります。
例3
解決（10、20、[15、17、16、18]）
この例では、重量が15、17、16、18の4つの分子があります。合計重量が10〜20のサブセットを見つける必要があります。 繰り返しますが、20-10≥18-15であることに注意してください。1つの要素で構成されるサブセットの重みはそれぞれ10〜20であり、可能な正解は[0]、[1]、[2]および[3]です。
グレーディングシステム
（9ポイント）：1≤n≤100、1≤wi≤100、1≤u、l≤1000、すべてのwiは等しい。
（10点）：1≤n≤100、1≤wi、u、l≤1000、およびmax（w0、...、wn − 1）-min（w0、...、wn − 1）≤1
（12点）：1≤n≤100および1≤wi、u、l≤1000
（15ポイント）：1≤n≤10000および1≤wi、u、l≤10000
（23点）：1≤n≤10 000および1≤wi、u、l≤500 000
（31点）：1≤n≤200000および1≤wi、u、l <231。
テストモジュールの例
チェックモジュールは、次の形式でデータを受信します。
デバイスの機能により、lとuの差は、最も重い分子と最も軽い分子の重量の差以上であることが保証されています。 より正式には、u-l≥wmax-wmin、ここでwmax = max（w0、...、wn − 1）およびwmin = min（w0、...、wn − 1）。
デバイスの検出間隔に属する総重量を持つ分子のサブセットを見つけるか、そのようなサブセットが存在しないと判断するプログラムを作成する必要があります。
実装の詳細
1つの関数（メソッド）を実装する必要があります。
int [] solve（int l、int u、int [] w）
- lおよびu：検出間隔の境界、
- w：分子量。
必要なサブセットが存在する場合、関数はそのようなサブセットを形成する分子のインデックスの配列を返す必要があります。 正解が複数ある場合は、いずれかを返します。
必要なサブセットが存在しない場合、関数は空の配列を返す必要があります。
Cプログラミング言語の場合、関数のシグネチャはわずかに異なります。
int solve（int l、int u、int [] w、int n、int []結果）
n：wの要素数（分子の数）、
他のパラメーターは上記と同じです。
（上記のように）m個のインデックスの配列を返す代わりに、関数は結果配列の最初のm個のセルにインデックスを書き込み、mを返す必要があります。
必要なサブセットが存在しない場合、関数は結果配列に何も書き込まずに0を返す必要があります。
プログラムは、返された配列（またはC言語の結果配列）に任意の順序でインデックスを書き込むことができます。
提供されたファイルテンプレートを使用して、選択したプログラミング言語での実装を明確にしてください。
例
例1
解決（15、17、[6、8、8、7]）
この例では、重量が6、8、8、および7の4つの分子があります。デバイスは、合計重量が15〜17の分子のサブセットを検出できます。 17-15≥8-6であることに注意してください。分子1と3の合計重量はw1 + w3 = 8 + 7 = 15なので、関数は[1、3]を返すことができます。 その他の可能な正解は、[1、2]（w1 + w3 = 8 + 8 = 16）および[2、3]（w1 + w3 = 8 + 7 = 15）です。
例2
解決（14、15、[5、5、6、6]）
この例では、重みが5、5、6、および6の4つの分子があります。合計重量が14〜15のサブセットを見つける必要があります。 繰り返しますが、15-14≥6-5であることに注意してください。この例では、総重量が14〜15の分子のサブセットがないため、関数は空の配列を返す必要があります。
例3
解決（10、20、[15、17、16、18]）
この例では、重量が15、17、16、18の4つの分子があります。合計重量が10〜20のサブセットを見つける必要があります。 繰り返しますが、20-10≥18-15であることに注意してください。1つの要素で構成されるサブセットの重みはそれぞれ10〜20であり、可能な正解は[0]、[1]、[2]および[3]です。
グレーディングシステム
（9ポイント）：1≤n≤100、1≤wi≤100、1≤u、l≤1000、すべてのwiは等しい。
（10点）：1≤n≤100、1≤wi、u、l≤1000、およびmax（w0、...、wn − 1）-min（w0、...、wn − 1）≤1
（12点）：1≤n≤100および1≤wi、u、l≤1000
（15ポイント）：1≤n≤10000および1≤wi、u、l≤10000
（23点）：1≤n≤10 000および1≤wi、u、l≤500 000
（31点）：1≤n≤200000および1≤wi、u、l <231。
テストモジュールの例
チェックモジュールは、次の形式でデータを受信します。
- 1行目：整数n、l、u。
- 2行目：n個の整数：w0、...、wn − 1。
デニスのソリューション
タスクはすでに十分に形式化されています。 長さnの配列wから数値のサブシーケンスを選択し、それらの合計が区間[l、u]になるようにする必要があります。 また、奇妙な条件があります：u-l≥wmax-wmin（1）。
問題を解決する上で明らかに役割を果たします。そうでなければ、単に存在しません。 それが私たちに与えるものを理解してみましょう。
sum = SおよびS <lの要素のサブシーケンスを選択しましょう。 この場合、サブシーケンスの要素の1つを、私たちが選択していない他の要素に置き換えると、新しい合計S '≤uになります。 可能な最大数だけ合計を増やす場合は、最小要素を最大要素で置き換え、条件u-l wmax≥wminに従います。
この事実を武器に、解決策に直接進みます。 まず、w配列を並べ替えて、作業しやすいようにします。 問題を2つのポイントに分けます。
- L-正解内の要素の数を決定するか、存在しないと言います。
- 合計が[l、u]にあるL個の要素を見つける
最初に、2番目の段落を理解します。 回答が存在し、L個の要素が含まれていることをお知らせください。 ソートされたwの最初のL要素を取得します。 答えが存在することに同意したため、それらの合計は正確に≤uです。 ここで、次のアルゴリズムを実行します。
現在の金額が下限以上の場合、アルゴリズムを終了します
選択した要素の最小値を、まだ選択していない要素の最大値に置き換えます。 そのような置換で量が増えない場合は、アルゴリズムを実行せずに完了します。
（1）により、上限を超えないことに注意してください。 なぜこのアルゴリズムが確実に答えを見つけるのですか？ 反対を仮定します。
各反復で、アルゴリズムはサンプルの最小要素を選択されていないものの最大要素に変更します。 そのような要素が私たちのものよりも小さい場合、これは最後の要素wをL個選択したことを意味します。 最大要素の合計Lがlより小さい場合、長さLの適切なサブシーケンスは存在しませんが、反対に同意しました。 論争。
バランスのとれた検索ツリーの組み込みC ++実装を使用して、同様のアルゴリズムをすばやく実装できます。 最悪の場合のアルゴリズムの反復回数：n、このような解の漸近的な振る舞いはO（n log n）になります。
問題解決の最初の段階、つまり適切なLの検索に戻ります。それぞれをチェックして、Oの漸近的な動作（n2 log n）を取得できますが、動作が長すぎます。
最初のi要素の合計がuより大きくなるような長さiを見つけましょう。 そのような長さが存在しない場合、i = n + 1であると想定します。すべての長さから最小値を取ります。 正解が存在する場合、i-1要素が含まれると主張します。 もちろん、他の回答もありますが、そのうちの1つには非常に多くの要素が含まれます。 この声明を証明しましょう。
L = i-1、またはiが存在しない場合はL = nとする。 L <iであるため、最初のL要素の合計≤u。 上記のサブシーケンス検索アルゴリズムを実行します。 彼が答えを見つけた場合、私たちの声明は真実です。 それ以外の場合、最後のL要素の合計<l。 この場合、L未満の長さに対しても答えは存在しません。L個の最大値が取得されたという理由だけで、それより少ない数もl未満になります。 また、最初のi要素の合計がuより大きいため、Lより長いすべての長さに対して答えは存在しません。 したがって、答えはまったく存在しません。
合計すると、O（n）で必要な長さを見つけ、O（n log n）で長さの答えを見つけることができます。 したがって、アルゴリズム全体の実行時間はO（n log n）になり、100ポイントを穏やかに獲得します。
ソリューションソースコード
#include <アルゴリズム>
#include <ベクトル>
#include <セット>
#include "molecules.h" //グレーダーファイルを含む
ll = long long を使用し ます。 //時間を節約するための小さなエイリアス。
名前空間 std を使用し ます 。
vector < int > find_subset （ int l、 int u、vector < int > w ） {
int n = w。 サイズ （ ） ;
ベクトル<ペア< int 、 int >> weight （ n ） ;
for （ int i = 0 ; i < n ; i ++ ） {
weight [ i ] = { w [ i ] 、i } ; //出力の初期インデックスを保存します。
}
sort （ weight。begin （ ） 、weight。end （ ） ） ;
ll cur_sum = 0 ;
int bad_i ;
for （ bad_i = 0 ; bad_i < n ; bad_i ++ ） { //最初の不正な長さを見つける
cur_sum + =重量[ bad_i ] 。 最初 ;
if （ cur_sum > u ）
休憩 ;
}
if （ bad_i == 0 ） //解なし
{
return vector < int > （ ） ;
}
set < pair < int 、 int >> picked、remain ;
ll curpicked = 0 ;
for （ int i = 0 ; i < bad_i ; i ++ ） {
選んだ。 挿入 （重量[ i ] ） ;
厳選+ =重量[ i ] 。 最初 ;
}
for （ int i = bad_i ; i < n ; i ++ ） {
残ります。 挿入 （重量[ i ] ） ;
}
while （ curpicked < l && ！残ります。empty （ ） ） {
if （ picked。begin （ ） - > first > = remaining。rbegin （ ） - > first ） //スワップするものはありません
休憩 ;
//最も低い要素と最も高い要素を交換します。
選り抜き+ =残ります。 rbegin （ ） - >最初-選択されました。 begin （ ） - >最初;
auto el1 = *選択。 begin （ ） ;
auto el2 = *残ります。 rbegin （ ） ;
選んだ。 消去 （ el1 ） ;
選んだ。 挿入 （ el2 ） ;
残ります。 消去 （ el2 ） ;
}
if （ curpicked < l ） { //ソリューションなし
return vector < int > （ ） ;
}
vector < int > answer ;
for （ auto el ： picked ）
答えてください。 push_back （ el。second ） ;
返事;
}
このような問題を解決するには、深刻なトレーニングが必要です。これは、 School of Programmersで取得できます。 今年、ShPはモスクワ支社の近くにあるITパークであるPhysTechParkに新しい支店を開設しました。 トレーニングプログラムは、Yandexの部門と同じように複雑で、高レベルおよび低レベルの言語、離散数学、アルゴリズム、データ構造、ネットワーク、OSなどの研究が含まれます。
2016/17年度のセットは、2016年10月8日14:00に開催される試験の結果に応じて、6〜10年生の生徒に対して実施されます。 試験に登録し、 こちらのオンライン準備コースを受講してください 。
プログラマースクールにはオンライン部門もあります。 レッスンはウェビナー形式で行われ、13歳からロシア全土の学生が受け入れられます。 次の入学試験は、10月15日17:00に開催されます。 オンラインプログラマースクールで試験に登録し、 こちらの準備コースを受講してください 。
