6月1日日曜日、ロシアコードカップ2014の4回目の最終予選ラウンドが開催されました。
ラウンドに参加するために登録された5428人。 730人の参加者から少なくとも1つのソリューションが送信されました。 合計で、ラウンドあたり4793の決定が送信され、そのうち1531が正しかった。
ほとんどのGNU C ++ソリューションは1786です。
Pythonには307のソリューションがあり、そのうち86が正しいです。
PHPソリューションは93個あり、そのうち15個が正しいです。
Perlには6つのソリューションがあり、そのうち2つが正しいです。
最初のタスクAは、Dmitry Filippov（DimaPhil）によって2:42分で解決され、12：09に問題Bを初めて解決しました。 タスクCとDは、それぞれ12:25分と37:44分にAlexander Obednikov（AOb）によって最初に決定されました。 最初のタスクEは、Fefer Ivan（Fefer.Ivan）によって45:22分に解決されました。 Ivanは、1時間8分ですべてのタスクを完了した最初の人でもありました。 12人が解決した問題は5つだけです。 10人の参加者が裁判官によって失格となりました。
4回の予選ラウンドの合計で、802人の参加者が6月8日の決勝でお互いに予選を行いました。
タスクA 世論調査
アイデア：アンドレイ・スタンケビッチ
実現：ニコライ・ヴェデルニコフ
分析：ニコライ・ヴェデルニコフ
タスクでは、問題を解決する参加者の最小数と最大数を見つける必要があります。 すべてにn人の参加者がいる場合、それらのうち、問題aおよびbを解決することができます。タスクは参加者に反します。
問題の条件によって、それが嫌で解決できない人によってのみ解決されるため、問題を解決しようとする人の数はn - b以下になります。 つまり、問題を解決しようとするすべての人の中に、できる人がいる場合、これは問題を解決する人の最大になります。 これはmin（ a 、 n - b ）です。
タスクに反対する全員が問題を解決できる場合、最小値に到達し、答えは最大（0、 a - b ）になります。
タスクB 百
アイデア：Vitaly Aksyonov
実現：パベル・クロトコフ
分析：パベル・クロトコフ
この問題の解決策は、いくつかの単純なケースを慎重に検討するプログラムです。 最も単純なケースは、 xの桁数がk +1の場合です。 この場合、数値に単一のゼロが含まれていない場合は-1を出力し、数値に少なくとも1つのゼロがある場合はゼロを出力する必要があります。
番号xの番号の数がkを少なくとも3超える場合、この状況をより慎重に処理する必要があります。 最後から2番目のゼロの中にあります。 その後ろにk + 1桁以下があることを確認してください。 末尾から2番目のゼロの後ろにあるすべてのゼロ以外の数字を消し、最後から2番目のゼロの直前に必要な桁数を消します。 最初の桁が消されることはないことに注意してください。これは、最終番号に先行ゼロがないことを意味します。
数字を削除する操作は、数字の長さだけ実行してはならないことを忘れないことが重要でした-このようなエラーのあるソリューションは、3回目のテストで制限時間を超過しました。
タスクC 訪問中
アイデア：ジョージコルネエフ
実装：Boris Minaev
分析：ボリス・ミナエフ
問題を解決するには、条件に記載されているプロセスを慎重にエミュレートする必要があります。 実装する場合、組み込みツールを使用してキューを維持すると便利です。 キュー自体に、たとえば、適切なギフトを購入した人の番号を保存できます。 次に、ゲストへの次の旅行は次のとおりです。 訪問する人に対応する要素をキューから取り出します。 彼の順番が空の場合、この人物に一致する要素がキューから取り出されたと想定します。 その後、この要素をキューに追加します。キューは、訪問した人に対応しています。 追加されたアイテムの値が追加されたキューの番号と等しい場合は、YESを印刷する必要があります。そうでない場合はNOを印刷する必要があります。
タスクD SNM
アイデア：Artem Vasiliev
実装：Artem Vasiliev
分析：アルチョム・ヴァシリエフ
このタスクでは、ランクヒューリスティックを使用した、パス圧縮ヒューリスティックを使用しない、ディスジョイントセットのシステムの実装について説明しました。 各ルートツリーの問題を個別に解決します。また、サイクルが存在する場合も考慮する必要があります。
入力にランク配列が指定されていませんが、パス圧縮なしでは、 ランクiはルートiに頂点iを持つサブツリーの高さであることを理解するのは簡単です。 また、アルゴリズムは、 ランクiが1つだけ増加するように設計されており、頂点が別の頂点から中断された後、その親とランクは変更されないため、リーフからルートまで構築できることに注意してください。
頂点uにルートを持つサブツリーを考えます。 ランクu = rの場合、頂点uにランク0、1、...、 r -1の子が存在する必要があります。 この条件が十分であることを示すのは簡単です。息子のランクを上げるために組合操作を行うと、すべての操作が正しく行われます。
したがって、単一ツリーのソリューション：
- ツリールートのすべての子のソリューションを再帰的に構築します。
- 0からランクroot -1までのすべてのhについて、ランクhの息子がいることを確認します。
- 子 （ランク、 子i ）の操作は、 子iのランクを昇順に実行します。
結果の親配列が必要なものと一致することを確認することにより、SNMを実装し、すべての操作を直接実行することもできます 。
ソリューションのランタイムはO （ n log（ n ））です。
タスクE ナノロボット
アイデア：Vitaly Aksyonov
実装：アンドレイ・コマロフ
分析：アンドレイ・コマロフ
問題では、2つの部分に移動または分割するアクションの最小数について、すべてのナノロボットを左上から右下に移動する必要があります。
動的プログラミングを使用してこの問題を解決します。 dp [ w ] [ x ] [ y ]で、質量wのロボットをセル（ x 、 y ）から最終セル（ n 、 m ）に運ぶことができる最小ステップ数を示します。 初期値dp [ w ] [ n ] [ m ] = 0は、ターゲットセルからどこにも移動する必要がないことを示します。 dpが計算された後、回答はセルdp [ w ] [1] [1]に含まれます。
dpを数えることを学びます。 dp [ w ] [ i ] [ j ]を計算するには、次の2つのいずれかを実行します。
- ロボットをバラバラにすることなくフィニッシュラインに到達します。 これを行うには、詳細なウォークを使用して、耐性セルを通るフィニッシュラインへの最短経路を見つけます。
- または、ある種のセルに到達し、2つの部分に分かれてそこから到達します。
ダイナミクスの値をカウントする順序を理解することに問題がないように、あなたはそれをゆっくりと考えることができます。 アルゴリズムの総複雑さ： O （ w 2 n 2 m 2 ）。