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

2013年4月13日土曜日、19時に最初の予選ラウンドが行われました。 一見不幸な日付にもかかわらず、多くの人にとって、この日は逆に非常に成功しました。

この投稿では、最初の資格審査の結果について簡単に説明し、参加者に提案したタスクを詳細に分析します。

関係する今日の分析では：

• ノームランドのオリンピック
• ある日、アントン・セルゲヴィッチと彼の生徒たち
• フラットランド原子力研究所におけるムーランの貯蔵の問題
• planet石から惑星を保護する実際の問題
• テレポーターと、トレジャーハンターのために作成する障害

合計から始めましょう。 765人が資格に参加しました（これは、ソリューションを送信した参加者の数であることに注意してください。登録者が著しく増加しました）。

参加者は問題を解決するために2時間与えられました。 タスク自体は予選ラウンドの最初にサイトで直接公開されたため、参加者は事前にそれらに慣れることができませんでした。すべてが平等な立場にありました。

参加者の地理的分布は真にグローバルであることが判明しましたが、もちろん、ロシアの参加者の数は最大でした。 したがって、降順で：



ロシア-540

ウクライナ-81

ベラルーシ-46

アメリカ-21

アルメニア-20

カザフスタン-15

ウズベキスタン-6

ジョージア-6

ドイツ-6

スイス-5

スウェーデン-2

イギリス-2

オランダ-2

キルギスタン-2

ポーランド-2

アイスランド-1

タジキスタン-1

アイルランド-1

日本-1

スペイン-1

リトアニア-1

イスラエル-1

チェコ共和国-1



201名が予選に参加しました。 以下は、最初に資格を得た10人の参加者のリストです。

1.ヴラディスラフ・エピファノフ

2.セルゲイ・ログレンコ

3. Ivan Popelyshev（3位）

3. Pyotr Mitrichev（もう3位）

5.アントン・ライチュク

6.ヴラディスラフ・イセンバエフ・ウィンガー

7.アントン・ルネフ

8.エゴール・クリコフ

8.ジェンナディ・コロトケビッチ

8.ローマン・リズヴァノフ

リストからわかるように、一部の参加者は同じ数のポイントを獲得したため、同じ数字で場所を共有しました。

それでは、タスクの分析に移りましょう。 参加者は自分の決定を確認することができ、まだ資格に合格していない人はバージョンを練習して確認することができます（ちなみに、次の資格ラウンドは5月11日と6月2日です）。



問題A.オリンピック

アイデア： Vitaly Aksyonov

実現： Vitaliy Aksyonov

分析：ヴィタリー・アクショノフ



問題を解決するために、3つの与えられた長方形すべてが共通のコーナーの1つを持つ最適なソリューションがあることに気付くことができます。

各フィールドの配置方法を列挙します-垂直または水平。 フィールドの位置を修正した後、長方形の結合の面積を計算するだけで十分です。 次のように計算できます。S= S ₁ + S ₃ + S ₃ -S ₁₂ -S ₂₃ -S ₁₃ + S ₁₂₃ 、ここでS _iはi番目の長方形の面積、S _ijは番号iと2つの長方形の交差面積j、およびS ₁₂₃は、3つの長方形すべての交差領域です。



問題B.台形マップと台形

アイデア： Vitaliy Demyaniuk

実現： Vitaliy Demyanjuk

分析： Vitaliy Demyanjuk



台形の小さい方の平行辺と大きい方の平行辺の長さをそれぞれaとbで示し、cで辺の長さを示します。 その後、a + 2c> bの場合にのみ台形を構成できます。 a、b、cを調べると、O（n ³ ）で解が得られます。

bを固定してcを増やすと、可能な最小aが小さくなることに注意してください。 昇順でbを反復し、固定bについては昇順でcを反復します。 cを反復するとき、可能な最小のaへのポインターを維持します。 b、c、可能な最小aがわかっていて、単純な組み合わせ式を使用すると、指定されたパラメーターで台形を形成する4つのセグメントのセットの数を簡単に計算できます。

また、a = b、a = c、b = cの場合を処理することを忘れないでください。また、各4つのセグメントの番号がペアごとに異なることを慎重に確認してください。 結果の複雑さはO（n ² ）です。



タスクC.ムランの保管

アイデア： Vitaly Aksenov

実現：パベル・クロトコフ

分析：パベル・クロトコフ



まず、線形時間で機能するソリューションを実装します。 同位体の質量を、1から始まる昇順で検討します。kを現在の数、2 ^tを kより大きい2の最小累乗とします。 この場合：

• kが2のべき乗または2 ^tである場合、「臨界数」のセットに含まれないため、質量kの同位体はどの倉庫にも保存できます。
• そうでない場合、質量kの同位体は、質量2 ^t -kの同位体がない倉庫にのみ保管できます。

答えは2 ^{x + d}であり、dは1以上n以下の2のべき乗の数であり、xは2のべき乗でない最小の2のべき乗が「臨界数」のセットにないような数の数であることに注意してください「。 したがって、1からnまでのすべての数を境界が2のべき乗であるlog ₂ n個のセグメントに分割し、目的のセグメントを選択してその長さを合計することができます。



タスクD.惑星の保護

アイデア： Vitaly Aksyonov

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

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



それぞれのeo石を検討し、危険地帯への進入と退出の時間を見つけます。 これを行うには、球の方程式x ² + y ² + z ² = R ²で、met石の軌道を定義する直線の方程式、つまりx = x ₀ + dx•t、y = y ₀ + dy•t、z = z ₀ + dz•t。 時間の二次方程式を取得します。 ルーツは私たちにとって興味のある時間です。 この問題では、浮動小数点数の精度に問題が発生する可能性があるため、方程式の根が整数に十分近い場合、丸める必要がありました。

これらの時間をクエリに追加し、昇順に並べ替えます。 時刻が一致する場合、エントリの時刻に対応する時刻が最初に送信され、次にリクエストが送信され、最後に危険ゾーンを離れる時刻が送信されます。 危険地帯にあるmet石の数を数えるカウンターを開始します。 現在の時刻が入力時刻の場合、それを増やします。 リクエストの場合は、このリクエストに対する回答を書き留めます。それ以外の場合は、回答を減らします。

ランタイムO（（n + m）•log（n + m））



問題E.テレポート

アイデア：アンナマロバ

実装： Boris Minaev

分析：ボリス・ミナエフ



便宜上、iと同様に、都市iに通じる道路の数を示します。 まず、効果的な旅行計画があるかどうかを判断する必要があります。 まず、 _i ≠0かつ_j ≠0であり、iとjの間に道がないような2つの都市iとjがある場合、計画を構築できません。 パスには、道路だけでなくテレポーターも含めることができることに注意してください。

すべての道路を通るいくつかのパスをすでに構築しているとします。 テレポートで接続されていないすべての都市が、途中の最初または最後の都市ではないことは明らかです。 2つの都市iとjがテレポートで接続されており、途中で最初の都市でも最後の都市でもない場合、 _{iでは j}と等しくなります。

パスの端にある都市に何が起こるか考えてください。 まず、都市iがjにテレポートされ、パスの最後にある場合、 _i =j + 1で（jもパスの終わりである場合を除く）。 さらに、パスが都市iで始まり、都市iで終わる場合、 _i =j + 2になります。都市が別の場所にテレポートで接続されておらず、パスの一方の端にある場合、 _iのある都市は奇数になります。

その結果、パスの存在を確認するには、次の手順を実行する必要があります。 各都市に対して特定の値a _iを計算します。 都市iがjによってテレポートに接続されている場合、a _i = max（0、c _i -c _j ）。 それ以外の場合、a _i =i mod2。すべてのa _iの合計が2または0に等しい場合、パスは存在し、そうでない場合は存在しません。

この国を訪問する計画の作成は、通常のコラムでのオイラーパスの作成に似ています。 _i ≠0で上から検索を開始する必要があります。 存在しない場合は、 _i ≠0の人と一緒に移動します。次の頂点に移動するときに、テレポートで別の頂点に接続されている場合は、その頂点に移動してさらに検索を続ける必要があります。 パスが実際に完全に見つかったという証明は、通常のグラフにおけるオイラーパスの存在の証明に似ています。

結果の難易度はO（n + m + k）です。



問題の解決策はすべて、 ロシアコードカップの公式ウェブサイトでも公開されます。 最後まで読んで興奮を感じた人は、次の予選ラウンドに登録できます -まだ時間があります！