興味のある人には知られているように、1か月以上前に、学生のオンラインスポーツプログラミングオリンピックであるABBYYカップが開催されました。 それについて何も聞いたことがない人のために、 まずこのトピックを読むことをお勧めします。
各ラウンドで参加者に6つのタスクを提供し、各タスクは100ポイントを獲得できましたが、軽量部門の場合、軽量部門が非常に簡単に思える参加者を楽しませるために、コードフォースはさらに7番目を構成しました。
昨年と同様に、さまざまな難易度の自動テストを使用して決定が評価されました。 ABBYYカップには、軽量部門に2つ、難しい部門に3つのテストグループがありました。 タスクをうまくやった人と非常によくやった人とを区別するには、さまざまなテストが必要です。 コードは、20の入力値を持つ特定のフレームワークで機能しましたか？ 入り口で50を取得、見てみましょう:)
さらに、追加の評価システムがありました。 人が何度も問題を解決しようとし、たとえば10倍の間違った解決策を送信し、11日に正しい解答を送信した場合、その人はより長く解決した人よりも評価が低くなりますが、すぐにすべてのテストに合格した解決策を送信します。
代表的なサンプル
タスク条件
ABBYYのClever Beaverは、細胞学および遺伝学研究所と長い間協力しています。 最近、この研究所の従業員はビーバーに新しい仕事を提供しました。 問題の本質は次のとおりです。
n個のタンパク質のセットがあります（必ずしも異なるとは限りません）。 各リスは、ラテンアルファベットの小さな文字で構成される文字列です。 スマートビーバーの科学者が提起する課題は、元のタンパク質のセットからパワーkのサブセットを選択することであり、選択したタンパク質のサブセットの代表性は最大でなければなりません。
ABBYYのClever Beaverは小さな調査を実施し、一連のタンパク質の代表性を1つの数値で評価できるという結論に達しました。これは計算が非常に簡単です。 タンパク質を記述するk行の{ a 1 、...、 a k }のセットがあるとします。 このセットの代表性は次の量です。
ここで、 f （ x 、 y ）は、行xとyの最大共通プレフィックスの長さです。 たとえば、 f （ "abc"、 "abd"）= 2およびf （ "ab"、 "bcd"）= 0です。したがって、タンパク質のセット{"abc"、 "abd"、 "abe"}の代表性は6です。 、セット{"aaa"、 "ba"、 "ba"}-2。
この発見後、ABBYY Clever Beaverは、カップの参加者に、可能な限り最高の代表性を持つ特定のタンパク質セットからパワーkのサブセットを選択するプログラムを作成するよう依頼しました。 彼がこの問題を解決するのを助けてください！
n個のタンパク質のセットがあります（必ずしも異なるとは限りません）。 各リスは、ラテンアルファベットの小さな文字で構成される文字列です。 スマートビーバーの科学者が提起する課題は、元のタンパク質のセットからパワーkのサブセットを選択することであり、選択したタンパク質のサブセットの代表性は最大でなければなりません。
ABBYYのClever Beaverは小さな調査を実施し、一連のタンパク質の代表性を1つの数値で評価できるという結論に達しました。これは計算が非常に簡単です。 タンパク質を記述するk行の{ a 1 、...、 a k }のセットがあるとします。 このセットの代表性は次の量です。
ここで、 f （ x 、 y ）は、行xとyの最大共通プレフィックスの長さです。 たとえば、 f （ "abc"、 "abd"）= 2およびf （ "ab"、 "bcd"）= 0です。したがって、タンパク質のセット{"abc"、 "abd"、 "abe"}の代表性は6です。 、セット{"aaa"、 "ba"、 "ba"}-2。
この発見後、ABBYY Clever Beaverは、カップの参加者に、可能な限り最高の代表性を持つ特定のタンパク質セットからパワーkのサブセットを選択するプログラムを作成するよう依頼しました。 彼がこの問題を解決するのを助けてください！
タスク解析
問題の完全な解決策にすぐに進みます。 行を辞書式にソートして、 lcp [ i ]-行iおよびi + 1の最大共通プレフィックスの長さを計算しましょう。任意の2行iおよびjの最大共通プレフィックスがmin （ lcp [ i ]、 lcp [ i + 1] 、...、 lcp [ j -1]）（接尾辞配列を使用する場合、同様のステートメントが使用されます）。 これは役に立ちます。
次に、動的計画法を適用します。 このようなDPを作成します： F （ i 、 j 、 k ）は、番号i ... jの行から正確にk行を選択する場合の問題に対する可能な最大の答えです。 遷移は次のとおりです。最小lcp [ p ]を持つセグメントi ... j -1の位置pを見つけ、次にF （ i 、 j 、 k ）= max q = 0 ... k （ F （ i 、 p 、 q ）+ F （ p + 1、 j 、 k - q ）+ q・（ k - q ）・lcp [ p ]）つまり、 qは i ... pの行から選択され、 k - qはp + 1 ... jの行から選択され、これらの行のすべてのペアの中で、最大の共通プレフィックスの長さはlcp [ p ]です（これは最初の段落のステートメントに続く）。
このような決定は、50ポイントを獲得するのに十分です。 これまでのところ、このソリューションの複雑さはO （ N 4 ）程度であるようです。 複雑さがO （ N 2 ）になるようにこのソリューションを実際に実装することが実際に可能であることを示すために残ります。最初に、関数Fの値に関心があるさまざまなセグメントi ... jが実際に正確に2 Nであることに注意してください- 1、 O （ N 2 ）ではありません。 これがなぜそうなのかは、DPの移行から理解できます。 セグメント1 ... Nは 2つのセグメント1 ... pおよびp + 1 ... Nに分割され、これらの各セグメントはさらに2つのセグメントに分割されます。 DPの計算全体で、 iの位置iとi + 1の間に1回だけ「カット」があり、このカットにより、DPの値に関心のある2つの新しいセグメントが生成されることがわかります。 ここから、必要なセグメントの2 N -1の推定値を取得します。したがって、このソリューションはすでにO （ N 3 ）以下の複雑さしかありません。
最後の最も難しいことは、上記のソリューションが複雑度O （ N 2 ）を持つ可能性があることを推測することです。 たとえば、次のように実装できます。 長さj - i + 2の配列を返す再帰関数F （ i 、 j ）を取得しましょう-実際にはDP値F （ i 、 j 、 k ）（0からj - i + 1の区間のkの値のみに関心があることは明らかです） この関数内で、以下を実行します： pを見つけ、 F （ i 、 p ）およびF （ p + 1、 j ）を呼び出し、 xを0からp - i + 1に繰り返し、 yを0からj - pに繰り返し、値Fを更新します（ i 、 j 、 x + y ）、改善された場合（著者のソリューションで詳細を確認できます。すべてがそこにあります）。 長さj - i + 1 = Nの区間i ... jで呼び出される関数Fの最大動作時間は、 T （ N ）= max X = 1 .. N -1 （ T （ X ）+ T （ N - X ） +（ X + 1）・（ N - X + 1））。 T （ N ）= O （ N 2 ）であることを理解する必要があります。 これは、たとえば、 Tを計算する単純なDPを記述することで実行できます。 考えてみれば、このように理解できます： x = 0 ... p - i + 1およびy = 0 ... j - pをループするとき 、2、3行をソートすると想像してみましょう： x = i ... pおよびy = p + 1 ... j （ここで、 xとyを反復処理すると、1回の反復処理が少なくなりますが、これは重要ではありません）; 次に、DPの計算全体の行の各ペアが1回だけソートされ、最終的な複雑度O （ N 2 ）が得られます。
ここで著者のソリューションを見つけることができます。
多くの参加者がホウ素を使用したソリューションに合格しました。 このようなソリューションはO （ N 2 ）の複雑さも持つ可能性がありますが、長持ちし、より多くのメモリを使用します。 それにもかかわらず、時間とメモリの制限は異なるソリューションに非常に忠実でした:)
次に、動的計画法を適用します。 このようなDPを作成します： F （ i 、 j 、 k ）は、番号i ... jの行から正確にk行を選択する場合の問題に対する可能な最大の答えです。 遷移は次のとおりです。最小lcp [ p ]を持つセグメントi ... j -1の位置pを見つけ、次にF （ i 、 j 、 k ）= max q = 0 ... k （ F （ i 、 p 、 q ）+ F （ p + 1、 j 、 k - q ）+ q・（ k - q ）・lcp [ p ]）つまり、 qは i ... pの行から選択され、 k - qはp + 1 ... jの行から選択され、これらの行のすべてのペアの中で、最大の共通プレフィックスの長さはlcp [ p ]です（これは最初の段落のステートメントに続く）。
このような決定は、50ポイントを獲得するのに十分です。 これまでのところ、このソリューションの複雑さはO （ N 4 ）程度であるようです。 複雑さがO （ N 2 ）になるようにこのソリューションを実際に実装することが実際に可能であることを示すために残ります。最初に、関数Fの値に関心があるさまざまなセグメントi ... jが実際に正確に2 Nであることに注意してください- 1、 O （ N 2 ）ではありません。 これがなぜそうなのかは、DPの移行から理解できます。 セグメント1 ... Nは 2つのセグメント1 ... pおよびp + 1 ... Nに分割され、これらの各セグメントはさらに2つのセグメントに分割されます。 DPの計算全体で、 iの位置iとi + 1の間に1回だけ「カット」があり、このカットにより、DPの値に関心のある2つの新しいセグメントが生成されることがわかります。 ここから、必要なセグメントの2 N -1の推定値を取得します。したがって、このソリューションはすでにO （ N 3 ）以下の複雑さしかありません。
最後の最も難しいことは、上記のソリューションが複雑度O （ N 2 ）を持つ可能性があることを推測することです。 たとえば、次のように実装できます。 長さj - i + 2の配列を返す再帰関数F （ i 、 j ）を取得しましょう-実際にはDP値F （ i 、 j 、 k ）（0からj - i + 1の区間のkの値のみに関心があることは明らかです） この関数内で、以下を実行します： pを見つけ、 F （ i 、 p ）およびF （ p + 1、 j ）を呼び出し、 xを0からp - i + 1に繰り返し、 yを0からj - pに繰り返し、値Fを更新します（ i 、 j 、 x + y ）、改善された場合（著者のソリューションで詳細を確認できます。すべてがそこにあります）。 長さj - i + 1 = Nの区間i ... jで呼び出される関数Fの最大動作時間は、 T （ N ）= max X = 1 .. N -1 （ T （ X ）+ T （ N - X ） +（ X + 1）・（ N - X + 1））。 T （ N ）= O （ N 2 ）であることを理解する必要があります。 これは、たとえば、 Tを計算する単純なDPを記述することで実行できます。 考えてみれば、このように理解できます： x = 0 ... p - i + 1およびy = 0 ... j - pをループするとき 、2、3行をソートすると想像してみましょう： x = i ... pおよびy = p + 1 ... j （ここで、 xとyを反復処理すると、1回の反復処理が少なくなりますが、これは重要ではありません）; 次に、DPの計算全体の行の各ペアが1回だけソートされ、最終的な複雑度O （ N 2 ）が得られます。
ここで著者のソリューションを見つけることができます。
多くの参加者がホウ素を使用したソリューションに合格しました。 このようなソリューションはO （ N 2 ）の複雑さも持つ可能性がありますが、長持ちし、より多くのメモリを使用します。 それにもかかわらず、時間とメモリの制限は異なるソリューションに非常に忠実でした:)
Codeforcesのすべてのタスクを見ることができます： 軽い部門 、 軽い部門 のタスクの分析 、 難しい部門 、 難しい部門 のタスクの分析 。
一般的に、私たちの同僚は、ABBYYカップの参加者のレベルが高いことに注目しています。 複雑な部門では、6つの問題すべてが10人で解決されました。これは非常に多くのことです。 参加者の適切な準備は、非公式の順位（学生だけでなく学童にも参加することができました）では、5人の指導者が学生を含むという事実によって示されています-学生のための全ロシアプログラミングオリンピックの勝者。
レビューから判断すると、ほとんどの参加者は私たちの問題を解決するのが好きで、 ヒューリスティックな認識タスクは特に興味深いものでした。 さて、来年、私たちの同僚は確かに同じ精神で何か面白いものを準備します。 昨年と同様、7月上旬にABBYYカップの参加者が私たちのオフィスに来ます。リクエストに応じて、今度はフルタイムのコンテストをもう1つ開催します。