ロシアコードカップ2015の2回目の予選ラウンドは4月25日土曜日に開催されました。3516人のプログラマーが2時間以内に問題を解決し、そのうち458人の参加者が少なくとも1つの正しい解決策を送りました。
問題A（地下鉄のターンスタイル）のAlexander Masharabov（地図）を解決するための4分9秒での最初。 Denis（Stigius）は8:48で問題B（ゲーム）を解決し、Nigmatullin Niyaz（niyaz.nigmatullin）は18:08で問題C（スティックとヒンジ）を解決しました。 問題D（フィボナッチ数）は1時間5分21秒でアントンルネフ（Anton_Lunyov）によって解決されました。 そして、1時間44分55秒での最後のタスクE（テレポート）は、ラウンドの結果によるランキングで1位になったPavel Kunyavskiyによって解決されました。 最後の成功は、アルバートサハキヤンが競技終了の4秒前に試みたものです。 5つのタスクはすべて、Pavel Kuyavskyによってのみ渡されました。
合計で、参加者は検証のために4287ソリューションを送信し、C ++では3145、Java-613でした。GNUC ++に提出された2166ソリューションのうち、1218ソリューションはC ++ 11標準を使用します。言語。 今回は、C ++の726とJavaの141を含む、913の正しいソリューションのみがあります。
ラウンドの結果によると、200人の参加者が6月14日に行われた予選ラウンドのファイナリストのタイトルを獲得しました。 土曜日に微笑んでおらず、何らかの理由でラウンドに参加できなかった人は、5月31日の13:00に3回目の予選ラウンドに参加することができます。 6月14日13:00に予定されている予選ラウンドには、各予選ラウンドからの200人の最高の参加者が含まれます。
チャンピオンシップに参加したい人は誰でも、3回目の予選の開始前にサイトに登録する時間があります。
タスクA. 地下鉄のターンスタイル
アイデア：Dmitry Filippov
実装：Dmitry Filippov
分析：ヴィタリー・アクショノフ
問題の状況に応じて、2人の男の子のターンスタイルに表示される数字がk回異なる時点を見つける必要があります。 まず、 k = 1の場合を分析します。この場合、両方のターンスタイルに99が表示されている場合、またはa = bの場合、答えはYESです。 それ以外の場合、適切な時点が、少年の場合は旅行の回数が99未満になるよりも早く来ることに気付くことは難しくありません。最初のそのような時点にすぐに進みます。 適切な日には99個以下のオプションが残っています。 問題の条件を満たしていることを確認するために、各項目を確認します。
問題B. ゲーム
アイデア：ニコライ・ヴェデルニコフ
実現：ニコライ・ヴェデルニコフ
分析：ニコライ・ヴェデルニコフ
問題の状態により、最初のレベルから最後のレベルまでのパスの長さの数学的期待値を見つける必要があります。 これを行うには、動的計画法を使用します。 j番目の部屋のi番目のフロアから開始して最後のレベルに移動する場合、パスの長さの数学的期待値はdp [i] [j]に格納されます。 次に、問題に対する答えがdp [1] [1]に保存されます。
最後のレベルから最初のレベルまで問題を解決します。 dp [n + 1] [x] = 0（ xは 1〜n + 1）であることは明らかです。（ k + 1）レベルの答えを知って、 kのダイナミクスの値を計算します。
- a [k] [j] [0] < a [k] [j] [1]の場合、 dp [k] [j] = dp [k + 1] [j] + a [k] [j] [ 0] 。 ここで、[k] [j] [0]は、 j番目の部屋のk番目のレベルから（ k + 1）番目のレベルのj番目の部屋までの廊下の長さです。 また、[k] [j] [1]は、j番目の部屋のk番目のレベルから（ k + 1）番目のレベルの（ j + 1）番目の部屋までの廊下の長さです。
- a [k] [j] [0] > a [k] [j] [1]の場合、 dp [k] [j] = dp [k + 1] [j + 1] + a [k] [j ] [1]。
- a [k] [j] [0] = a [k] [j] [1]の場合、 dp [k] [j] =（ dp [k + 1] [j] + dp [k + 1] [ j + 1] ）/ 2 + a [k] [j] [0] 。 なぜなら、最初の回廊と2番目の回廊の両方に等しい確率で進むことができるからです。
計算後、問題に対する回答はdp [1] [1]に保存されます。
問題S. スティックとヒンジ
アイデア：ジョージコルネエフ
実装：Grigory Shovkoplyas
分析：グリゴリー・ショヴコプリアス
この問題では、ヒンジで接続された一連のスティックが与えられます。これは、任意の破線の形をとることができ、エッジは対応するスティックの長さに等しくなります。 条件では、この図はチェーンと呼ばれていました。 チェーンを配置できる円の最小半径を見つける必要がありますが、円の中心は最初のスティックの始点と一致する必要があります。
回答によるバイナリ検索を使用したソリューションを検討してください。 明らかに、チェーンが円に配置されている場合、それはより大きな半径の円に収まります。 ここで、サークルにチェーンを含めることができることを確認する必要があります。 アイデアは簡単です。スティックの最大数を選択し、その合計長さが円の半径以下になるようにします。 スティックがなくなったら、問題は解決します。 それ以外の場合、次を配置できるかどうかを確認します：その長さから前のものの合計を引いたものが半径よりも大きい場合（ヒンジで180度回転して円を超えた場合）、この円にチェーンを合わせることができません。そうでない場合、円上の点があります次のヒンジを取り付けることができます。つまり、このスティックが収まります。 ここで、残りのスティックの長さが円の直径よりも小さいことを確認します。これは、残りのすべてのヒンジを円に分解でき、チェーンが円に収まるという事実に相当します。
問題D. フィボナッチ数
アイデア：イリヤ・ズバン
実現：Vitaliy Aksyonov
分析：ヴィタリー・アクショノフ
問題の条件によって、10 9 +23を法とする最初のn個のフィボナッチ数のk乗の合計を見つける必要があります。 最初のアクションは、モジュールを因数分解することでした：10 9 +23 = 3・11 2・61・45161。 これらのモジュールのそれぞれに必要な量を計算し、中国の剰余定理に従って問題の答えを復元しましょう。
モジュールごとに、問題は次のように解決されます。 フィボナッチ数の周期を見つけます。 私たちのモジュールの場合、それらは小さく、事前期間は常に0です。特定の期間と別の小さな断片のフィボナッチ数のk番目の合計を計算します。 次に、固定nの問題に対する答えは、いくつかの期間の合計と小さな部分の合計に等しくなります。
それぞれの小さなタスクの回答を受け取った後、最初のタスクの回答を復元します。 残念ながら、この段階ではタスクは終了しませんでした。 プログラムが時間通りに通過するためには、最適化を考え出す必要があります。 次のことを適用することができました：事前に2の累乗で数を数えた、急激なべき乗中に絶対値をとるdoubleを取り除くか、 k単位ではなく、オイラーの定理を使用してφモジュロ単位で上げる。
問題E. テレポート
アイデア：イリヤ・ズバン
実装：イリヤ・ズバン
分析：イリヤ・ズバン
この問題には、反映可能なn個のテレポートポイントが含まれており、開始ポイントから最終ポイントに到達できるかどうかを確認する必要があります。 点i、jに対する行の2つの反射により、現在の点の座標にベクトルf（i、j） =（2（ x j -x i ）、2（ y j -y i ））が追加されることに注意してください。 答えの反射が偶数であることがわかっている場合、問題は次のように減らすことができます：ベクトルf（i、j）の合計でベクトル（ x f -x s 、y f -y s ）を表すことは可能ですか？ 答えにベクトルの数が奇数の場合、最初のアクションが任意のテレポートに関する開始点を反映している場合は偶数の問題になり（最初の移動のnオプションすべてを並べ替える必要があるように見えるかもしれませんが、これは本当に必要ではありません）、偶数の問題を解決しようとします応答のベクトル。
すべてのn 2ベクトルf（i、j）を使用する必要はないことに注意してください：f（i、j）= f（1、j）-f（1、i） 。 したがって、 n -1ベクトルのみを考慮に入れました。 整数ベクトルの整数線形スパンは、いくつかのベクトルのうち2つだけの整数線形スパンとして表すことができると主張されています。 このシェルは、平面上のグリッドです。
考慮されたセットに一度に1つずつベクトルを追加し、すでに追加されているすべての線形結合を定義する2つのベクトルをサポートします。 1つのベクトルの形式はv 1 =（ x 1、0）で、 x 1は最小の正の値、2番目のベクトルはv 2 =（ x 2 、 y 2 ）の値、 y 2は最小の正の値、0≤x 2 < x 1 。
追加されたベクトルはすべて共線ですが、ユークリッドアルゴリズムを使用すると、他のすべてのベクトルを線形結合で表すことができる単一のベクトルを簡単に見つけることができます。 少なくとも1組の非共線ベクトルが考慮されるセットに現れるとすぐに、ベクトルは異なる方法で再計算されます。 ベクトルv 3を追加します。
新しいベクトルv 1を見つけるには、2つのベクトルのGCDを調べる必要があります。古いv 1と、ベクトルv 2とv 3の線形結合で表される形式（ x 、0）の最小xを持つベクトルです。 これを行うには、方程式k 2・y 2 + k 3・y 3 = 0の最小解を見つけます。新しいベクトルv 2を見つけるには、形式k 2・v 2 + k 3・v 3のベクトルを考慮する必要があります。 方程式k 2・y 2 + k 3・y 3 = GCD（ y 2 、 y 3 ）の解を見つけて、新しいv 1を数回追加して、x座標の最小性を保証する必要があります。 グリッドを定義する2つのベクトルがわかれば、このベクトルが整数線形結合として表現できることを簡単に確認できます。これら2つのベクトルの展開係数が整数であることを確認するだけです。