みなさんこんにちは！ 9月に、国際プログラミングオリンピアード、IOI 2012が開催され、ロシアチームは、ご覧のとおり非常に成功しました。
私はマックス・アフメドフです。 私は、そのような競争とは何か、私たちが解決しなければならない課題を一般に公開するよう提案されました。 「Jousting Tournament」の第2ラウンドの最後のタスクについてお話します。 条件の英語版はこちらにあります 。 ちなみに、これはその日の3つのタスクの中で最も単純なものです:-)
凡例
仕事は、1491年に行われたミラノの知事であるロドヴィコスフォルツァ公爵とベアトリスデステ公爵夫人の婚約式です。トーナメント。
そして、お祭りの始まりまでに、遅刻したがトーナメントを妨害するほどではない人を除いて、すべての騎士が時間通りに到着したことが判明しました。 偶然にも、この騎士は群衆のお気に入りであり、彼の参加によるすべての戦いは非常に人気がありました。 レオナルドはトーナメントの戦いのスケジュールと騎士がどのように参加するかを知っており、好きな騎士ができるだけ多くの戦いに参加できるようにトーナメントのコースに少し影響を与えたいと考えています。 そのため、PRなPRマネージャーのレオナルドは、イベントの重要性を高めようとしています。
このような刺激的な物語。
正式な条件
ナイトリートーナメントは次のとおりです。 行には多くの騎士がいます。 次の各戦闘の前に、ジャッジが出て、連続したセグメントを形成する位置に立つ騎士を決闘に招集し、その結果、勝者が決定されます。 勝者は自分の場所に戻り、負けた騎士は脱落します。 この後、多くの騎士が動き、空きスペースを取ります。 より正式には：N人の騎士が並んでおり、裁判官は2つの数字lとrを指名します。その後、左から右への番号順にlからrまでの場所を占める騎士が戦い、勝者だけが列に残ります。 その後、トーナメントの勝者として宣言された騎士が一人だけ残るまで、同じ原則で後続の戦いが行われます。
現時点では、後半の1を除くすべてのN-1騎士はすでに列に並んでいます。 レオナルドには、好きなものを最初または最後を含め、列のどこにでも到着する機会があります。 戦闘の順序とそれに参加する騎士の位置はすでに決まっています。 レオナルドは、各騎士について、0からN-1の整数で表される抽象的な「力」の値を知っています。このタスクの一部として、特定の騎士が参加する戦いで、最も重要なものが勝つと考えられています強さ。 トーナメントでは、すべての騎士の強さが異なります。つまり、どの戦闘でも勝者はその意味の知識に基づいて明確に決定されます。 レオナルドは、トーナメントの結果に応じて、観客のお気に入りが勝った戦いの数ができるだけ多くなり、そのような結果につながるすべてのポジションから、一番左のものを選択したいと考えています。 注意：ナイトがトーナメント全体の勝者になる必要はありません！ 彼が勝利を収めた戦闘の数を最大化するのに十分です。
例を見てみましょう。 5人の騎士がトーナメントに参加できるようにします。 列に並んでいる時間厳守の騎士は、左から右に見たときにパワー値[1、0、2、4]を持ちます。 ご覧のとおり、レイトナイトの強さは3です。たとえば、トーナメントが3ラウンドで構成されており、位置（2、4）、（1、2）、および（1、2）で特徴付けられているとします。 これが何を意味するのかを説明しましょう。
- 最初の騎士は、左から2番目から左から4番目までの場所に立って戦っています。
- 残りの2番目の騎士では、最初の左に立って左の2番目の場所にいる2人が戦います。
- 最後のラウンドでは、残りの2人の騎士が出会って、1人目が左側、2人目が左側になります。
このようなトーナメントは、ツリー形式でより明確に表示できます。
さらに、ところで、同様のツリーに戻ります。
たとえば、レオナルドが他のすべての騎士の左にお気に入りを置いた場合、トーナメントの写真がどのように見えるかを理解します。 最初は、騎士の力の値は左から右に[3、1、0、2、4]のように見えます。
- 最初のラウンドでは、パワー1、0、2の騎士が戦い、勝者はパワー2の騎士となり、彼は自分の場所に戻り、列は[3、2、4]のようになります。
- 第2ラウンドでは、私たちのお気に入りは力3で、騎士は力2で戦うでしょう。観衆のお気に入りは勝利して出て、彼は戻り、列は[3、4]のようになります。
- 最後のラウンドでは、私たちのお気に入りは、トーナメントの勝者になる力4の騎士に負けます。
したがって、私たちの騎士は、引退する前に1試合だけ勝ちます。 最善の解決策は、ランク1と0の騎士の間の位置に彼を置き、一連の[1、3、0、2、4]を形成することです。
- 最初のラウンドでは、彼は0と2の部隊の騎士との戦いに参加し、そこから勝利します。 多くの騎士の形は現在[1、3、4]です。
- 第2ラウンドでは、彼は敗北する強さ1の騎士と戦う。
- 第3ラウンドでは、彼はフォース4でトーナメントの勝者にも負けます。
その結果、お気に入りは2つの戦いに勝ちます。
彼はすでに1ラウンドを除くすべてのラウンドに勝利しているため、これ以上の戦いに勝つことはできません。また、トーナメントの勝者になることが保証されている彼よりも強い騎士（ランク4）があるため、すべてに勝つことはできません。 つまり、最初の2人の騎士の間の位置は、レオナルドが必要とする位置であり、これが問題の答えです。
プログラムが受け取るポイントの数は、決定の有効性によって異なります。 騎士の数が500を超えない状況で1秒間に正解を受け取るのに十分な速さで動作する場合、ソリューションは100のうち17ポイントを受け取ります。5000に達する騎士の数で正解を計算できた場合、49と推定されます。ポイント。 フルスコアを獲得するには、最大10万人の騎士を含むトーナメントを処理する時間が必要です。 私たちのチームでは、4人全員が100ポイントを獲得したソリューションを作成しました。タスクはラウンドで最も簡単でした。
額の決定
この問題に対する最も簡単な解決策は、レイトナイトのN個の可能な位置のそれぞれを明示的にチェックし、それらから最も有利な位置を見つけることです。 ソリューションの唯一の技術的なポイントは、騎士の初期位置を使用したトーナメントのシミュレーションです。 これを非常に単純に行うことができます。たとえば、リスト内の多数の騎士を左から右へ、そして次の各ラウンドでサポートするには、戦闘する騎士を選択し、それらから最も強い騎士を見つけ、彼を戻し、騎士をシフトして空の場所を埋めます。
このような決定は、騎士の数が500人を超えない最初のテストグループに合格する必要があります。 プログラムによって実行される操作の数の順序を計算することにより、どれだけ機能するかを推定しましょう。 各ラウンドで、最悪の場合のシナリオでは、ほとんどすべてのナイトを左に移動して、空のスペースを埋める必要があります。つまり、シリーズの長さに比例する操作の数の最悪の場合のプロセスの1つのラウンドプログラムは、大まかに言えば、N / 2のナイトで構成されます。 最悪の場合のトーナメントでのラウンドはN-1に達する可能性がありますが、レイトナイトのすべての可能なポジションについて、可能な限りNのトーナメントを奨励する必要があります。 ナイトの数Nに対してプログラムによって実行される単純な操作の数に対する依存性N ^ 3/2が判明します。
ところで、現代のコンピューターは、1秒間に約4億から5億の簡単な操作を完了することができます。 N = 500のソリューションの複雑さは約6,200万の単純な操作と推定されたため、時間制限に余裕をもって収まることが期待できます。 確かに、このソリューションを作成することで、17ポイントを獲得することができます。これは、そのようなソリューションがタスクのデバッグとテストをさらに進める上で役立つ場合にのみ有用です。
もっと深くする必要がある
ソリューションが5000ナイトのテストで1秒以内に機能するためには、アルゴリズムの立方体の複雑さはもはや適切ではありません-複雑さの推定値を少なくとも2乗Nに比例するように減らす必要があります。そのような場合、 O-big用語がしばしば使用されます： N ^ 2）。
上記の複雑度評価の3つの要因Nの1つを削除する必要があります。 外部を取り除く方法-遅いナイトの位置を整理する-はまだ非常に明確ではありません。 それでは、トーナメントシミュレーションの有効性を高めましょう。 ラウンドの数から逃れることはできないようです。したがって、1回の戦闘の実行をより効率的にする必要があります。 すべての騎士を移動して空のスペースを埋めるのは非常に非効率的です。配列は分割不可能な断片としてメモリ内にあり、彼の位置によって騎士にすばやく移動したいので、これから逃げることはできません。 ストレージの構造を何らかの形で変更する必要があります。
1つの解決策は、短時間でセグメントをカットできるナイトの配列ではなく、何らかの構造を使用することです。 しかし、これらの構造のほとんどはO（log N）のときよりも速く動作せず、O（N ^ 2 log N）の複雑さは非常に危険であるため、この方法は非常に疑わしいです。時間制限。
あまりにも多くの不必要な操作を行っているという事実があります-何らかの理由で、明示的な形式でナイトの位置をサポートします。 トーナメントツリーのようなものを思い出すと、それをすべての戦闘の迅速な実施に使用する方法が明らかになります。 ある頂点に対応するラウンドを実行する必要がある場合は、子の頂点に対応するラウンドを実行し、これらのラウンドの勝者から最も強いものを選択するだけで十分です。 これは、たとえばトーナメントツリーを詳細に走査するときに行われます。 したがって、トーナメントツリーがある場合、すべてのバトルを線形時間O（N）で実行できます。 外では、私たちがお気に入りを置く位置を整理する必要があり、O（N）の複雑さもあります。 これは、O（N ^ 2）に対してこのツリーの下で実際の回答の検索を実行できることを意味します。
このツリーを構築する方法を学ぶことだけが残っています。 二次的な時間であっても一度それを構築し、それを使用すれば十分です。 これは、ナイーブな決定でラウンドを行った方法との類推によって行うことができます。ナイトの強さの値の代わりに、これらの場所で勝ったナイトに対応するトーナメントツリーの頂点を行に格納します。 各ラウンドでは、このラウンドに参加しているナイトピークが立つサブラインを選択し、代わりに新しいサブセグメント、すべての親である頂点を設定します。
したがって、トーナメントツリーを構築するためにO（N ^ 2）メモリを必要とし、その答えを見つけるためにO（N ^ 2）を必要とするソリューションを考え出しました。 N <= 5000のこのようなソリューションは、時間に余裕を持って進み、49ポイントを獲得する必要があります。
ソリューションをフルスコアにポンプで送ります
ソリューションをさらに改善しましょう。 配列の代わりに、サブラインをすばやくカットできるデータ構造にトーナメントツリーの頂点を格納すると、ツリーの構築を時間内に最適化できます（配列でできるように、O（N）よりも高速です）。 このような便利なデータ構造の例は、暗黙的なキーによるデカルトツリーです。これは、かつてHabréで説明されていたもので、たとえばここで読むことができます 。 結果として、トーナメントツリー構築の実装は、シリーズのナイトピークの表現とそれらの操作方法が変わることを除いて、ほぼ同じままです。 したがって、ソリューションの最初の部分はO（N log N）に最適化されます。
2番目の部分を最適化するには、唯一のお気に入りの動きが、原則としてトーナメントの結果にあまり影響を与えないことを理解する必要があります。 たとえば、後発者が最初に立つ場所では、トーナメント全体の勝者は決して変わりません。いずれにしても、それは最大の強さを持つ騎士になります。
さらに議論しましょう-トーナメントツリーのトップで勝者は誰ですか？ これが、このピークに対応するサブツリーで最も強い騎士であることは十分に明らかです。 これは非常に有用な考慮事項です。たとえば、理論上、あるピークでお気に入りが理論上勝者になる場合を理解できます。このため、このサブツリーに彼よりも強い騎士がいないことが必要かつ十分です。 そして、ピークのサブツリーとは何ですか？ これは、定刻の騎士がすでに立っているシリーズのセグメントです。たとえば、そのようなデータ構造をセグメントのツリーとして使用して、最強の騎士を見つけることができます。
そのため、トーナメントツリーの各頂点について、お気に入りが含まれているかどうかを判断できます。 そして、もし彼がそこにいることができるなら、このツリーでのパスができるだけ長くなるような位置に彼を置くことが最も有利です：パス上の各頂点は、お気に入りが訪れたある種の戦いですが、まさに私たちにとってはそうです戦闘の数。タスクの条件に応じて最大化する必要があります。 したがって、最も深い葉を含む頂点（つまり、「子供」を持たないツリーの最上部-この頂点は騎士のある位置に対応する）を選択し、この葉を答えとして選択することは、お気に入りの利用可能なすべての頂点からのみです。 。
したがって、ソリューションの2番目の部分もO（N log N）に最適化されました。 N <= 100000の場合、このような複雑さを持つソリューションは原則として制限時間内になります。このタスクも例外ではありません。 実際、このような決定を（わずかな逸脱を伴って）実施したことで、私たち4人は満点を獲得しました。
これらはパイです
私たちはオリンピアードでそのようなオペラのようなことをしています-これは、さまざまな解決策と多くの論理的なレンガを備えた国際的なオリンピアードからの多方面の深刻な仕事の典型的な例です。 プログラミングの目的が少し明確になり、メダルを獲得できることを願っています:-)またね！