Mischeviouslittleelfによる真夜中の剣
4月2日、 ロシアコードカップ2017の最初の予選ラウンドが開催され 、過去3年間の参加記録が破られました。 ラウンドのタスクの数と分析を提供します。
A. 火星のバレーボール
B. 壁画
C. 魔法のアーティファクト
D. メモリマネージャー
E. フォックス
ラウンドに参加した4552人の参加者のうち、1001人は今年だけRCCを発見した新人です。 今回は2015年と2016年の2倍のアクティブな参加者がいました！ 合計で6586個のソリューションが送信されました。 いつものように、最も人気のあるものはさまざまなバリエーションのC ++です（2346ソリューション-11番目のバージョンのプラスのC ++ 14、1425と、それぞれGNU C ++ 6.2およびVisual C ++ 2013を備えた約500のソリューション）。 Java 8.0（649）で人気が2位、Python（PyPy 2.4.0でPython 3.5 + 60ソリューションで402）で3位。 スポーツプログラミングで最も不人気なのは、Perl、D、およびHaskellであることが判明しました（最後に、彼らはラウンド全体で1つのソリューションを正確に作成しました）。 サポートされているすべての言語のリストは、 ここにあります 。
ラウンドの結果によると、200名の参加者が5月14日に開催される予選ラウンドに参加しました。 しかし、5つすべての問題を解決したのはそのうちの8つだけでした。 ここで一般的な結果を見ることができます。累積ペナルティ時間に応じて、トップの残りから真剣に離脱した5人をリストします。
- エフゲニー・カプン、サンクトペテルブルク
- スタニスラフ・エルショフ、サンクトペテルブルク
- ピーター・ミトリチェフ、チューリッヒ、スイス
- So島誠、東京、日本
- マキシム・フィニュティン、トリアッティ
資格をお持ちのすべての人を祝福します。 今週の4月16日日曜日、モスクワ時間12:00から14:00に開催される第2予選で、他の皆さんに幸運を祈ります。
A.火星のバレーボール
2秒の制限時間
256 MBのメモリ制限
火星でのバレーボールの試合は、 kポイントまでの2つのチームによって行われますが、勝つためには、ギャップは少なくとも2ポイントでなければなりません。 各ボールについて、チームの1つが正確に1ポイントを獲得します。
現在、最初のチームのスコアはxで、2番目のチームのスコアはyです。 試合終了までにプレーするゴールの最小数は？
入力データ
入力には、いくつかのテストスイートが含まれます。 最初の行には、テスト数t （1≤t≤5000）が含まれています。
各テストケースは、スペースで区切られた3つの整数、 k 、 x 、 y （1≤k≤100; 0≤x、y≤100）を含む1行で記述されます。
正しい未完のゲームで得点が得られることが保証されています。
インプリント
テストごとに、個別の行に答えを印刷します-試合の終了前にプレーされるゴールの最小数。
実行する必要がある最初の観察：ゲームの期間を最小限に抑えるために、最高スコアのチームのみがポイントを獲得する必要があります。 いずれかのチームの勝利条件を考慮してください。 少なくともkポイントを獲得し、負けたチームを少なくとも2ポイント追い越す必要があります。
最終的な答え： max （ k 、 min （ x 、 y ）+ 2） -max （ x 、 y ）。
B.壁画
2秒の制限時間
256 MBのメモリ制限
少女マーシャは彼女の部屋の壁を見ています。 壁には正方形のタイルが並んでいますが、一部ではなくランプが取り付けられています。 したがって、壁は、サイズがn × mの市松模様の長方形で、一部のセルにはランプがあると想像できます。
マーシャには、 k種類の色の塗料があります。 Mashaは、壁のすべてのタイルをペイントして、壁の端または両端のランプで囲まれたタイルの垂直または水平セグメントで、色が繰り返されないようにします。 この場合、Mashaはもちろんペイントしません。 マーシャはすべての色を使用する必要はありません。
マーシャは、壁の塗り方を理解するように頼みます。
入力データ
入力には、いくつかのテストスイートが含まれます。 最初の行には、テストの数tが含まれています。
各テストの説明は次のとおりです：テストの説明の最初の行には、3つの数値n 、 m 、 k （1≤n、 m≤100、1≤k≤max （ n 、 m ））が含まれています-壁の寸法とMashaが持っているさまざまな色の数。
次のn行には、それぞれa ijの m個の数字が含まれています。
- ランプが位置（ i 、 j ）にある場合、 a ij = 0。
- タイルが位置（ i 、 j ）にある場合、 a ij = 1。
すべてのテストのタイルとランプの総数は10 5を超えません。
インプリント
個別の行の各テストについて、最初にその答えを印刷します。
- いいえ、マーシャが望むように壁をペイントする方法がない場合。
- はい、再描画する方法がある場合。 この場合、次のn行でm番号b ij-位置（ i 、 j ）のタイルの色、またはこの位置にランプがある場合は0を印刷します。 適切な色が複数ある場合は、それらのいずれかを印刷します。
この問題を解決するために、条件を満たすために最低限必要な色の数を見つけます。 これを行うには、タイルの最も長い連続したセグメントを垂直または水平に見つけます。 このセグメントの長さをLに等しくします。
次に、正方形L × Lを想像してください。最初の行は1からLまでの数字のシーケンスであり、次の各行は前の行を右に循環シフトすることによって取得されます。 これらの正方形を使用して、ランプを忘れずに、余分な部分を捨てて元の長方形を並べます。 たとえば、 L = 4の場合、タイリングは次のように開始されます。
1 2 3 4 1 2 3 4 1 2
2 3 4 1 2 3 4 1 2 3
3 4 1 2 3 4 1 2 3 4
...
このタイリングは問題の条件を満たします。 これは 、長さLの任意の水平および垂直セグメントについて、すべての色が異なること、したがって短い長さについても満たされるためです。
Mashaの色がLよりも少ない場合、答えはありません。
C.魔法のアーティファクト
2秒の制限時間
256 MBのメモリ制限
マキシムはコンピューターゲームをプレイしています。 1からnまでの番号が付けられたnレベルで構成されます。 これらは、マキシムがi秒を費やすi番目のレベルで、任意の順序で完了することができます。
さらに、マキシムはキャラクターを強化する魔法のアーティファクトを見つけることができます。 ゲームにはアーティファクトが1つだけあり、その場所は正確にはわかりません-i番目のレベルでは、確率p iで配置されます。 アーティファクトを受け取った後、プレイがはるかに簡単になります-マキシムは、 i番目のレベルをb i秒で渡します（ b i≤a i ）。 マキシムが見つけたレベルではアーティファクトが機能しないことに注意してください。
マキシムは、ゲーム時間の数学的期待を最小限に抑えるために、この順序でレベルを完了することを望んでいます。 合格レベルの特定の順序を選択することで、彼が達成できる最小数学的期待値を計算するのを手伝います。 マキシムは事前にレベルの順序を選択しますが、この順序はアーティファクトのレベルに依存するものではありません。
確率変数の数学的期待値は、この結果の確率と量の値の積のすべての可能な結果の合計です。 この場合、結果はアーティファクトのレベルに対応し、数量の値は、アーティファクトがこのレベルにある場合の通過時間であり、マキシムは選択された順序でレベルを渡します。
入力データ
入力には、いくつかのテストケースが含まれます。 最初の行には1つの数値t-テストの数（1≤t≤1000）が含まれます。
各テストの説明は次のとおりです。最初の行には、数値n-レベル数（1≤n≤10 5 ）が含まれます。
次のn行はレベルを示します。 それらのそれぞれは、3つの整数で与えられます： a i 、 b i 、 x i-アーティファクトを見つける前後のレベルの経過時間、およびこのレベルでアーティファクトを見つける確率の計算に役立つ値。 確率は式p i = x i / 10 7 （1≤b i≤a i≤10 5 ; 0≤x i≤10 7 ;すべてのx iの合計は10 7に等しい）によって計算されます。
すべてのテストの合計nは5・10 5を超えません。
インプリント
テストごとに1つの数字を印刷します。合格レベルの順序を最適に選択して、ゲーム時間の数学的予想を印刷します。 絶対誤差または相対誤差が10-6を超えない場合、答えは正しいと見なされます。
c iで、 i番目のレベルのアーティファクトからマキシムが受け取る時間ゲインを示します： c i = a i - b i 。
レベルを1、2、...、 nの順序で進めます。 アーティファクトがi番目のレベルで見つかった場合、通過時間はb jとc 1 + ... + c iの値の合計に等しくなります。 次に、移動時間の数学的な期待値は次のとおりです。
b 1 + ... + b n + p 1・c 1 + p 2・（ c 1 + c 2 ）+ ... + p n・（ c 1 + ... + c n ）。
b 1 + ... + b nはレベルの順序に依存しないため、合計の残りの部分を減らすように努力します。 括弧を開くと、i≤kであるように、すべてのペアi 、 kの合計c i・p kに等しいことがわかります。
レベルiとi + 1を入れ替えた場合、合計がどのように変化するかを見てみましょう。c i・p kの項のうち、 c i・p i + 1のみが変化します-c i + 1・p iに置き換えられます。 レベルの順序が最適な場合、 c i・p i + 1≤c i + 1・p i （それ以外の場合、それらを交換して回答を改善できます）。 この不等式を変換します。
c i / p i≤c i + 1 / p i + 1。
1からn -1までのすべてのiの最適な答えでは、この不等式は真実です。 したがって、最適な答えでは、レベルはc i / p iでソートされます。それを取得するには、それらをソートする必要があります。 p i = 0の場合、 c i / p i =∞と仮定できることに注意してください。
c i / pで並べ替えるには注意が必要です。 除算が浮動小数点数で実行される場合、 c i = p i = 0の場合、エラーが発生するNaNが得られます。 コンパレータc i・p k < c k・p iを使用して、分数c i / p iとc k / p kを比較すると、 c i = p i = 0の場合、結果は常にfalseになり 、間違ったソート。 したがって、 c i = p i = 0のレベルは個別に処理する必要があります。 これらのレベルはいつでも完了できます。固定用語b iを除き、それらが答えに寄与していないことは簡単にわかります。 たとえば、最後に配置できます。
ソート後、目的の数学的期待値を計算する必要があります。 プレフィックスの合計c iを使用した上記の式を使用して計算されます。
D.メモリマネージャー
制限時間-3秒
256 MBのメモリ制限
Petyaは、磁気7Dブロックに基づくストレージ用に独自のMEM 2.0メモリマネージャーを積極的に開発しています。 ただし、ストレージからユーザーへのデータの最適な出力という問題に直面しました。
合計で、Petitのマネージャーは1からnまでの番号が付けられたn個のブロックを格納し、1つ以上のデータを発行するためのq要求があります。 要求は、到着した順に処理する必要があります。
Petyaにはデータ出力用のk個のポインターがあり、各ポインターはブロックの1つを指します。 最初、Petyaは任意のブロックセットにポインターを置くことができます。
Petinマネージャーは、少なくとも1つのポインターが各ブロックを指している場合、任意の数のブロックから即座にデータを返すことができます。 そうでない場合、マネージャーは最初に条件が満たされるようにポインターを再配置し、次にデータを提供します。i番目の要求に対するこの操作の実行時間はs iミリ秒です。任意の数のポインターを再配置できます。
Petyaは、すべてのユーザー要求への合計応答時間が最小限になるように、マネージャーにポインターの順列を実装したいと考えています。 リクエストは到着順に処理する必要があり、リクエストを交換することはできません。 彼を助けてください。
例に示されているテストを検討してください。
最初のテストでは、Petyaは最初にブロック1、2、および4にポインターを置くことができます。その後、最初の2つのクエリが即座に実行されます。 s 3 = 1ミリ秒の3番目の要求の前に、ブロック2、3および5へのポインターを置くことができ、 s 4 = 1ミリ秒の4番目の要求の前に、ブロック1、3および5にポインターを置くことができます。すべての要求の合計時間はs 3 + s 4 = 2ミリ秒。
2番目のテストでは、Peteは最初の2つのクエリを（ブロック1、2、4へのポインターを最初に配置することで）すぐに実行することは有益ではありません。 したがって、Petitの最適な戦略は、 s 2 = 1ミリ秒のブロック1、3、4への2番目の要求の前、 s 4のブロック1、3、5へのポインターの最後の要求の前に、最初にブロック1、2および3へのポインターを置くことです= 3ミリ秒。 リクエストの合計応答時間s 2 + s 4 = 4ミリ秒。
入力データ
入力には、いくつかのテストスイートが含まれます。 最初の行には、テスト数t （1≤t≤1000）が含まれています。
以下のtテストのそれぞれは、次のように説明されています。テストの説明の最初の行には、3つの数値n 、 k 、 q-マネージャー内のブロック数、ポインターの数、ユーザークエリの数がそれぞれ含まれています（ 1≤k≤n≤10 5、1≤q≤10 6 ）。
次の行には、 q個の整数s i - i番目の要求に応答するときにポインターを再配置するのに必要な時間（ 1≤s i≤10 4 ）が含まれます。
次のq行にはユーザー要求の説明が含まれ、 i番目の要求は1行で記述されます。最初の数字c iはユーザーが受信したいデータブロックの数を表し（1≤c i≤k ）、次のc i番号はこれらのブロックの数b昇順のi 、 j （1≤b i 、j≤n）。
同じ入力データのすべてのテストの合計nが10 5を超えないこと、および同じ入力データのすべてのテストの合計c iが10 6を超えないことが保証されます。
インプリント
テストごとに、その回答（すべてのユーザーリクエストに対する最小合計応答時間）を出力します。
まず、 q iクエリごとに、 go i - q j 、 q j + 1、...、 q iに最大k個の異なる数がある最小jを見つけます。これは、 j番目のクエリの前にこれを実行できることを意味しますj 、 j + 1、...、 iのリクエストが即座に実行されることを示すポインタを置きます。 これは、クエリ配列の最後から行く場合、 O （ sum （| q i |））で行われます。たとえば、2つのポインターを使用します。
ここで、動的プログラミングを使用して、 dp iの値を計算します。これは、最初のiクエリが完了することができる最小時間です。 go i = 0の場合、 dp i = 0です。そうでない場合、 dp i = min j = go i .. i （ dp j -1 + s j ）-変更するクエリjを選択します。ポインター、および対応するコストを支払います。 go iは減少しないため、 設定値dp j -1 + s jをサポートするか、「最小」操作でキューを使用することで、この値を計算できます。
E.フォックス
制限時間-3秒
256 MBのメモリ制限
Ilyaは、文字列アルゴリズム研究研究所（FOX）で働いています。 今、彼はそのような問題を解決しようとしています。
文字列の配列s 1 、 s 2 、...、 s nおよびqクエリを指定します。 各クエリは、2つの整数l iおよびr i （1≤l i≤r i≤n）で特徴付けられます。 要求に応答するには、次の手順を実行します。 次のように取得できる場合、表現可能な文字列を呼び出します.2つの文字列s xおよびs yを選択します。ここで、 l i≤x、y≤r i 、文字列s xの空でないプレフィックスを選択し、文字列s yの空でないサフィックスを選択し、それらの連結を取得します。 クエリへの応答は、指定されたl iおよびr iの異なる表現可能な文字列の数です。
たとえば、 s = [ abc 、 ab 、 ac 、 bcac ]とし、 l i = 2、 r i = 3を選択します。次の行が表示可能です。
x = 2、 y = 2： ab = a + b、 aab = a + ab 、 abb = ab + b 、 abab = ab + ab *。
x = 2、 y = 3： ac = a + c 、 aac = a + ac 、 abc = ab + c 、 abac = ab + ac 。
x = 3、 y = 2： ab = a + b 、 aab = a + ab 、 acb = ac + b 、 acab = ac + ab 。
x = 3、 y = 3： ac = a + c 、 aac = a + ac 、 acc = ac + c 、 acac = ac + ac 。
合計12の異なる表現可能な文字列。
イリヤが十分に迅速に問題を解決するのに役立ちます。
入力データ
最初の行には、それぞれ2つの整数nとq-単語とクエリの数が含まれます（1≤n、 q≤10 5 ）。
次のn行のそれぞれには、小文字のラテン文字で構成される空でない単語s iが含まれます。 すべての単語の合計長は10 5を超えません。
次のq行には、数値l i 、 r i （ 1≤l i≤r i≤n ）のペアが含まれます-それぞれi番目のクエリの左右の境界線。
インプリント
q行を印刷します。それらのi番目には、 i番目の要求に対する答えである単一の整数が含まれている必要があります。
最初に2つの特定の行の問題を検討します：最初の行の各文字と2番目の行の各文字の出現回数を計算します。最初の行の最初の文字と2番目の行の最後の文字は考慮しません。 答えを得るには、文字列の長さの積を計算し、この値からcnt1 [letter] * cnt2 [letter]の合計をすべての文字で減算する必要があります。 声明の証拠は演習として残します。そのようなタスクは、北部準々決勝-2015 （ http://neerc.ifmo.ru/archive/2015/northern/north-2015-statements.pdf 、タスクC）で提案されました。 参加者の広いサークルは、3つの準々決勝のカップでそれを決めることができました。
n行の場合、問題は同様の方法で解決されます。すべての行を接頭辞のボロンに追加し、すべての行を接尾辞のボロンに追加し、最初のボロンと2番目のボロン（ルートを除く）の頂点の数をカウントし、これら2つの数値を掛けます-パスを適用して生成できる行数接尾辞ボアのパスへの接頭辞ボアで。 繰り返しを差し引く必要があります。これは同様に行われます：接頭辞ボアでは、ルートからのエッジ上の文字を除いて、エッジ上の各文字の数が考慮され、これらの値が乗算され、この量はバーの頂点の数の積から減算されます
セグメントのリクエストに応答する方法を学ぶことは残っています。 sqrt分解を使用し、長さの合計に従って行をグループに分けます。 グループの合計長が長さの合計のルートより大きくなるまで、最後の行は非常に大きくなる可能性があります。
ここで、Moアルゴリズムを使用して、クエリを左境界線のブロックで並べ替え、右境界線で等しいブロックを並べ替えます。左境界線のブロックの変更の間、右境界線は右にのみ移動します。 ホウ素に線を追加するか、ホウ素から線を削除するには、サブツリー内の頂点の数をカウントし、それに応じて、ホウ素内の文字の出現回数をカウントします。
第2ラウンドのすべて！
お知らせします。第2ラウンドは、この日曜日、モスクワ時間の12:00からです。 この記事の執筆時点では、4,600人以上の参加者がすでに登録していますが、興味深いものになります。 今すぐ参加しよう ！
さらに、RCCとスポーツプログラミング全般に特化した電報のグループを開くことを決定しました。 ようこそ！