先週の土曜日、6月16日、ロシアコードカップ2012の予選ラウンドは終了しました。予選ラウンドのタスクは予選よりも複雑です-それが準決勝の理由です。 私はすでに、以前のオンラインツアーで参加者に提供されたものについて話し、ソリューションオプション（ Q1 、 Q2 、 Q3 ）を詳細に分析しました。



600名が予選に招待されました。 434人が少なくとも1つの問題を解決できました。 すべてのタスクは2人で解決されました。 最高の50人が決勝に進出しました。 ツアーのわずか3時間で、3190のソリューションがテストシステムに送信されました。



それでは、タスク自体に移りましょう。 私はそれらを説明しようとしたので、スポーツプログラミングの最初の一歩を踏み出す人たち（そして実際にはプログラミング全般）でも決定が明確になるようにした。

終了

問題の本質は、2種類の順列を任意の順序で適用することにより、値のリスト内の指定された位置から指定された位置に要素を移動できるかどうかを判断することでした。 問題の状態により、最初の2つの要素を交換するいわゆる順列と、値のルールセット（a1、a2、...、aN）によって定義される複雑な順列を適用することができました。各値は、移動可能な位置のシリアル番号を決定します。この位置からの番号。 たとえば、順列規則の最後の2つ（1,4,3,2）は、最後の位置から2番目に再配置でき、それから最後に再配置できることを意味します。 実際には、最後に、このリスト（N個の値）とフォーム（位置1、位置2）を含む入力データに「はい/いいえ」という形式の回答を与える必要があります-「要素を位置1から位置2に移動できますか」。



このタスクはコンテストで最も簡単で、411人がそれに対処しました。最初のテストは、ラウンドの開始から3分31秒でDmitry Zhukovによって提案されました。



明らかに、すべての順列は最終的に一連のループになります。 上記のサイクル3の例では、4-> 2-> 4-> 2 ... 1-> 1-> 1 ... 3-> 3-> 3 ...つまり、「pを適用する」という操作だけがあった場合、 2つの要素aiとbiについては、これらの要素が順列pの1サイクルにある場合に限り、答えは「はい」になります。



「順列」zを適用するとどうなるか考えてみましょう。 最初に1番目と2番目の要素が異なるサイクルにある場合、「順列」を使用すると、これら2つのサイクルの1つから別の要素に要素を再配置する機会が与えられます。



これで、一般的なソリューションを定式化できます。

• 順列p全体をサイクルに分割します。
• aiとbiのそれぞれについて、aiとbiが同じサイクルにある場合、または最初の要素が一方のサイクルにあり、2番目の要素が他方のサイクルにある場合、答えは「はい」です。

サイクルへの分割は次のとおりです。

//    col,   −1. vector<int> col(n, −1); //    ,    ,       for (int i = 0; i < n; i++) { if (col[i] != −1) continue; //     int x = i; do { col[x] = i; //    x = a[x]; } while (col[x] == −1); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初の2つのサイクルを1つに結合します。

 for (int i = 0; i < n; i++) if (col[i] == 0) col[i] = 1;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その結果、colの配列が得られ、そのi番目の要素はi番目の位置を含むサイクルを示します。

 for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; //  ,          . cout << ((col[a — 1] == col[b — 1])? «Yes» : «No») << «\n»; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Cor冠式

問題の状況に応じて、2つの首都と特定の数の都市があり、道路で接続されているため、どの道路からでも唯一の道路があります。 しかし、それらは、各道路に示されている特定の数の車を通過した後、旅行に適さないほどの品質です。 2つの都市の間に帯域幅が無制限の別の（おそらく重複する）道路を追加することが決定されました。 この新しい道路を考慮して、2つの首都間を走行できる車の最大数を見つける必要があります。



問題の詳細な声明は、ロシアコードカップの公式ウェブサイトのラウンドページにあります 。



このタスクは、「最後から」2番目に難しいことが判明しました。313人が解決しました。 最初の正しい決定は、12：50にDmitry Zhukovによって送信されました。



問題には、重みのある無向ツリーがあります。 つまり、ループと複数のエッジがなく、そのエッジ（「道路」）が「重み」で書かれているグラフ-道路のスループット。



2つのピークが強調表示されます-「資本」-sおよびt。 sからtへのフローが最大になるように、sまたはtに影響しないエッジを追加する必要があります。



頂点aから頂点bにエッジを追加しましょう。 sとtの間に最大2つの単純なパスが存在することを証明しましょう（パスは、そのエッジが繰り返されない場合、単純と呼ばれます）。 私たちは反対から証明します。 3つの方法を見つけたとします。



次の2つの場合を考えます。

• そのうちの少なくとも2つには、エッジabがあります。 ここにも2つのケースがあります。
  
  
  • リブは両方の方向で一方向にコストがかかります。 方向a-> bのいずれかを取ると、考慮される両方のパスにサブパス<sが含まれます。 a; b; t>。 これらのパスは等しくないため、サブパス<sは等しくありません。 a>、または<b; t>。 どちらの場合も、これは、ツリーの頂点間に2つの異なるパスがあることを意味します。これは、そのプロパティと問題の状態に矛盾します。
  • リブは反対方向に進みます。 その場合、ツリーのサイクルは<sです。 a; t; b; s>は、問題の状態とツリーのプロパティとも矛盾します。
• エッジabはそのうちの1つだけにあります。 次に、残りの2つのパスがサイクルを形成し、したがって、ツリー内の単純なサイクルを形成しますが、これは問題の条件によるものではありません。

その結果、エッジabを追加すると、2つ以下の単純なパスが表示され、そのうちの1つだけがエッジabを持ち、もう1つは明らかにツリーのエッジに沿って通過するため、頂点都市間の唯一のパスであることがわかりました。



エッジabを通る2番目のパスを考えます。 一端では、このエッジは頂点sへのパスに接続され、他端では頂点tへのパスに接続されます。 ここで、abと<s; a>のジャンクションをsに近いノードに移動しても、スループットは低下しません。 同様にtへの道について議論し、問題の制約を思い出して、資本ノードs、t、およびエッジabを最も効果的な形で通過する新しいパスは、sからのエッジ、sからabおよびtからのエッジ。



その結果、答えは2つのパスで構成され、1つはエッジabを追加する前に存在し、もう1つはsからのエッジ、エッジab、tのエッジであることがわかります。



ソリューションを取得します。

1. ツリーのエッジに沿ってsからtへのパスを見つけ、
2. それに沿って車の最大数をスキップし、それに応じて、道に沿ってすべてのrib骨のスループットを減らします。 この場合、最大数のマシンがパスに含まれるエッジの最小スループットに対応するため、パスは間違いなく崩壊します。
3. sとtからより多くの道路（または1つの道路）が存在する可能性があります。 最大スループットを持つものを選択します。
4. それらをエッジabで接続して、車の数を計算します。これは、首都を離れる2つのrib骨のスループットからの最小値です。

ソシオフォベ

問題の条件は、最小限の削減でここにもたらすことです。

「すべての人が常に群衆の中にいることを喜んでいるわけではありません。 多くの人が孤独を愛し、その代価を払っても構わないと思っています。 OJSC「Joyful Railways」がチケット販売ウェブサイトで「Sociophobe」と呼ばれる新しいサービスを導入したのはそのためです。 このサービスは、各乗客が可能な限り少ない数の隣人のいる区画に乗ることができるようにするために必要です。 その本質は次のとおりです。



チケットは、コンパートメントの一部がすでに満たされている台車で販売されます。 ある時点で別の乗客がこの車のチケットを購入すると、最も空いている区画、つまり他のすべての人よりも多くの人がいない区画で座席を販売されます。 そのようなコンパートメントが複数ある場合、最も小さい番号のコンパートメントが選択されます。 ただし、いずれかのコンパートメントの乗客がチケットを発行すると、このコンパートメントと最も満員のコンパートメントの人数の差が少なくとも2になった場合、他のコンパートメントの前にチケットを購入した乗客は、最も満員のコンパートメントから空いているコンパートメントに転送され、番号が最も小さい乗客がいます。 最もいっぱいの区画が複数ある場合、チケットが配られた区画に最も近い区画が選択されます。 そして、それらが複数ある場合、最も小さい番号のコンパートメントが選択されます。



乗客がチケットを購入して配布した方法に応じて、コンパートメント内の乗客の最終的な分布を表示する必要があります。 乗客がチケットを購入するたびに、車内に少なくとも1つの無料座席があることが保証されています。

問題の列車は本当に巨大なようです。なぜなら、チケットの販売とチケットの返却の数は最大200,000、クーペの数は最大50,000であるからです。



合計で167人がこの問題を解決しました。最初の人はPavel Kuniavsky（23:19）でした。



この問題の解決策の1つは次のとおりです。 次のデータ構造を準備します。

 // ,     . Pas[i] = , -1  «  ». vector<int> pas(200000+1, -1); //   –    . Cars[i]     vector< set<int> > cars(50000 + 1);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、2つのセットをサポートします（たとえば、C ++では、このためにJavaのTreeSetでsetを使用できます）：0と1。 ゼロでは、乗客数が最も少ないコンパートメント番号を格納し、1つでは-最も多いコンパートメント番号を格納します。

 set<int> zero; set<int> one;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初は、すべてのコンパートメントが空であるため、それらを塗りつぶしの候補リストに入れます-ゼロ。

 for (int i = 1; i <= n; i++) zero.insert(i);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

異なる区画の乗客数の差が1を超えることはないため、他の人は必要ありません。



チケット販売操作（「+」）。 問題の状況に応じて、最も人数が少ない車を選択する必要があります。 これを行うには、設定されたゼロの最小要素を取得します。 pasとcarsの情報をそれぞれ更新します。 次に、見つかった要素を0から削除して1に追加します。これは、この車にはすべての車が1つに並んでいるのと同じ数の人がいるからです。 ゼロが空になった場合、すべてのクーペは同じ人数であるため、1と0を交換する必要があります。

 int car = *zero.upper_bound(0); //    pas[++id] = car; //      cars[car].insert(id); //       zero.erase(car); //        one.insert(car); // …     if (zero.empty()) //   ,      … { zero = one; //        zero.erase(-n); zero.erase(2 * n); one.clear(); //     one.insert(-n); one.insert(2 * n); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

チケット配信操作（ "-"）。 pas配列を使用して、乗客がどのコンパートメントに座っていたかを調べます。 対応するコンパートメントから乗客を取り除きます。

 int car = pas[x]; cars[car].erase(x); pas[x] = −1;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

車のクーペに属していたものをご覧ください。 以下のオプションがあります。

• 1つのセットに属していた-「塗りつぶされたコンパートメント」。 次に、Xを1つから削除して0に追加します。つまり、コンパートメントを未入力に転送します。
• ゼロのセットに属し、1のセットは空です。 次に、すべてゼロ（充填の申請者）を1（充填済み）に転送し、乗客が出た区画のみをゼロのままにします。
• ゼロのセットに属し、1のセットは空ではありません。 これは、コンパートメントの乗客数の差が2に等しくなる状況が発生する唯一のケースです。 これを行うには、セット1で、最初のコンパートメント（番号がコンパートメントよりも大きい）と、最後のコンパートメント（番号がコンパートメントよりも小さい）を見つけます。 次に、見つかったこれら2つのクーペから、最も近いクーペを選択します。 セット1（入力済み）からセット0（「応募者」）に転送します。 また、車のクーペの配列と乗客のパスの配列の修正を行います。

 set<int>::iterator ll = (one.upper_bound(car)); ll--; //  ,    set<int>::iterator rr = (one.upper_bound(car)); //  ,    if (abs(*ll - car) > abs(*rr - car)) //        ll = rr; int l = *ll; one.erase(l); zero.insert(l); //   one  zero int p = *cars[l].upper_bound(0); cars[l].erase(p); cars[car].insert(p); //      pas[p] = car;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

タスクへの回答を表示するには、cars配列を使用します。 i番目のコンパートメントの乗客に関する情報を表示するには、セットされている車のサイズ[i]を表示するだけで十分です。

 cout << cars[i].size() << ((cars[i].size() == 0) ? "\n" : " ");
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、多くの車に属するすべての乗客[i]。

 set<int>::iterator en = cars[i].end(); en--; for (set<int>::iterator it = cars[i].begin(); it != cars[i].end(); it++) cout << *it << ((it == en) ? "\n" : " ");
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

硬貨

問題の状況に応じて、ある魔術師のリンセウィッドはコインを混同し、例えばダブロンで支払う代わりに、スターリングをカウントします（同時に、彼は本物のスターリングで支払いません）。 コインのペアがいくつあるかを計算する必要があります。そのため、最初のコインを2番目に取って、計算したとおり、SではなくTドルを正確に支払うことができます。



説明のために例を示します。 流通している1、2、3ドルの硬貨があり、Riswindが9ではなく10ドルを支払った場合、1の硬貨に対して2の硬貨を受け入れ、たとえば2の硬貨4枚と2の硬貨1枚を支払うことでこれを行うことができます彼は額面「1」のためにそれを取った。



彼はまた、2の宗派のコインに対して3の宗派のコインを受け入れ、1の宗派で7コイン、3の宗派で1コインを支払い、それを2の宗派でコインとして取りました。

実際に額面で支払われる金額1	名目値2で実際に支払われる金額	額面金額3で実際に支払われる金額	支払総額
-	ほんとに 4コイン （8ドル、4×2） 1コイン （2ドル、2×1） Riswindの見解では- 1ドル（1×1）	-	ほんとに 5コイン （10ドル、4×2 + 2×1） Riswindの見解では- 9ドル（4×2 + 1×1）
ほんとに 7コイン （7ドル、7×1）	-	ほんとに 1コイン （3ドル、3×1） Riswindの見解では- 2ドル（2×1）	ほんとに 8コイン （10ドル、4×2 + 1×1） Riswindの見解では- 9ドル（4×2 + 2×1）

Rincewindがsのコインtを取ったと仮定します。 最後の例では、コイン3（t）が2（s）です。 これは、コインs（この例では$ 7）を使用せずに特定の金額V（例では$ 10）を獲得し、その後、別のkコイン番号t（例では1コイン） 3、それが2だと思って。



つまり、さまざまなオプションが2つのケースグループに収まります。

• 整数V≥0およびk> 0があり、S = V + k・asおよびT = V + k・atです。ここで、Tは実際に支払われた金額で、SはRiswind表現の金額です。
• Vの合計は、コインsを使用せずに入力できます。

最初の条件はO（1）で検証できます。 に注意してください



k =（S-T）/（as-at）;

V = S-k



得られた数値が整数、V≥0、k> 0であることを検証することは残っています。



2番目の条件を確認するために、動的計画法を使用します。 D [i] [j]とする-最初のi個のコインを使用して合計jを取得することは可能ですか？ ベース：D [0] [0] = true。 遷移：D [i] [j] = D [i-1] [j]またはD [i] [j-ai]。 実装には、サイズSの1つの配列で十分ですが、このアルゴリズムの実行時間はO（S・n）です。 動的プログラミングを使用したアプローチの詳細な説明については、 最後のラウンドからのタスクの分析、 および例と図を含む優れた資料を参照してください。



説明した方法を使用して、Rinncewindがコインsを使用せずにこの合計を収集できたかどうかを、1からSまでの合計Vについて計算します。 その後、Rincewindが取ったコインを整理します。 これで、O（1）の両方の条件の検証が実行されます。 結果として得られる解の漸近挙動はO（S・n2）です。



「コイン」のタスクは、17：06にPeter Mitrichevによって最初に解決されました。 合計で234の正しい決定があり、このタスクは複雑さの点で最後から3番目になりました。

行解析

この問題は、特定のテキストからの語彙単語の検索アルゴリズム-発見された単語がこのテキストから削除されるたびに、いわゆる欲張りアルゴリズムについて説明します。 場合によっては、このアプローチが誤った結果につながるという例が示されています。 たとえば、workingrassの場合、workingは削除され、一部のrassがありますが、正しい解決策は、work / in / grasの3つの単語に分割し、それぞれを辞書に入れることです。 貪欲なアルゴリズムが指定された辞書で正しく機能するかどうかを確認する必要があります。正しくない場合は、辞書からの単語分割が存在するが、説明されたアルゴリズムでは見つからない文字列の例を示します。 そのような例が複数ある場合は、最も短いもの、つまり長さが他の部分より長くないものを見つける必要があります。 複数ある場合は、いずれかを印刷する必要があります。



まず、問題の解決につながる重要なアイデアを検討します。 文字列t-最短長の必要な反例と、辞書w ₁ 、w ₂ 、...、w _kからの単語への分割があるとします。 この行を調べる際に破壊しようとしている貪欲なパーサーを、文字列wを最初に「食い込ませ」ます。



次のステートメントを証明しましょう。文字列の長さwが文字列の長さw ₁ 、w ₂ 、...、w _k-1の合計よりも大きくない場合、文字列tより短い反例があります。



まず、文字列tの長さをこの合計に等しくします。 次に、文字列wが最初に「噛み付いて」から、文字列tが辞書に含まれる最も長い文字列プレフィックスであるため、文字列tで貪欲なパーサーが正しく動作することは明らかです。



この場合、文字列の長さwを文字列の長さw ₁ 、w ₂ 、...、w _k-1の合計よりも小さくします。 次に、w _jが接頭辞w _j1と接尾辞w _j2に分割され、w _j1が文字列wの接尾辞（長さがゼロの場合もある）であるような番号jが存在します。 文字列w _j2を考えます。 彼女のために辞書から単語への正しいパーティションがある場合、反例として、行_{j j2} 、w _{j + 1} 、w _{j + 2} 、...、w _kの連結を残すだけで十分です。これはより短い反例になります。 文字列w _{j2に対して} 、辞書からの単語分割が原則として存在しない場合、短い反例は文字列w ₁ 、w ₂ 、...、w _jの連結です。







だから、今、私たちは望ましい反例がどのように見えるか想像することができます。







その構築に有効なアルゴリズムを開発します。 辞書の各行について、どの接尾辞と接頭辞が辞書からの単語に分類されているかを確認します（このデータの計算方法については後で説明します）。 ディクショナリのすべての行をソートして、それらが最初に「噛み付いた」w行であるかどうかを確認します。 正しいパーティションから最後から2番目の行は、パーティションがある行プレフィックスwが終わる同じ場所でのみ終了できることは明らかです。 このようなすべてのプレフィックスについて説明します。 これで、反例の正しい分割の最後の行を理解するだけです。 まず、これらは、チェック対象の文字列のまだカバーされていない接尾辞wの長さよりも長い行である必要があります。 第二に、文字列wのカバーされていない接尾辞は、対応する長さのパーティションの最後の場所の候補文字列の接頭辞と正確に一致する必要があります。 そして最後に、文字列wでカバーされていない候補文字列の接尾辞には、辞書からの単語への正しい区切りがないはずです。



ここで重要なポイントを1つ挙げるのが適切です。 候補文字列のカバーされていない接尾辞が辞書から単語に分割されたとしても、現在チェックしていることは反例になります。 ただし、サフィックス自体が反例になり、チェックするのは探している最短の反例ではなく、興味がありません。







問題を解決するこのアプローチでは、もう1つ質問する必要があります。 そして、チェックしている行wの代わりに、最初の行がwが接頭辞である別の行に「噛み付いた」場合、どうなりますか？ この場合、貪欲なパーサーは予測できない動作をし、何らかのパーティションを見つける可能性があります。 ただし、この運命を回避するには、行の長さが増加しない順でw文字列でないかどうかを確認し、既に確認した行を覚えておく必要があります。 次に、そのような問題が発生する可能性のある各行は、問題が発生する時間までにチェックされ、この行は単純に無視できます。



問題を解決するための一般的なアルゴリズムが用意されたので、接頭辞と接尾辞の壊れやすさをチェックする問題を解決し、必要な行の必要な部分文字列をすばやく比較して同等にする方法も学習します。 2番目の問題は、それ自体が別の記事または講義のトピックであるハッシュアルゴリズムの助けを借りて非常に簡単に解決されます。 最初のタスクは、動的プログラミングを使用して解決されます。 文字列tのすべてのプレフィックスについて、その長さが厳密にlより短い場合、辞書からの行への分割があるかどうかを確認します。 長さlのプレフィックスのパーティションがあるかどうかを確認するには、辞書からすべての行を整理し、2つのステートメントが真になるように存在を確認するだけで十分です。

• 対応する長さの調査済み接頭辞の接尾辞は、辞書からの行と正確に等しい
• 対応する長さの調査済み接頭辞の接頭辞は、辞書からの単語に分割されます

, O(sumL × n), sumL — , n — , , . , .



« » ( ) « », , – 115:47.

, , . , / , . , , , . , , , — Impossible.



, , x , x — . : (0, 0) (x, y) y, ( ), ( ) (). .







, , , . , , .



, . , , «» , . , . . , - . . , .



, . , . , . , , , , - . , . , , . x, . , , .



, , . O(n2 log n) , O(n) O(n) O(n) . O(n log n) , O(n) .



, .







そして







.







– 23 , – 100:18. , , – , 2 . , .

---

50 . 10 Swissotel, . , , , .



アリエフ・ラウフ



Mail.Ruグループ