この記事では、 3番目の資格で提供されたタスクを詳細に分析します。 この資料は、スポーツプログラミングの最初の一歩を踏み出している人と、5つの問題すべてを解決できなかった参加者の両方に役立つはずです。 前の2つの解析も歓迎します。1 番目と2番目の資格からです。
行列に並んでいる訪問者からの役人、塗料で満たされた時計、誰かに食べられなかったチョコレートについてのネガティビティの最小量を計算する際の大きな問題-これらの素晴らしいタスクを分析する喜びを共有しようと思います。
予選ラウンドのタスクは著しく複雑で、さらに興味深いものになります。 6月
「チョコレート」
Chocolateタスクでは、2つの「半分」の正方形のチョコレートから全体を組み立てることができるかどうかを判断する必要がありました。 入力は、行ごとの「スイープ」であり、各「行」の左半分と右半分のスライスの幅です。 小葉が欠落している場合は回答する必要があります。「はい」はこれが見つかったことを意味し、すべてが正常な場合は「いいえ」を意味します。 問題の詳細な声明については、 RussianCodeCup.ruの公式Webサイトを参照してください。明らかに、「左半分の幅」-「右半分の幅」の合計がn-チョコレートバーの幅にならない場合は、「はい」と書きます。
最初の2つの資格と同様に、最初のタスクは最も単純で、できるだけ早く、最初の試行で実行する必要がありました。 Korotkevich Gennadyが最高の結果をもたらしました-ツアー開始から1分40秒。 この時間は、タスクを読み取り、プログラムを作成してテストし、サーバーに送信するのに十分でした。
「ゲーム」
問題の観点から、プレイヤーが無限のフィールドを横切って1つのピースを交互に移動する単純なゲームで勝者を見つける必要があります。 開始位置とゴールの既知の座標に応じて、駒を持ち込む場所、および移動の範囲に関連する数値パラメーターに従って、ゲームの結果とゲームが終了し、その移動が最後に行われた移動の回数を通知するか、Infinityを表示する必要がありますプレーヤーは永遠にプレイできます...問題の詳細な声明については、 RussianCodeCup.ruの公式Webサイトを参照してください。最も単純なオプションは、最初のプレーヤーの1ターンでゲームが終了する場合、つまりターゲットと開始位置が指定範囲以下の距離にある場合に明らかです。
この問題の重要な解決策は、他のすべての場合において、プレイヤーがいずれも間違った動きをしない場合、無期限にプレイできることを証明することです。 それ以外の場合、最初の動きよりも最初の動きが勝つことはできません。 2番目の1つは負けないように1番目の1つが2番目の1つをその場所に戻すことができるため、2番目の1つも勝つことができません。
その結果、問題の解決策は非常にシンプルになりました。ポイント間の距離が指定範囲以下の場合、1回の動きで最初のプレイヤーの勝利を表示し、他の場合は「Infinity」を表示します。
「時計」
タスクでは、時計が停止したときに針の異なる位置の数を見つける必要があります。 条件により、ダイヤルは部分的にしか開くことができず、停止時の手または両手の片方が開いたセクターに落ちた場合、それらの位置は既知になりますが、それにより可能なオプションの数が狭くなります。 実際の時計のように、時針と分針の位置が互いに直接依存していることも知られています。 矢印オプションの数を見つける必要があります。 すべての詳細を含む問題の完全な声明は、 RussianCodeCup.ruで入手できます。開始するには、分針の位置に多くの値を準備します。
if (m == -1) { // , // mins = new int[60]; for (int i = 0; i < 60; i++) mins[i] = i; } else { // , () mins = new int[]{m}; }
時計回りにも同じことを行います。
if (h == -1) {// , // hours = new int[12]; for (int i = 0; i < 12; i++) hours[i] = i; } else { // , () hours = new int[]{h}; }
次に、これらのセットの製品全体を調べて、互いに対する矢印の正しい位置を確認します。
| 分針 | 0-11 | 12-23 | 24-35 | 36-47 | 48-59 |
| 時針
（最小区分で） | 5 * h + 1 | 5 * h + 2 | 5 * h + 3 | 5 * h + 4 | 5 * h + 5 |
| 5 * h + int（m / 12） | |||||
正しい位置を確認する式は簡単です-5 * h + mm / 12。
for (int hh : hours) { // for (int mm : mins) {// int hhh = hh; // hhh – if (hours.length != 1) hhh = hhh * 5 + mm / 12; // // check . // a = // b = ans += check(a, b, hhh, mm, h == -1, m == -1) ? 1 : 0; } }
補助チェック機能は、分針と時針の相対位置が存在できるかどうか、および針の位置が可視性に対応しているかどうかをチェックします。
boolean check(int a, int b, int hh, int mm, boolean hInside, boolean mInside) { // a = // b = // hh = // mm = // hInside = // mInside = boolean hOk = inside(a, b, hh) ^ hInside; boolean mOk = inside(a, b, mm) ^ mInside; return hOk && mOk && (hh % 5 == mm / 12); } // , m a,b boolean inside(int a, int b, int m) { if (a <= b) return a <= m && m <= b; return inside(a, 59, m) || inside(0, b, m); }
GAS「キュー」
このタスクの条件は、ここに完全に持ってくることです：「過去数年にわたり、電子回線はしっかりと日常生活に入ってきました。 多くの政府機関では、番号付きの紙を印刷する端末に会うことができ、「誰が最後ですか？」という通常の質問をすることなく、訪問者は電子スコアボードを使用して、待機時間と順番が来るのを確認します。
ただし、そのようなシステムは完璧にはほど遠いものの、 たとえば、キューの標準原則では、「最初に到着した人が最初にサービスを提供します」という疑問が生じます。 革新的なGAS "Queue"を開発する際、この原則の実装が必要とされないようにすることが決定されました。 代わりに、新しいシステムは、列に並んでいる人々に受け入れられている役人に関する否定性の量を最小限に抑えるように設計されています。
各人が過敏性などの基準を持っていることが知られています。 このパラメーターがwに等しい場合、t時間並んで待った後、この人は、公式の頭に正確にwt単位の怒りと虐待をもたらします。 したがって、訪問者が到着直後に仕えられれば、役人は苦しむことはなく、訪問者が3時間の初めに到着し、彼の奉仕が5時間の初めにのみ始まった場合、怒りの量は2ワットになります。
また、各訪問者にサービスを提供するのに正確に1時間かかり、各訪問者は1時間の初めに到着することも知られています。 あなたの仕事は、あなたの過敏性指標と訪問者の到着時間に応じて、顧客サービスの最適な順序で職員がどれだけ否定的になるかを決定することです。
最初の行には、1つの整数t-処理する必要があるケースの数が含まれています。 以下は、ケース自体の説明です。
各ケースの説明は、最初の行の数n-訪問者の数、および訪問者自身のn個の説明で構成されます。 各ビジターについて、別々の行に、2つの整数riおよびwi（1≤ri、wi≤106）が示されます-ビジターが到着した時間数、およびそれぞれのイライラ係数。
1つのテストのすべてのケースでの訪問者の総数は1,000,000を超えません。
ケースごとに、個別の行に回答が表示されます-担当者が受け取るネガの最小合計額。
タスクの例の1つは、説明されている原則を示しています。 この例では、3人の訪問者がオフィシャルに来ました。 これらのうち、2-最初の1時間の始めに、それぞれ「3」と「4」のいらいらがあります。 そしてもう1つ-2時間目の始めに、いらいらする「5」があります。 それぞれのサービスには1時間かかります。したがって、最初の1時間の開始時に2つのオプションがあります。刺激性のある訪問者「4」または刺激性のある訪問者「3」をスキップします。 見逃していない人は次の時間に移動し、別の訪問者「5」が追加され、さらに2つのオプションがあります-新人をスキップするか、並んでいる人。
| 迷惑
来て | オプション1 | オプション2 | オプション3 | オプション4 | |
| | 3、4 | P（3）、RF = 0 | P（3）、RF = 0 | P（4）、RF = 0 | P（4）、RF = 0 |
| | 5 | P（4）、RF = 4×1 = 4 | P（5）、RF = 4×1 = 4 | P（3）、RF = 3×1 = 3 | P（5）、RF = 3×1 = 3 |
| | - | P（5）、RF = 4 + 5 = 9 | P（4）、RF = 4×2 = 8 | P（5）、RF = 3 + 5 = 8 | P（3）、RF = 3×2 = 6 |
| 最小 |
2時間、オフィシャルは最小限の刺激性を受け取ります6。
この問題を解決するアルゴリズムは非常に簡単です。この瞬間にすでに到着した人、まだ役立っていない人、そして同じ人の残りの人と同じように過敏性がある人に奉仕することが最も有益であるという事実を推測した場合。
この声明を証明しましょう。 このルールに従って構築されたスケジュールと最適なスケジュールを用意してみましょう。 それらが異なる最初の時点t 1を考えます。 この時点で最適なスケジュールで勤務している人に過敏性w 1を与え、この時点で勤務している人に2番目の過敏性w 2を設定します。 最適なスケジュールでは、この人はある時点t 2でサービスされ、t 2 > t 1 （結局、t 1まではスケジュールは同じでした）。 つまり、これら2人の場所を最適なスケジュールで変更すると、時刻t 1と時刻t 2の両方で（両方のスケジュールが有効であるため）両方が利用可能になるため、明らかにできます。 （t 2 -t 1 ）×w 1 +（t 1 -t 2 ）×w 2に変化し、これは（t 2 -t 1 ）×（w 1 -w 2 ）に等しくなります。
t 2 > t 1 （上記のとおり）、およびw 2 > w 1 （調査済みのスケジュールを作成することにより）であるため、表示される怒りの変化量は負になり、最適なスケジュールが改善されたことを意味します。 明らかに、他のすべての不一致に対するこのような推論は、上記のキューアルゴリズムが正しいという事実につながります。
これで、説明したソリューションの実装について考えることができます。 すでに到着したがまだサービスを受けていないすべての人々を格納し、そこから短時間で最大の要素（過敏性が他の人よりも劣らない人々）を抽出できるデータ構造が必要です。 この構造は優先キューです。 たとえば、バイナリヒープを使用して実装する場合、操作はO（log n）で実行され、ソリューションの合計漸近時間はO（n log n）になります。
たとえば、JavaおよびC ++では、優先度キューはそれぞれPriorityQueueおよびpriority_queueクラスとして実装されます。 しかし、完全を期すために、知識のない人にとってそれが何であるかを伝える必要があります。
優先度キューを使用すると、ペア（キー、値）を保存でき、ペアの追加、最小または最大キーを持つペアの迅速な検索、およびそのようなペアの取得の操作をサポートします。 この構造を実装する効果的で最適な方法は、バイナリヒープを使用することです。
累積が最大のバイナリヒープは、子孫ノードをその祖先ノードより大きくすることはできません。つまり、最大は常にルートであるため、取得は非常に高速です。 新しいペアが任意のフリーエンドノード（シート）に追加された後、ルートに向かって移動しますが、祖先の値は追加されたばかりのキーの値よりも小さくなります。
このアルゴリズムの詳細については、 http ： //www.rsdn.ru/article/submit/heap/heaps.xml#EKLACをご覧ください。
「干渉」
この問題では、既知の多項式ハッシュから破損したデータ（34ビットのメッセージのセット）を回復するためのアルゴリズムを記述する必要がありました。 同じハッシュを持つ最小ビット数の元のメッセージとは異なるメッセージを復元する必要があります。問題の詳細な声明については、 RussianCodeCup.ruを参照してください
ミートインザミドルの概念には、タスクを半分に分割し、半分の部分的な計算を通じて「大きなタスク」を解決することが含まれます。 このアプローチによって解決される古典的な問題は、最も効率的なバックパック梱包の問題です。 各アイテムは重量と価値によって特徴づけられます。重量制限のあるバックパックに最大合計額の物を詰める必要があります。 これを解決するために、多数のNが2つの等しい（またはほぼ等しい）サブセットに分割されます。そのため、すべてのオプションを許容時間内に実行し、各重みと値の合計を計算してから、最初のサブセットの各グループに対して2番目のグループを見つけます総重量が制約に適合する最大値。
この場合、最初のn / 2ビットのハッシュと、nn / 2ビットのすべての種類のオプションのハッシュを個別に計算する必要があります。 各半分で、最大2 17 = 131072個のオプションが取得されます。
int m = (len + 1) / 2; // ó Pair[] h1 = new Pair[1 << m]; // for (int i = 0; i < h1.length; i++) { h1[i] = new Pair(i, countHash(i)); // } Pair[] h2 = new Pair[1 << (len – m)]; for (int i = 0; i < h2.length; i++) { h2[i] = new Pair(i, countHash(((0L + i) << m))); // }
固定の既知のハッシュhを持つメッセージを受信する必要があるため、ペアのビットh 1の前半のハッシュ値の各バリアントは、h =（h 1 + h 2 ）mod Mのようにビットh 2の後半のハッシュ値と1つしか一致しません。
h 2の対応する値をすばやく見つけるために、各バリアントh 1について学習する必要があります。 C ++のsetやJavaのTreeSetとHashSetなどのデータ構造を使用できます。
また、前半と後半のすべての種類のハッシュを昇順で並べ替え、「2つのポインター」という考え方を使用することもできます。
値の昇順で、最初の半分のハッシュに沿って最初のポインターiを移動します。 この場合、前の適切な値から開始して後半の対応するハッシュを検索し、後半のハッシュに沿って値の降順で2番目のポインターjを移動します。 その時点で、ポインターjが最小値に達したら、最大値に移動する必要があります。 ただし、これは1回しか発生しないため、合計で、ポインタjはすべての値で2回以下しか渡されません。
そして最後に、見つかったh 1とh 2の適切な値のすべてのペアから、受信したメッセージmと比較して最小ビット数が変化したものを選択する必要があります。
アリエフ・ラウフ、
研究教育ディレクター
Mail.Ruグループ