ピクナートのマーサートンネル

5月8日、 ロシアコードカップ2016チャンピオンシップの最初の予選ラウンドが行われました。 今年はプログラマーのコンテストも初めて英語で開催されるため、外国人参加者にとって言語の壁はもはや障害になりません。 最初の予選ラウンドを完了するには、5つの問題を解決する必要がありました。 決定は2時間以内に行われました。 正確性だけでなく、ソリューションの速度も考慮されました。 合計で3559人がこのラウンドに参加し、そのうちの最初の200の場所が次のステージに進みました。 それまでの間、提案された問題の解決策を見てみましょう。

1. バイナリ文字列
2. 電車とトンネル
3. 美しい休憩
4. タスク準備
5. 同様の地下鉄

タスクA.バイナリ文字列

条件：

制限時間2秒
256 MBのメモリ制限

Petyaはボード上にゼロと1の長さnの文字列を書きました。 その後、彼は連続した文字のすべてのペアを見て、ペア00が1回発生し 、ペア01がb回発生し、ペア10がc回発生し、ペア11- d回（ a + b + c + d = n -1 ）

いじめっ子のグリシャは彼の線を消した。 悲しくなったペティアは、対応する隣接するキャラクターのペアの数について同じ条件が満たされている行を復元したいと考えています。 彼を助けて！

入力フォーマット：

いくつかのテストケースが入力に送信されます。 最初の行には、正の整数t （1≤t≤10,000）-テストケースの数が含まれています。

各テスト例は、4つの数字a 、 b 、 c 、およびd （0≤a 、b、c、 d≤20）を含む1行で記述されます-隣接する文字のペアの数はそれぞれ00、01、10、11に等しい。

a + b + c + d≥1が保証されます。

出力形式：

t行を印刷します。 テストケースごとに、ゼロと1からなる検索文字列を出力します。そのような文字列が存在しない場合は不可能です。

例：

入力データ
5
0 0 1 0
1 0 0 1
1 1 1 1
2 1 1 2
1 2 3 4

インプリント
10
無理
00110
0001110
11111001010

解決策：

まず、次の2つの条件のいずれかが満たされている場合にのみ、タスクに解決策がないことに注意してください。

• •または| b-c | > 1
• •またはb = 0、 c = 0、同時にa ≠0およびd ≠0

残りのケースについては、2段階で解決します：最初に、行01および10の条件を満たす最小文字列を収集し、最初のゼロがa -1ゼロに達した後、および最初に満たされたユニットd -1ユニットに追加します。 明らかに、このようなアクションによる01と10の状態は悪化しません。

タスクB.列車とトンネル

条件：

制限時間2秒
256 MBのメモリ制限

Petyaは旅行に行くことにしました。 今、彼は電車に乗っています。 列車はn台の車で構成され、 i番目の車の長さは_iメートルです。 車間の距離は無視できます。

Petyaは、一部の車にライトが点灯していることに気付きました。 列車はhメートルの長さの鉄道トンネルに近づいています。 Petyaは、トンネル内のある時点で、ライトがオフになっている車だけを望んでいません。 すべての車の中で、トンネル内にある長さがゼロでない特定のセクションで、光が点灯しない場合、Petyaは時間の暗い瞬間を呼び出します。 そのような瞬間の出現を排除するために、Petyaは一部の車のライトをオンにしたいと考えています。

トンネルの通過中に暗闇が一瞬もないように、Petyaが最小台数の車のライトをオンにするのを助けてください。

入力フォーマット：

入力には、いくつかのテストケースが含まれます。 最初の行には1つの数値t （1≤t≤100）-テストの数が含まれています。 以下はテストの説明です。

各テストは次のように定義されます。最初の行には2つの正の整数n 、 h （1≤n≤10 5、1≤h≤10 ⁹ ）が含まれます-列車内の車の数とメートル単位のトンネルの長さ。 テストの次の行には、 n個の自然数a _i （1≤a i≤10 ⁹ ）-車の長さ（メートル）が含まれています。 次の行にはn個の数値が含まれます。i番目の車でライトが最初にオンになっている場合、 i番目は1です。それ以外の場合は0です。 車は列車の先頭から末尾までリストされています。

すべてのテストのn値の合計は10 ^6を超えません。

出力形式：

テストケースごとに、1つの数字を印刷します。これは、ライトをオンにする車の最小数です。

例：

入力データ
2
7 10
5 3 4 5 9 9 9
1 0 0 0 1 0 0
5 2
1 2 3 1 1
1 1 0 1 1

インプリント
2
1

解決策：

電車全体を光のない車のセグメントに分割します。 そのような車の各グループを通過し、車の全長がh以上になる車でライトを点灯します。 明らかに、この戦略は最も少ない結果をもたらします。 また、最初の車と最後の車のライトを必ずオンにする必要があります。トンネルに入るときとトンネルを出るとき、これらの車は暗い時間を形成します。

問題C.美しいパーティション

条件：

制限時間2秒
256 MBのメモリ制限

今日、数学の授業で学校で、ピートは多くの複数の数字の最大公約数について話されました。 彼はこのトピックをとても気に入ったので、すべてのタスクでそれを探し始めました。

そのため、コンピューターサイエンスのレッスンで、教師はボード上に整数の配列を書きました。ペティアはすぐに、彼の要素が2つのセットM ₁とM _2に分割され、 gcd（M ₁ ）とgcd（M ₂ ）が非常に大きくなることに気付きました。 ここで、 gcd（M）（Mは空でない数のセット）は、 Mのすべての数の最大公約数を意味します。

Petyaは問題を一般化することを決定しました：この数の配列に対して、彼は、 min（gcd（M ₁ ） 、 gcd（M ₂ ））が可能な限り大きくなるように、 ₂つの空でないセットM ₁およびM _2に要素のパーティションを見つけたいと考えています。 このタスクで彼を助けてください。

入力フォーマット：

入力には、いくつかのテストスイートが含まれます。 最初の行には、テスト数t （1≤t≤1000）が含まれています。
各テストの説明は次のとおりです。テストの説明の最初の行には、数n （2≤n≤5•10 ⁴ ）-配列内の要素の数が含まれます。 次の行には、 n個の数値a _i （1≤a i≤10 ⁹ ）-配列のelement1が含まれます。

同じ入力データのすべてのテストでのn値の合計は、5•10 ^4を超えません。

出力形式：

テストケースごとに、個別の行に回答を出力します。可能な最大値はmin（gcd（M ₁ ） 、 gcd（M ₂ ））です。

例：

入力データ
3
5
3 2 4 6 9
3
3 5 14
4
6 4 6 6

インプリント
2
1
4

解決策：

配列の最初の要素は、 M ₁またはM _2にあります。 一般性を失うことなく、 M _1に含まれると仮定します。 次に、 [1]はgcd（M ₁ ）で除算されます。つまり、 gcd（M ₁ ）は[1]の約数です。

すべての約数a [1]をソートします（10 ⁹までの数の場合、それらの数は1344以下です）。 現在の除数dを考慮すると、 M _1で dで割り切れる配列のすべての要素を取得します（このgcd（M ₁ ）はd未満にならず、 M _2の要素が少ないほど、 gcd（M ₂ ）が多くなります）。 M _2の他のすべての要素と値min（gcd（M ₁ ） 、 gcd（M ₂ ））で回答を更新します。 この場合gcdが無限に等しいことを考慮すると、 M ₂が空になるという事実を無視できることに注意してください。この場合のすべての要素はdで割り切れるため、 gcd（M ₂ ）は少なくともdになります。

解の漸近的挙動はO（sqrt（a [1]）+ d（a [1]）• n ）です。ここで、 d（a [1]）≤1344です。

タスクD.タスクの準備

条件：

制限時間2秒
256 MBのメモリ制限

アンドリューは、選手権に向けて準備する必要のあるn個のタスクを考え出しました。 各タスクiについて、開発に必要な時間t _iを推定しました。 アンドレイは友人を招待して準備を手伝ってもらいたいと考えています。

彼はまだ何人の友人が彼を助けるかを正確に知りませんが、彼のアシスタントに仕事を公平に分配したいと考えています。 したがって、各タスクについて、彼はそのような整数x _iを決定して、各友人がその準備にちょうどx _i分費やしたいと考えています。 アンドレイは、すべての友達が準備に少なくともt _i分を費やすと、タスクiは高品質になると信じています。

Andreiは、タスクをうまく開発するのにかかる時間を誤って推定したことに気付き、 t _iを1 ずつ増やしたり減らしたりすることがあります。

タスクt _iを準備するための初期時間の見積もり_{が与えられ}ます。 m個のリクエストを処理する必要があります。 各リクエストの説明は次のとおりです。

• 1 i-アンドレイはt _iの値を1増やすことを決めました。
• 2 i -Andreyはt _iの値を1つ減らすことにしました。
• 3 k -Andreyは、 k人の友人が彼を助けた場合に1人の友人がタスクを準備するのに必要な合計時間を知りたいと思っています。

入力フォーマット：

最初の行には、2つの整数nとm （1≤n、m≤10 ⁵ ）-タスクの数とクエリの数が含まれています。

次の行には、 n個の整数t _i （1≤t i≤5•10 ⁵ ）-Andreiの初期評価に従ってi番目のタスクを準備するのにかかる時間が含まれています。

次のm行がプロンプトに従います。 それらはそれぞれ2つの数字で記述され、最初の数字はそのタイプです。 タイプ1または2の場合、2番目の数値i （1≤i≤n）はタスク番号です。 タイプ3の場合、2番目の数値k （1≤k≤5•10 ⁵ ）は、Andreyを支援する友人の数です。

t _iは常に1〜5•10 ^5の範囲にあることが保証されています。

出力形式：

3番目のタイプのクエリごとに1つの数字を印刷します。これは、1人のタスクを準備するのに必要な合計時間です。

例：

入力データ
5 11
1 2 3 4 5
3 1
3 2
3 3
1 1
3 1
3 2
3 3
2 5
3 1
3 2
3 3

インプリント
15
9
7
16
9
7
15
8
7

解決策：

そもそも、時間を変更するリクエストがなければ、問題を解決します。 配列t _iから、新しい配列cnt _{j を}生成します。この配列には、 j分を費やす必要があるタスクの数を格納し、そのプレフィックス量の配列を計算します。 次に、各友人がk人しかいない場合に費やす時間は、 O（MAX / k）としてカウントできます。MAXは、タスクに必要な最大時間です（1、2、... MAX / k分かかるタスクを選別するだけです） 。 ご存知のように、1からMAXまでのすべてのkに対するこのようなアルゴリズムの合計動作時間はO（MAXlog（MAX））です。

次に、タスクに必要な時間がtからt + 1に変化したときに何が起こるかを見てみましょう。答えは、 tの約数であるkについてのみ変化します。 最大5•10 ⁵までの数の除数の最大数は200であるため、それらの数に比例して時間の経過とともに単純に除数し、それらの解のみを更新できます。

同様に、時間がtからt -1に変わると、 t -1の約数である数値の答えが変わります。

問題E.関連するメトロ

条件：

制限時間3秒
256 MBのメモリ制限

Vasyaは、多くの場合、さまざまな都市で開催される国際的なプログラミングコンテストに参加します。 ベイトランドに到着し、地下鉄の地図を見ると、彼はどこかで信じられないほど似たものを見ていることに気付きました。 彼は慎重に考えた後、Baytlandの地下鉄がBaytoviaの地下鉄に非常に似ていることに気付きました。 どちらの都市でも、当然のことながら、地下鉄のトンネルが木を形成しています。2つの駅の間をトンネルに沿って両方向に移動できます。

両方の都市のメトロマップが本当に似ていることをPetyaの友人に証明するために、Vasyaは彼に、Baytlandのk駅a _iのコヒーレントセットとBytoviaのk駅b _iの対応するセットを見せたいです。 Baytlandのa _jは、Baytoviaのステーションb _iとb _jの間にトンネルがある場合にのみトンネルがあります。 一連のステーションは、このセットの任意のステーションから他の任意のステーションに到達でき、このセットのステーションのみを移動できる場合、接続済みと呼ばれます。

Vasyaがステーションの数で接続されたステーションの最大のペアを見つけるのに役立ちます。

入力フォーマット：

最初の行には、単一の整数n （1≤n≤50）-ベイトランドの地下鉄駅の数が含まれています。

次のn -1行は、番号u _i 、 v _i （1≤u _i 、 v i≤n）のペア-トンネルがあるBaytlandの駅の数を示します。 ステーションのペア間には、正確に1つの単純なパスがあることが保証されています。

次の行には、単一の整数m （1≤m≤50）-ビトビアの地下鉄駅の数が含まれています。

次のm -1行は、番号u _i 、 v _i （1≤u _i 、 v i≤m）のペアを与えます-ビトビアの駅の数で、その間にトンネルがあります。 ステーションのペア間には、正確に1つの単純なパスがあることが保証されています。

出力形式：

単一の整数k-似たようなステーションのペアの最大サイズを出力します。

例：

入力データ
3
1 2
2 3
3
1 3
3 2

インプリント
3

入力データ
5
4 1
2 4
4 3
3 5
5
1 2
2 3
3 4
4 5

インプリント
4

解決策：

このタスクでは、これらのツリーの互いに同形の連結ツリーサブツリーの最大のペアを見つける必要がありました。 この問題を動的計画法で解決します。

最初のツリーの一対の有向エッジ（ u ₁ 、 v ₁ ）および₂番目のツリーの（ u ₂ 、 v ₂ ）について、同型の最大のペアのサイズに等しい値dp [ u ₁ ] [ v ₁ ] [ u ₂ ] [ v ₂ ]を計算します頂点u ₁が頂点u ₂に移動し、頂点v ₁およびv ₂が選択されたサブツリーに必ずしも含まれない場合、サブツリー。 さらに、v _iをダミーの頂点-1と等しくします。これは、リモートサブツリーv _iがないことを意味し、共通サブツリーのすべての頂点を使用できます。 そのような量を計算する場合、答えは_、量dp [ u ₁ ] [-1] [ u ₂ ] [-1]の頂点u ₁ 、 u _2のすべてのペアの最大値になります。

dp [ u ₁ ] [ v ₁ ] [ u ₂ ] [ v ₂ ]を計算するには、何らかの方法でサブツリーu ₁とu _2を互いに一致させる必要があります。 e ₁がv ₁以外の頂点u ₁の息子である場合、 v ₁でツリーをぶら下げたとき、サブツリーe _1には、サブツリーu ₁よりも少ない頂点が含まれることに注意してください。 頂点u ₁の息子e ₁および頂点u _2の e _{2について、}帰納法の仮定により、すでにdp [ e ₁ ] [ u ₁ ] [ e ₂ ] [ u ₂ ]を計算しているので、目的のサブツリーにいくつの頂点を追加できるかがわかります。その頂点e ₁がe _2に対応する場合。 頂点u _1に k個の息子があり、 u _2に m個の息子がある場合、サイズk•mの行列a _i、jを取得します。ここで 、各列および各行に最大合計を持つ複数のセルを選択する必要があります選択されるセルは1つだけです。 これは、ハンガリーのアルゴリズムによって解決される標準の割り当て問題です。

ソリューションの総複雑さはO（n ⁵ ）であり、2つのツリーのエッジのペアを選択するn ^2の方法であり、 O（n ³ ）はハンガリー語アルゴリズムの時間です。 最適化のために、同じ（同形の）ペアに複数回ツリーを割り当てる問題を解決することはできませんが、答えを覚えておいてください。

* * *

チャンピオンシップへの参加申請を提出していない場合でも、まだ時間はあります！ 5月29日までロシアコードカップの Webサイトに登録して、2回目の予選ラウンドに参加してください。

ロシアコードカップチャンピオンシップは、ロシアのIT産業の発展を目的としたMail.Ruグループの取り組みの1つであり、IT.Mail.Ruリソースによって統合されています。 IT.Mail.Ruプラットフォームは 、ITに興味があり、この分野で専門的に開発しようと努力している人々のために作成されました。 このプロジェクトは、テクノパークMSTUでの教育プロジェクトであるロシアAiカップ、ロシアコードカップ、ロシアデベロッパーズカップの選手権を組み合わせたものです。 バウマン、モスクワ州立大学テクノスフィア M.V. MIPTのロモノソフとテクノトレック。 さらに、IT.Mail.Ruでは、テストを使用して、人気のあるプログラミング言語の知識をテストしたり、ITの世界から重要なニュースを学習したり、ITトピックに関する関連イベントや講義の放送を見たり見たりできます。