ロシアコードカップ2015の最初の予選ラウンドのタスクの分析

ロシアコードカップ2015の最初の予選ラウンドは3月28日土曜日に開催されました。3093人のプログラマーが2時間以内に問題を解決し、そのうち1012人の参加者が少なくとも1つの正しい解決策を送りました。 5つの問題すべてに対する適切な解決策が、Gennady KorotkevichとPetr Mitrichevの2人に引き継がれました。 合計で、参加者は4069のソリューション、C ++で2517、Javaで705、Pythonで425、C＃で318のソリューションをテストするために送信しました。 1745個の正しいソリューションがあり、そのうち1099個がC ++で送信され、339個がJavaで送信されました。

問題A（マジックカード）、2014 RCCの勝者であるGennady Korotkevich（ツーリスト）を解決するための記録的な2分2秒の最初の記録。 彼は6:50の問題B（宿題）と25:43の問題C（若い恋人たちの会議）を最初に解決しました。 51分42秒での問題D（復号化）は、2013 RCCのPeter Mitrichev（Petr）の勝者によって決定されました。 そして、1時間2分52秒での最後のタスクE（エンターテインメント暗号）は、日本の参加者（anta）によって解決されました。 最後に成功した試みは、ミハイルチホミロフが競技終了の6秒前に行ったものです。 最も単純なタスクA、最も難しいタスクはEです。タスクEに合格したのはわずか13人です。

ラウンドの結果、202人の参加者が資格を取得し、6月14日の予選ラウンドでファイナリストのタイトルを競います。 土曜日に微笑んでおらず、何らかの理由でラウンドに参加できなかった人は、4月25日の12:00に2回目の予選ラウンドに、また必要に応じて3月-5月31日の13:00に手を試すことができます。 。 6月14日13:00に予定されている予選ラウンドには、各予選ラウンドからの200人の最高の参加者が含まれます。 ロシアコードカップに参加するには、 サイトに登録する必要があります （3回目の予選の開始前に登録が開始されます）。

チャンピオンシップの参加者と興味のある方は、 VKontakteグループを利用できます。ここでは、人工知能の作成、Webデザイン、スポーツプログラミング、インターフェイス開発、マーケティング、ITプロジェクトの作成に関する情報を見つけることができます。 このグループの資料には、業界の専門家の意見、有用な文献、マスタークラス、説明ビデオ、最高のテーマ別会議、IT分野で最も興味深いイベントが含まれます。 グループの購読者は、Mail.Ru Groupのコンテストやその他のロシアおよび国際IT選手権に関する重要なニュースをいち早く知ることができます。

そして、最初の予選ラウンドのタスクを分析します。

問題A. マジックカード

アイデア： Vitaly Aksyonov
実装： Grigory Shovkoplyas
分析：グリゴリー・ショヴコプリアス

問題では、選択したカードに関係なく、グリシャがいずれの場合でもラウンドに勝つことが本当かどうかを確認する必要があります。 グリシャに最小カードが1枚あり、ディマに最大カードが1枚ある場合を考えます。 明らかに、この場合、グリシャが勝った場合、彼は他のカードで勝ちます。選択したカードのいずれかを特定のプレイヤーのセットの別のカードと交換しても、ディマの量は増加せず、グリシャの量は減少しません。 したがって、問題を解決するには、グリシャのカードを昇順で並べ替え、ディマのカードを降順に並べ替えるだけです。 次に、両方のセットの最初のl数の合計を見つけて比較します。 グリシャの金額が大きければ、彼はどんなラウンドでも勝ちます、そうでなければ-いいえ。

タスクB. 宿題

アイデア： Vitaly Aksenov
実装： Dmitry Filippov
分析：ドミトリーフィリッポフ

この問題は、10進表記で記述された3つの数値x、y、zを提供します。 x _k・y _k = z _kが無限数の数値kについて成り立つかどうかを確認する必要があります（ xの値は、 k数体系で書かれていると仮定するとx _kで表されます）。 そのようなkが無限に多いと仮定します。 次に、任意の大きなkに対して等式を満たさなければなりません。 数値xとyを乗算するときに、どのカテゴリでも転送が行われない数値システムを採用しています。 いずれかのカテゴリで10以上の数値が取得された場合、転送も行われないため、与えられたkだけでなく、基数が大きいすべての数値システムについても同等性は保持されません。 これは、少なくとも転送せずに乗算する場合、数kの無限数について等式が真であることを意味します。9より大きい数の数字があってはなりません。これが行われた場合、結果の積が数zと一致することを検証するためだけに残り、そうであれば、問題の答えは「無限」、それ以外の場合は「有限」です。

タスクC. 若い恋人たちの会議

アイデア： Vitaly Aksyonov
実現： Vitaliy Aksyonov
分析：ヴィタリー・アクショノフ

このタスクは、動的プログラミングタスクです。 次の配列を計算してみましょう：d [最初から何席座っているか] [そのうちの何人が哲学者であるか] [一緒に座っている哲学者と数学者のペアの数] [最後の2つの処理された場所の人々のタイプ]-問題の種類と条件。 この配列は、新しい場所を追加するときに順番に再計算されます。 つまり、新しい人を追加し、彼の前に座っている哲学者の数を整理し、彼のタイプを整理し、環境と場所のタイプに関する条件が満たされていることを確認します（これにより、以前の2つの場所に人々のタイプを保持します）、おそらく2人の哲学者がいます近隣の場所に座っている数学者。

これまでのところ、さまざまな国の人々を使用していません。 型の割り当てを修正する場合、複数の国からの人々が哲学者-数学者の立場にいることを国ごとに数えるために知っておくだけでよいことに注意してください。 国の割り当ての数は、タイプの割り当てのそのようなペアの数にのみ依存することにも注意してください。 配列d から配列cを取得するのは簡単です。配列dは 、対応する型の割り当ての数をペアの数で返します。

最初のk個の位置の間に不動点がないように、 n個の要素の順列の数をp _n、kとします。 その後、答えがnであることを確認するのは簡単です！ Σi = 1 ⁿ p _n、i pを数えることは残っています。 この考え方を使用して、たとえばwikipediaで説明されている固定小数点なしの順列を計算し、再帰式p _n、k =（n-1）p _n-1、k-1 +（k-1）p _n-2、k-を取得します₂およびp _n、0 = n ！ そして、 p _n、1 = n！ -（n-1） ！..

タスクD. 復号化

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

まず、修正なしで問題を解決する方法を学びます。 これを行うには、動的プログラミングのアイデアを使用します。 dp [i]には 、長さiのプレフィックスを取得する方法の数が格納されます。 次に、暗号化された数字が位置i + 1からの行に対応する場合、次の最初の数字xを調べ、値dp [i + len（x） ]をdp [i]だけ増やします（ len（x）は暗号化された数字xの長さです） 。

次に、変更に伴う問題を解決します。 3項式の係数に所定の制限がある場合、1桁は3桁以下の数字に変換できることに注意してください。 次に、この問題を解決するために、セグメントのツリーを使用します。 lからrまでのセグメントを担当する頂点で、 l + 0 ... 2位置からr -0 ... 2位置までの部分文字列を取得する方法の数の9つの値を格納します。 そのようなツリーを構築する方法は？

• lからrまでの間隔が小さい場合、動的プログラミングを使用して値を計算します。
• セグメントが大きい場合は、セグメントを2つに分割し、それらに対応する値を再帰的に計算します。 子の値を知っている場合、ノードの値をカウントする方法を学習する必要があります。 最初に、右と左のサブセグメントが接触している場合、それらの結合でのこの値は、それらの値の積に等しくなります。 それらの間に距離がある場合（つまり、左側に1文字または2文字のない値が右側のサブラインから取得され、右側に1文字または2文字のない値が左側のサブラインから取得される）、答えはそれらの間の1つの番号を取得する方法の数に等しくなります右のサブセグメントと左のサブセグメントの値。

セグメント全体の答えは、セグメントツリーのルートにあります。 したがって、1桁の数字を変更すると、シートの値が更新され、値が更新されて値が上がります。 セグメントのツリーの深さはO （log（ n ））（ nは行の長さ）であるため、合計ランタイムはO （ m log（ n ））です。ここで、 mはクエリの合計数です。

タスクE. 楽しい暗号化

アイデア： Vitaly Aksyonov
実装：イリヤ・ズバン
分析：イリヤ・ズバン

タスクでは、このハッシュを持つ行の数を計算する必要があります。 素朴な解決策は、動的プログラミングdp _iの概念を使用します_。jは、ハッシュjを持つ長さiの行の数です。 遷移はΣで行うことができ、解はn・m・Σで得られます。 このソリューションは、バイナリリフティング手法を使用する場合、 m ²・log nに加速できます。dpi _、jは、ハッシュjを持つ長さ2 ^iの行数です。 dp _i、j =Σ（x = 0..m-1）dp _i-1、x・p ^2i-1 _％m・dp _i-1、jx 。 このダイナミクスの値を使用すると、 nの2のべき乗の展開がわかり、問題の答えが得られます。 最後の加速は、前のダイナミクスの遷移式では、2つの多項式の積にすぎないことがわかります。 これに高速フーリエ変換を使用すると、漸近線m・log m・log nが得られます。 これが完全なソリューションになります。