国際情報学IOI 2016からの問題の分析

今年の8月、カザンは学童向けの国際プログラミングオリンピック-IOI 2016を開催しました。ロシアのチームは、総合ランキングで2番目になりました 。

銀メダリストの一人、MytishchiのDenis Solonkovは、 「分子の検出」タスクの分析を行いました。これは、オリンピアードの参加者に提供されました。

デニス・ソロンコフは、オールロシアンプログラミングオリンピックの複数勝者であり、現在はHSEの学生であるプログラマースクールの卒業生であるモスクワCTFスクールです。

デニスの教師の一人として、私は彼にIOI 2016でタスク分析を行うように頼みました。

タスク条件

ピーターは、分子を検出するデバイスを作成した会社で働いています。 各分子は、全体的に正の重量を持っています。 デバイスは、検出間隔[l、u]によって特徴付けられます。ここで、lとuは正の整数です。 このセットに含まれる分子の総重量がデバイスの検出間隔に属するサブセットが含まれている場合にのみ、デバイスは多くの分子を検出できます。

デニスのソリューション

タスクはすでに十分に形式化されています。 長さ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に開催されます。 オンラインプログラマースクールで試験に登録し、 こちらの準備コースを受講してください 。