9月18日、2016 ロシアコードカップスポーツプログラミングチャンピオンシップの最後の最終ステージが開催されました。 苦闘の最初の場所はGennady Korotkevich 、2位と3位-それぞれVladislav EpifanovとNikolai Kalinin でした。
最終順位はこちらで確認できます。今年の賞金プールは、評価の最初の25か所に初めて分配されます。 これが唯一の革新ではありません。RCCで初めて、英語を話すプログラマーが参加する機会があり、そのうち4.5万人の参加者のうち1000人以上が参加しました。 競争の伝統的なCIS諸国に加えて、ドイツ、フィンランド、日本、スイス、中国、韓国の代表が最終ラウンドで戦いました。 さらに、今回はCodeforcesでミラーラウンドが開催されました-メインコンペティションの決勝直後に、全員が第1部門の特別に編成されたコンペティションで決勝の問題を解決する機会があり、200人を超えるプログラマーが参加しました。
従来、最終タスクの分析を提供しています（テストはこちらからダウンロードできます ）。
A.閉会式
B.サボテン恐怖症
C.宿題
D.スラローム
E.暗号
F.アレイカバレッジ
A.閉会式
制限時間 2秒
256 MBのメモリ制限
状態
Squanch Code Cupの閉会式は、 n × m人の大ホールで開催されます。 ホール自体はn列で構成され、各列にはmの椅子があります。 各椅子には2つの座標があります：（ x 、 y ）（1≤x≤n、1≤y≤m）。
ホールの入り口には2つの線がありました。k人は座標（0、0）のポイントにあり、 n・m - k人は座標（0、 m + 1）のポイントにあります。 各人は特定の場所へのチケットを持っている必要があります。 人が初期座標（ x 、 y ）を持つp 、場所へのチケット（ x p 、 y p ）を持っている場合、|を通過する必要があります。 x - x p | + | y - y p |。
誰もが自分のスタミナ、つまり、彼がどのくらいの距離を移動できるかを知っています。 あなたの仕事は、すべてのチケットを配布して、全員が自分の場所に到達できるかどうかを調べることです。
入力形式
入力の最初の行には、2つの自然数nとm （1≤n・m≤10 4 ）-ホールの寸法が含まれています。
2行目には、負でない整数がいくつか含まれています。 最初の数k （0≤k≤n・m ）は、初期座標（0、0）を持つ人の数を示します。 これらの人々のスタミナを示すk個の数字が続きます。
3行目には、負でない整数がいくつか含まれています。 最初の数字l （ l = n・m - k ）は、初期座標（0、 m + 1）を持つ人の数を示し、その後にこれらの人のスタミナを示すlの数字が続きます。
耐久性は、 n + mを超えない自然数で与えられます。
出力形式
説明どおりにチケットを配布できる場合は、「YES」を印刷します。 それ以外の場合は、「NO」を出力します。
例
入力データ：
2 2
3 3 3 2
1 3
出力データ：
はい
入力データ：
2 2
3 2 3 3
1 2
出力データ：
いや
この問題は、この貪欲なアルゴリズムの記述に対応する、最大でO （（ nm ） 2 ）の漸近線を使用した適切に記述されたソリューションで構成されていました。 セットを使用する場合、漸近性をO （ nm log （ nm ））に減らすことができます
B.サボテン恐怖症
制限時間 2秒
256 MBのメモリ制限
状態
ツリーは、循環のない接続された無向グラフです。 エッジサボテンは、ループと複数のエッジのない接続された無向グラフであり、各エッジは多くても1つの単純なサイクルにあります。
Vasyaにはrib骨サボテンがあり、各rib骨はある色で塗られています。 Vasyaは、サボテンから最小数のエッジを削除して、ツリーを取得したいと考えています。 同時に、彼は残りのdifferent骨の間の異なる色の数が最大であることを望んでいます。 彼がグラフにいくつの異なる色を残せるかを見つけるのを助けてください。
入力形式
最初の行には2つの整数n 、 m （2≤n≤10,000）が含まれています-それぞれVasyaグラフの頂点とエッジの数。
次のm行は、3つの整数u 、 v 、 c （ 1≤u 、v≤n、 u ≠ v 、1≤c≤m）-次のエッジを接続する頂点とその色を示します。 説明したグラフがエッジサボテンであることは保証されています。
出力形式
単一の整数-グラフに残せる異なる色の最大数を印刷します。
例
入力データ
4 4
1 2 4
2 3 1
3 4 2
4 2 3
インプリント
3
入力データ
7 9
1 2 1
2 3 4
3 1 5
1 4 5
4 5 2
5 1 6
1 6 4
6 7 6
7 1 3
インプリント
6
左葉がブロック、右葉が色の2部グラフを作成しましょう。 ブロックから、このブロック内の各色にエッジを描画します（色が複数回発生する場合は、複数のエッジを描画します）。 花rib骨からストックまで。 ブロックがブリッジの場合、エッジのソースからブロックまで、スループットは1、それ以外の場合はサイクル長より1少ないスループット。 このグラフの最大フローが答えになることは容易にわかります。
この問題でも、スレッドを使用せず、 O （ n ）で機能するソリューションがあります。これを演習として検討することをお勧めします。
C.宿題
制限時間 3秒
256 MBのメモリ制限
状態
今日、Petyaは数学の授業でひどく振る舞い、教師は彼に余分な宿題を与えることで彼を罰しました。 彼女は3つの数字n 、 m 、 kを彼に渡し、サイズn × mの長方形の市松模様のボードに1つ以上のセルをマークするように指示しました。 マークされたセルは、一貫した図を形成する必要があります。 この場合、3つのマークされたセルを選択して「コーナー」を形成するには、正確にk個の方法が必要です。選択された3つのセルはすべて2×2の正方形内にあります。
セルのセットは、接続された図を形成します。セットのセルから他のセルに到達できる場合、プロセス中にセルから側面に移動します。 Petyaはタスクが簡単ではないことを知っているので、プログラマーおよび親友として、このタスクで彼を助けるように頼みました。
入力形式
入力には、いくつかのテストスイートが含まれます。 最初の行には、テストの数t （1≤t≤100）が含まれています。 以下の各tテストは、3つの数値n 、 mおよびkの 1行で記述されます（3≤n、 m 、 n ×m≤10 5、0≤k≤10 9 ）。 すべてのテストの合計n × mが10 5を超えないことが保証されています。
出力形式
各テストについて、その答えを印刷します。 答えが存在する場合、 m文字のn行を印刷します。「*」はマークされたセルを意味し、「。」 -マークなし。 答えが存在しない場合は、1行に-1を出力します。 各テストの後、最後を除いて、空の文字列を出力します。
例
入力データ
3
3 3 4
3 3 5
3 3 3
インプリント
**。
**。
...
***
**。
...
。**
**。
* ...
- すべてのn 、 m <5のケースの分析を簡素化するために、徹底的な検索を開始します。 ここでは、非漸近的な最適化を避けてTL内に保つために、事前計算を行う価値がありました。
- さて、一般性を求めることなく、m≥5と仮定できます。
- テーブルに従って星を一列に並べ始めます（上から下の行、左から右の各行）。 各スター（極端なスターを除く）を追加すると、4つの新しいコーナーが追加されます。 アスタリスクが追加されると、3つの新しいコーナーが行の終わり、先頭に追加されます-1. kが4未満になるか、テーブルに空きセルが5つ未満になるとすぐにプロセスを停止します。
- イベントのさらなる開発は、2つのケースに分けられます。
- フリーラインを残しました
- 空き回線がありません
- 最初のケース。 空き線が残っている場合、 kが4未満であるため、中断しました。
- k = 0：追加する必要はありません、すべてが一緒になりました
- k = 1：現在の行に2つ以上のアスタリスクがすでにある場合は、次の行の先頭にアスタリスクを入れます。そうでない場合は、現在の行の終わりにアスタリスクを入れます
- k = 2：現在の行に3つ以上のアスタリスクが既にある場合は、次の行の2列目にアスタリスクを入れます。そうでない場合は、現在の最後から2番目のセルに入れます
- k = 3：現在の行にすでに4つ以上のアスタリスクがある場合、次の行の1列目と3列目にアスタリスクを入れます。 3が設定されている場合、2番目の列に次の列、最後から2番目の列に配置します。 2の場合-次の行の先頭から現在の行の最後から2番目の列まで。 1つの場合-現在の行のm -1およびm -3列にアスタリスクを入れます（最初から番号を付けます）。
- 2番目のケース。 テーブルには、アスタリスクを配置できる4つの空きセルがあります。 単純なケースの列挙により、これらのセルにアスタリスクを入れることにより、 kの次の値を取得できると推測できます：{0、1、2、3、4、5、6、8、9、12、15}。 これらのケースの分析は、演習として読者に任されています。
- また、m≥5かつk = 2 *（ m -1）-8-という3× mの長方形の場合も忘れないでください。この場合、最初の列を空のままにして、残りの列を埋める必要があります。
D.スラローム
制限時間 2秒
256 MBのメモリ制限
状態
少女マーシャはウィンタースポーツが大好きで、今日はスキースラロームに行かなければなりません。 トラックは回路図のn × mチェックボックスです。 いくつかのセルを占める長方形の障害物がフィールドに配置されます。 Mashaは、座標（1、1）のセルからセル（ n 、 m ）に到達する必要があります。 この場合、各セルから、1つ上のセルまたは1つ右のセルに移動できます。 障害物があるセルでは、取得することは不可能です。
したがって、各障害物は2つの方法で回避できます。障害物は、高速道路に沿った移動軌跡の左側または右側のいずれかに残ります。 マーシャは多様性を愛しており、トラックに乗る方法はいくつあるのだろうと考えています。 ルートの通路は、マーシャの軌跡の左側のパスと右側のパスに障害物が少なくとも1つある場合、異なると見なされます。
あなたの仕事は、マーシャが軌道に乗るためのさまざまな方法を見つけるのを助けることです。 答えは大きく、Mashaは10 9 + 7を法とする値に満足します。以下の図では、条件からのテストが分析されます。
入力形式
入力の最初の行には、3つの自然数n 、 m 、およびk （3≤n、m≤10 6、0≤k≤10 5 ）-それぞれ経路の次元と障害物の数が含まれています。 次のk行には、4つの自然数x 1 、 y 1 、 x 2 、 y 2 （1≤x 1≤x 2≤n 、1≤y 1≤y 2≤m）が含まれます-障害物の左下および右上隅の座標。 セル（1、1）および（ n 、 m ）には障害物がなく、すべての障害物に交差点がない（ただし、接触できる）ことが保証されています。
出力形式
出力ファイルに単一の数字を出力します。これは、トラックを通過するさまざまな方法の数を10 9 + 7で割った余りです。
例
入力データ
3 3 0
インプリント
1
入力データ
4 5 1
2 2 3 4
インプリント
2
入力データ
5 5 3
2 2 2 3
4 2 5 2
4 4 4 4
インプリント
3
動的計画法により問題を解決します。 クラスごとに、最低パスを検討します。通過するセルの高さの合計は最小です。 動的プログラミングの状態は、特定のセルを通過するそのような下位パスの数です。 次に、障害物に出会うと、その上部にあるセルを通過するすべてのパスを2つに分けることができます。 つまり、上部境界より上のセルで障害物を処理する場合、上部より下のセルの値の合計を追加する必要があり、そこからパスを分割できます。
このアルゴリズムの単純な実装にはO （ nm ）メモリとO （ nm 2 ）時間が必要であったため、セグメントのツリーを使用して、動的プログラミング遷移中に合計の計算を最適化し、フィールド全体だけでなく現在の列のみを保存する必要があります。 したがって、 O （ m ）メモリが取得され、ランタイムはO （ n log m ）になります。
E.暗号
制限時間 2秒
256 MBのメモリ制限
状態
最近、ボルヤは大きな電子スコアボードを見ました。 スコアボードでは数字が暗号化されています。 数字自体はn桁で構成され、各数字はラテン文字で書かれています。 ボードの横には、暗号化スキームを説明するプレートがあります。 したがって、各桁iおよび桁jについて 、エンコードされるシンボルcが既知です。 この場合、同じ文字を異なる数字に対応させることができます。 1秒ごとに、スコアボードにエンコードされている数値が1つ増えます。 そして、スコアボードで暗号化された数字のn桁すべてが9になった後、1秒でスコアボードが非常に大きな音を出します。
アンドレイは、スコアボードで最初に暗号化された番号を知っています。 彼は、Boryaがこの数値を正確に決定できる秒数を知りました。 Boryaが正確に時間を測定できること、およびスコアボード上の数値が初めてスコアボードを見た1秒後に正確に変化することを考慮してください。
入力形式
最初の行には、整数t （1≤t≤100）-テストケースの数が含まれています。 各テストの説明は、数字n （1≤n≤18）-暗号化された数字の文字数で始まります。 次の行には、スペースなしのn桁の数字（先行ゼロが含まれる場合があります）-暗号化された番号が含まれます。 次のn行には、それぞれ10文字が含まれています。 行iのj番目の文字がcに等しい場合、 i番目の桁j -1（上位ビットについては前に説明します）は文字cでエンコードされます 。
出力形式
各テストケースについて、先頭にゼロを付けない単一の整数（数値を復号化するのに必要な最小秒数）を個別の行に出力します。
例
入力データ
3
2
42
abcdefghij
ジフフェドクバ
2
42
aaaaaaaaaaa
aaaaaaaaaaa
1
2
abcdabcdff
インプリント
0
58
2
ソリューションの主なアイデアは、番号が10 n -1 個すべてと区別できることを確認する必要がないことです。 正確に1桁が変更された数字と数字を区別できる場合、他のすべての数字と区別できると主張されています。 したがって、数字を他の9 n個と区別できる最初の瞬間を見つける必要があります。
このサブタスクは10 nよりも速く解決できることに注意してください。 これを行うには、2つの数値とその値を区別できるカテゴリをソートします。 その後、数値の1つが正確にこの値を取る最初の瞬間を見つけ、2つの数値を区別できるかどうかを確認します。 したがって、桁数から多項式時間で機能するソリューションが得られます。
F.アレイカバレッジ
制限時間 3秒
256 MBのメモリ制限
状態
Mishaにはn個の整数の配列があります。 彼は、配列の各要素に対して、それを含む少なくとも1つの選択されたセグメントが存在するように、 k個の異なるサブセグメントを選択したいと考えています。 同時に、ミーシャは、各セグメントの数値を合計し、結果の金額を合計すると、合計金額が最大になることを望んでいます。
入力形式
最初の行には2つの整数n 、 k （1≤n≤100 000、1≤k≤n・（ n + 1）/ 2）-配列内の要素の数と選択するセグメントの数が含まれます。
2行目には、 n個の整数a i （-50 000≤a i≤50 000）-配列の要素が含まれます。
出力形式
単一の整数を印刷します-各要素が少なくとも1つのセグメントでカバーされるようにk個のセグメントを選択することで達成できるセグメント上の数値の合計の最大合計。
例
入力データ
5 4
6 -4 -10 -4 7
インプリント
11
少し脱線しましょう。 n 2 log nの問題をどのように解決できるかを検討してください。 x-回答の最大セグメント数（ O （ n ）バリアント、 最小 （ k - n 、0）の最大セグメントが回答に含まれるので）を見てみましょう。 インデックスi 1 、...、 i mの要素はカバーされないままにしておき、 k - xセグメントを使用してそれらをカバーする必要があります。 これらのk - xセグメントのそれぞれには、少なくとも1つのi jthが含まれている必要があり、2つのセグメントはi jthセグメントに沿って交差できないことに注意してください。 これらのk - xセグメントを辞書式に並べ替えることができ、 l番目のセグメントが番号i jをカバーし、 l + 1番目のセグメントがi j + 1をカバーする場合、これら2つのセグメントはセグメントのサブセグメント[ i j + 1 ; i j + 1-1]、またはセグメントの一部のサブセグメントで交差しない[ i j + 1; i j + 1-1 ]。 したがって、各セグメントに対して[ i j + 1; i j + 1-1]最大サブセグメントの最大値から最小値を引いた数を書き込みます。最適なカバレッジは配列全体を取得することですが、最小プレフィックス（ i 1まで ）、最小サフィックス（ i mから）、およびk- x書き出された最大数。 したがって、彼らはn 2 log nの問題を解決しました。
このソリューションを最適化するために、セグメント[ i j + 1; i j + 1-1 ]順序付きセット。 新しい最大セグメントを追加する場合、いくつかのi j -xを削除し、影響を受けるセグメントの最大および最小サブセグメントをセットで再計算する必要があります（これはO （1）で実行でき、サブセグメントのプレフィックスとサフィックスの最大量を知っています）、合計k - xの最大値を取得しますセットからの数字。 削除の総数はi j -x O （ n ）なので、この部分はすべてO （ n log n ）で機能します。
***
ロシアコードカップチャンピオンシップは、ロシアのIT産業の発展を目的としたMail.Ruグループの取り組みの1つであり、 IT.Mail.Ruリソースによって統合されています。 IT.Mail.Ruプラットフォームは、ITに興味があり、この分野で専門的に開発しようと努力している人々のために作成されました。 このプロジェクトは、テクノパークMSTUでの教育プロジェクトであるロシアAIカップ、ロシアコードカップ、ロシアディベロッパーズカップのチャンピオンシップを組み合わせたものです。 バウマン、モスクワ州立大学テクノスフィア MIPTのM.V. LomonosovとTechnotrek さらに、IT.Mail.Ruでは、人気のあるプログラミング言語の知識をテストしたり、ITの世界から重要なニュースを学んだり、関連するイベントやITトピックに関する講義の放送を見たり見たりするためにテストを使用できます。