ロシアコードカップ2014の予選ラウンド：結果とタスクの分析

先週の日曜日、 ロシアコードカップ2014の予選ラウンドが行われました。 4人の資格で最高の結果を示した802人のプログラマーが参加しました。 この段階では、参加者は3時間で6つの問題を解決しなければなりませんでした。これは1時間であり、予選ラウンドよりも1つのタスクが多くなります。 また、タスクは以前のタスクよりもはるかに複雑でした。 802の競争中、少なくとも1つの問題を解決できたのは444人の参加者だけでした。 合計3271のソリューションが送信され、そのうち1402が正しかった。

GNU C ++のほとんどのソリューションは1516です。
Java 7には333のソリューションがあります。
Java 8-106ソリューション。

最初のタスクAは、2時52分でGennady Korotkevich（観光客）によって解決されました。 Gennadyは、それぞれ7：05、24：29、13：05に問題B、C、Dを迅速に解決しました。 問題Eは、Dmitry Egorov（Dmitry_Egorov）によって最初に1分40:59に解決されました。 問題Fはロシアコードカップの歴史の中で最も困難なものの1つになりました-すべての参加者のうち、3人だけが正しくそれを解決し、最初のタスクFはRCC 2013 Petr Mitrichev（Petr）の2:25:46で勝ちました。

すべてのタスクを最初に完了したのは、2時間47分でPavel Kunyavskiy（PavelKunyavskiy）でした。 3人で6個の問題が解決され、100人で5個以上の問題が解決されました。 大事にされたトップ50の最後は、開始から2時間30分後に5番目のタスクに合格したRoman Bily（RomaWhite）でした。

勝つ意志については、上位50位に入り、7回目の試行でタスクの1つをパスしたEgor Kulikov（Egor）に注目します。 また、問題Cの解決方法が分からず、解決を試みることを拒否したPetr Mitrichev（Petr）は、最も困難なタスクFを最初に解決しました。次に、タスクCに戻り、終了4分前に合格し、合計3場所。

このラウンドの参加者の領土分布は次のとおりでした。

ロシア	515
ウクライナ	112
ベラルーシ	77
カザフスタン	26
アメリカ	17
アルメニア	8
ウズベキスタン	8
スイス	6
ドイツ	4
ラトビア	4
オーストリア	2
ブルガリア	2
英国	2
ジョージア	2
モルドバ	2
ポーランド	2
シンガポール共和国	2
アゼルバイジャン	1
アルゼンチン	1
アイルランド	1
カナダ	1
キプロス	1
リトアニア	1
大韓民国	1
スロバキア	1
トルコ	1
スウェーデン	1
日本	1

同時に、ロシアコードカップで初めて、オーストリア、アルゼンチン、日本からのロシア語を知らない参加者がいました！ 彼らの一人が認めたように、彼はオンライン翻訳サービスを通じてラウンドのタスクの条件を翻訳しました。

予選ラウンドでの戦いは激しかった。 その結果、50人の最強のプログラマーが決勝に到達しました。 それらについては後で詳しく説明します。

タスクA.タスクの分析

アイデア：アンナマロバ
実装：アンドレイ・コマロフ
分析：アンドレイ・コマロフ

タスクでは、解析の合計時間が最小限になるように、解析タスクの計画を作成する必要があります。 タスクは、最初からm番目の順にソートする必要があります。 1つのタスクの解析時間はt秒です。 タスクを分析するju審員の交代-c秒。 同じ審査員が連続して複数のタスクを解析する場合、交換は必要ありません。 各ju審員は、どのタスクを処理したいのか、どのタスクを処理したくないのかがわかっています。

この問題は、貪欲なアルゴリズムによって解決されます。 最初から問題の最大数を解決できるju審員を選択します。 彼にk個の問題を解決する方法を教えてください。 次に、 kthから始めて、最大数の問題を解決する方法を知っている人を選択します。 すべてのタスクが整理されるまでこの方法を続けます。 次に、問題の答えはm・t + q・cです 。ここで、 qは行われた置換の数です。

なぜこれが最良の答えですか？ ある時点で、最大数のタスクではなく分析したいju審員を選択してみましょう。 それから、彼をもっと分解する方法を知っていて、もっと分解する方法を知っている誰かに置き換えられるという事実から、答えは改善することができるだけです。

このソリューションは、 O（n・m）で機能します。

動的プログラミングを使用して簡単なソリューションを作成することもできます。 dp [ i ] [ j ]は、 iタスクが逆アセンブルされ、 i番目の審査員が逆アセンブルされた場合に費やされる最小時間に等しくなります。 この配列は、 O（n ² m）として簡単にカウントできます。

問題B. 遠くアマゾンで

アイデア： Vitaly Aksenov
実装： Demid Kucherenko
分析：デミッド・クチェレンコ

この問題では、次の条件が満たされるn個の頂点で構成される有向グラフを作成する必要があります。

• グラフにはサイクルがありません。
• 最大で1つのエッジが各頂点につながります。
• グラフには、発信エッジが存在する頂点が正確に含まれている必要があります。
• グラフには、入ってくるエッジが存在するb個の頂点が正確になければなりません。

まず、答えが「不可能」であるケースを分析します。 これらの条件の少なくとも1つが当てはまる場合です。

• 娘よりも母親の方が多い。
• n -1よりも多くの母親がいます（すべてが母親になることはできません）。
• n -1を超える娘。

そのようなグラフを作成できる場合は、まずエッジのチェーンを作成します。 したがって、+ 1の女性が関与し、母親と娘がいます。 その後、娘が正確にbになるように、母親の娘を補完します。 一部の女性は母親でも娘でもない可能性がありますが、これは課題の条件と矛盾しません。

問題C. 実験室の物理学

アイデア： Vitalik Aksenov
実装： Artem Vasiliev
分析：アルチョム・ヴァシリエフ

この問題では、2つの容器の水を冷水と温水と混合することにより、どの温度の水が得られるかを判断する必要があります。 特定の温度で、このようないくつかの要求に答える必要がありました。

体積c _iの容器からの冷水と体積h _jの容器からの温水を混合する場合、水温の式を記述します：T = p / q =（C・c _i + H・h _j ）/（c _i + h _j ）この式は、 （H・q-p）/（p-C・q）= c _i / h _jとなるので、問題を次のように縮小しました：既約分数と分子と分母のセットが与えられ、分子を選択することが可能です分母が与えられた分数が得られるように？

すべてのc _i / xのセットである表記A _xを導入します。ここで、 c _iはxで割り切れます。 同様に、 B _yはすべてのh _i / yの集合であり、 h _iはyで除算されます。 次に、 A _pとB _qが交差する場合にのみ、既約分数p / qを表すことができます。 すべてのセットA _xおよびB _yの合計サイズはO （ M log M ）であることに注意する必要があります。ここで、 Mは血管の体積の制限です（この問題では、 Mは10 ^5です ）。

A _xとB _yがソートされたリストとして表示される場合、 O（M / max（x、y））で1つのクエリを実行できます。 A _xとB _yをビットセットとして表すと、リクエストごとにO （ M / 64）の解が得られます。

同じ分数の回答を数回数えないと、最速の解決策が得られます。 この場合、ソリューション作業時間のより正確な推定値を証明することができます。 推定値O（（M + k）sqrt（M））を証明しましょう。ここで、 kはクエリの数です。 pとqの最大値がsqrt（M）より大きい場合、小さい方のセットのすべての要素を調べることで、 O（sqrt（M））でクエリを実行できます。 他のすべてのクエリの実行時間の合計を推定してみましょう。 O（M / x）で実行されるクエリは2 x以下です。 すべてのxを合計し、xがsqrt（M）より大きくないことを考慮して、推定値O（（M + k）sqrt（M））を取得します解の合計時間： O（（M + k）sqrt（M）） 。

タスクD. のこぎりの建設

アイデア：ニコライ・ヴェデルニコフ
実現：ニコライ・ヴェデルニコフ
分析：ニコライ・ヴェデルニコフ

タスクでは、次のような順列の数を計算する必要があります。

• a _2・i -1≤a _2・i
• a _2・ i≥a _{2・i + 1}

1からn ⁄ 2までのすべてのiについて、このような順列を鋸歯と呼びます。

このような順列の数は、隣接する数よりも奇数の位置にある順列の数に等しいことに注意してください。 全単射対応： b _i = n-a _i 。 このような順列を減少する鋸歯と呼びます。 これは、問題を解決するためにさらに役立ちます。

明らかに、置換の長さが0または1の場合、答えは1です。

0からnまでのすべての長さの答えがわかっていると仮定すると、 n +1の答えが見つかります。 ノコギリ波シーケンスの総数を考慮します。 増加数を取得するには、増加数が減少数に等しいため、シーケンスの総数を2で除算する必要があります。

n +1を2・kに置き、最初に長さが2・k -1の鋸歯を増やし、次に長さがn -2・k +1の鋸歯を増やします。 最初の2・k -1の位置については、 n個の数字のいずれかを選択できます。 合計で、数n + 1が位置2・kにある長さn + 1の順列の数を取得します。ans _{2・ k -1}・ans _{n -2・k +1}・Binom （ n 、2・k -1） 。

n +1を2・k +1の位置に置くと、最初に長さが2・kの鋸歯が減少し、次にn -2・kの長さが増加します。 最初の2・kポジションについては、 n個の数字のいずれかを選択できます。 合計は、長さn + 1の順列の数を取得します。その数n + 1は、位置2・k + 1で： ans _2・k・ans _{n -2・k}・Binom （ n 、2・k ）。

合計、長さn +1ののこぎり歯列の総数： ans _{n +1} = ∑ ⁿ _{k = 0} ans _k・ans _{n − k}・Binom（n、k） 。

タスクE. 給与

アイデア：アンナマロバ
実現：パベル・クロトコフ
分析：パベル・クロトコフ

この問題では、有向グラフが与えられます。 すべてのrib骨は3つの部分に分類できます。

• このrib骨の最上部での給料とボーナスの配置では、リーダーシップの条件が満たされます。
• リーダーシップの条件を満たすためには、このrib骨の両方の頂点でボーナスで給料を変更するか、いずれかで変更しないことが必要です。
• マニュアルの条件を満たすには、このrib骨の頂点の1つで正確にボーナスで給与を変更する必要があります。

最初のタイプのすべてのエッジと、2番目と3番目のタイプのエッジの向きについては忘れてください。 この後、2番目のタイプのエッジに沿って互いに到達可能な頂点を結合します。 その後、マニュアルの要件を満たすことができるかどうかを確認するタスクは、結果のグラフを2色で着色できるかどうかを確認することになります。

給与とボーナスを交換する必要がある頂点の最小数を取得するには、この検索を詳細に変更します。 次の接続されたコンポーネントを2色で色分けした後、1色と他の色でペイントされた頂点（2番目のタイプのエッジに沿って結合する前の元のグラフ）の数をカウントし、必要に応じて色付けを反転します。

タスクF. ロボット

アイデア： Boris Minaev
実装：ボリスミナエフ、アルテムヴァシリエフ
分析：ボリス・ミナエフ、アルテム・ヴァシリエフ

このタスクでは、フィールドのあるセルから別のセルへの異なるパスの数を特定のステップ数で計算する必要があります。 同時に、アクションを実行するロボットは、最後のターンより前に最終セルにアクセスすることはできません。 また、ロボットは無限平面の4分の1だけを歩くことができます。

最初に、最後の移動の前に最終セルにアクセスできないという条件なしで、あるセルから別のセルに移動する方法を見つけます。 この問題は座標によって個別に解決でき、1つの座標で行われた移動の数と別の座標で行われた移動の数を反復処理できます。 一次元の場合の問題を解決するには？ ロボットは最初に座標x ₁を持ち、最後に座標x _2を持つ必要があります。 a = | x ₂ - x ₁ |、合計tの移動が行われました。 その場合、さまざまなメソッドの数は、（ t - a ）/ 2のtの組み合わせの数に等しくなります（ t - aは非負で偶数でなければなりません）。 ただし、移動中はロボットが正の座標しか持てないことを考慮する必要があります。 これを行うには、セルから取得する方法の数-x 1〜x _2を結果から減算します。 これは、座標の陽性の要件に違反するx ₁からのパスと-x ₁からのすべてのパスとの間で1対1の対応を示すことができるためです。 互いに対応するパスには、最初の部分（セル0に入るまで）と共通の2番目の部分があります。

二次元問題の考察に戻りましょう。 あるセルから別のセルへの各座標に沿って移動する方法の数をすでに数えたと仮定します（各固定移動距離に対して）。 2次元問題の同様の値を計算するには、各座標に費やされた時間を整理し、既に計算された配列の対応する値を乗算する必要があります。また、どの動きがどの座標に対応するかを選択するさまざまな方法の数を掛けます。 これらの値をすばやく計算するには、フーリエ変換を使用できます。 多項式の乗算の問題を軽減するには、組み合わせの数の式に存在するものを取り除く必要があります。 これを行うには、階乗を使用して記述します。 項をグループ化すると、元の配列のi番目の要素をi ！で除算し、結果の多項式を乗算し、 i番目の桁の値にi ！を乗算できることがわかります。 問題では、高速フーリエ変換を実行できるように、すべての操作を実行する必要があるモジュールが選択されました。

次に、ロボットが最後の動きまで最終セルに入ることができないという事実を考慮する方法を検討します。 動的プログラミングを使用して答えを検討します。 t未満の移動でセルに到達する方法の数はすでに数えられています。 t移動のこれらの値を計算するには、 t移動でこれを行う方法の総数を考慮し、 tの前に最終セルに入るすべてのメソッドをそこから減算します。 これを行うには、ロボットが最後のセルにアクセスする最初の動きの番号を整理し、対応するウェイの数にセルを出るウェイの数（ x ₂ 、y ₂ ）を掛けて残りの時間に戻ります。 同時に、ロボットは最終セルに必要な回数だけアクセスできます（2番目の部分）。

これまでに概説したソリューションはt ^2で機能することに注意してください。 より高速なソリューションを得るには、関数を生成するという点で理由が必要です。 f（x）= f ₀ x ⁰ + f ₁ x ¹ + ... + f _t x ^t + ...を表します 。ここで、 f _iは答えであり、問​​題ではありません。 同様に、 カウント（x） -パスの数の生成関数を定義します。最後のターンの最終セルへの最初のエントリの条件を考慮せずに、 サイクル（x） -最終セルからそれ自体へのパスの数の生成関数を定義します。 f _iの再帰関係から、生成関数への関係を導出できます： f（x）= count（x）-f（x）cycle（x） 、whence f（x）= count（x）/（cycle（x）+ 1）= count（x）（cycle（x）+ 1） ^-1 。 fを計算するには、右側の分数の最初のt + 1メンバーをカウントする必要があります。 これは、 サイクル（x） + 1モジュロx ^{t + 1}の逆数を計算し、 カウント（x）に結果を乗算することで実行できます。 x ^{t + 1を}法とする逆多項式は、高速フーリエ変換を使用して時間O （ t log t ）で取得できます。 合計実行時間： O （ t log t ）。