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

先週の日曜日、ロシアコードカップの予選ラウンドが行われました。 これは、競争の最後のオンラインラウンドです。ファイナリストの決定的な会議がモスクワで開催されます。 決勝に参加するには、前の段階よりも多くの努力をする必要がありました。 参加者には6つのタスク（資格ラウンドでは1つ少ない）が提供され、3時間はソリューションに割り当てられました（資格ラウンドでは2つ）。



ファイナルに到達するための戦いは簡単ではありませんでしたが、公平でした。ラウンド中にコピーライターは1人も特定されませんでした。

カットの下で-勝者に関する統計と予選ラウンドのタスクの詳細な分析：

• タスクA：2つの塔
• タスクB：デポジット
• タスクC：ケプラー
• タスクD：テスト
• タスクE：レーザー
• タスクF：ホイール

ラウンド中、439人がログインし、そのうち少なくとも1つの決定が371人の参加者によって送信されました。 合計3334のソリューションが送信されました。



対応するタスクに最初にソリューションを送信した参加者、およびラウンド開始後の時間（分：秒）：

• タスクA： RAVEman（9:12）
• 問題B： ant.ermilov（16:58）
• タスクC： Zhukov_Dmitry（5:52）
• タスクD： e-maxx（33:05）
• タスクE：ウインガー（37:50）
• タスクF：観光客（82:51）

このラウンドの参加者の領土分布は次のとおりでした。



ロシア=> 183

ウクライナ=> 53

ベラルーシ=> 23

米国=> 18

カザフスタン=> 5

ドイツ=> 4

スイス=> 3

ラトビア=> 2

アルメニア=> 2

ブルガリア=> 1

アイスランド=> 1

ハンガリー=> 1

ウズベキスタン=> 1

ジョージア=> 1

スペイン=> 1

リトアニア=> 1

英国=> 1

オーストリア=> 1

キプロス=> 1

ポーランド=> 1



3時間目の終わりにのみ、勝者のリストの写真が形になり始めました。 50人が決勝に達しました。 それらの最初の10：

1. ヴラディスラフ・イセンバエフ
2. ジェナディ・コロトケビッチ
3. ドミトリー・ジュルガコフ
4. ピーター・ミトリチェフ
5. ヴラディスラフ・エピファノフ
6. アルチョム・ラホフ
7. マイケル・ケバー
8. ドミトリー・ゴズマン
9. ドミトリー・ジューコフ
10. エフゲニー・カプン

最後に、タスクの分析に直接行きましょう。



タスクA. 2つの塔

アイデア：ヒョードルツァレフ

実現：パベル・クロトコフ、アンドレイ・スタンケビッチ

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



タスク条件



制限時間：2秒

メモリ制限：256メガバイト



Mail.Worldは最近、それぞれ10 ⁹フロアの2つの超高層ビルのように見える新しいオフィスに移転しました。 一部のフロアでは、タワーがトランジションによって接続されており、トランジションを介してタワー間を移動できます。 合計n個のトランジションがあり、それらはフロアa ₁ 、a ₂ 、...、a _nのタワーを接続します



Artyomは、L ₁階のタワーb ₁で働いています。 今日、彼は同僚のドミトリーと話をする必要があります。彼はL ₂階のb ₂タワーで働いています。 奇妙なことに、ArtemのワークステーションからDmitryのワークステーションに到達する最速の方法を選択することはそれほど簡単ではないことがわかりました。



各タワーにはエレベーターが1つあります。 タワー1のエレベーターは時間u ₁秒で1階を通過し、タワー2のエレベーターはu ₂秒で通過します。 Artyomは、タワー間の経路にt秒を費やします。



この情報に基づいて、Artemが職場からDmitryの職場までの最短時間を見つけられるようにします。 1つのタワーのフロア内の移動時間とエレベータの待機時間は無視する必要があります。



最初の例では、Artyomは最初のタワーのエレベーターに乗るだけです。



2番目の例では、2番目のタワーのエレベーターがはるかに速く動作し、Artemが2番目のタワーへの移行を行い、エレベーターを10階に持って行き、最初のタワーに戻り、1番目のタワーのエレベーターで別の階に移動する方が有利です。



入力形式



最初の行には、正の整数t-入力内のテストケースの数が含まれています。 以下はテストケースの説明です。



最初の行には、n-タワー間の遷移の数（1≤n≤10 ⁵ ）が含まれます。 2行目には、n個の異なる整数a ₁ 、a ₂ 、...、a _n （1≤a ₁ <a ₂ <... <a n≤10 ⁹ ）が含まれます。 次の行には、3つの正の整数u ₁ 、u ₂およびtが含まれています（それぞれ1〜10 ^9の範囲にあります）。 最後に、次の2行にはそれぞれb ₁ 、L ₁およびb ₂ 、L _2の2つの数値が含まれています（b ₁およびb ₂はそれぞれ1または2、1≤L ₁ 、L 2≤10 ⁹ ）。

入力データのすべてのテストケースの遷移の総数は10 ^6を超えません。



出力形式



各テストケースについて、1つの数字を印刷します。これは、Artemが職場からDmitryの職場に到達できる秒単位の最小時間です。



例

入力データ	インプリント
2 1 5 3 3 2 1 1 1 10 2 1 10 5 3 2 1 1 1 11	27 36

タスク解析



この問題は、グラフの最短パスを見つける問題の単純な特殊なケースです。 これを解決する1つの方法は、条件に記述されたグラフにダイクストラのアルゴリズムを実装することです。 ただし、頂点の数が多いため、このアルゴリズムのすべての実装がプログラムの制限時間に収まるわけではありません。 したがって、より高速なソリューションを検討してください。



興味のあるフロアからグラフを作成します。 次のフロアが興味深いと考えます。

• アルテムが動作するタワー内のアルテムが動作するフロア
• ドミトリーが働くタワー内のドミトリーが働く階
• Artyomに最も近いトランジションの終端であるフロア（合計で、トランジションから2つの頂点が得られ、それがより高く、トランジションから2つの頂点が得られます）
• 前の段落と同様の4つの頂点を追加しますが、Dmitryのみです。

グラフには2種類のエッジがあります。

• 遷移があるピークを結ぶリブ。 そのようなエッジの重みはt
• 1つの塔の山頂を結ぶリブ。 このようなリブの重量は、対応する階間の距離に、対応するタワーのエレベーターの速度を掛けた値に等しくなります

グラフには10個の頂点があることに注意してください。 このグラフの最短経路はどの方法でも検索できますが、フロイドアルゴリズムを実装するのが最も簡単でした。



タスクB.デポジット

アイデア： Boris Minaev

実現： Vitaliy Demyanjuk

分析： Vitaliy Demyanjuk



タスク条件



制限時間：2秒

メモリ制限：256メガバイト



長年の実務経験で、ヴァシリーイバノビッチはkルーブルを獲得しました。 現在、Vasily Ivanovichは退職し、このお金を今後m年間預け入れたいと考えています。 彼の故郷にはnの銀行があります。 Vasily Ivanovichがj年目に銀行口座番号iにお金を持っている場合、年末にこの口座の金額はp _i、jパーセント増加します。



毎年の初めに、Vasily Ivanovichは、必要に応じて、銀行口座にあるお金を再分配できます。 お金を再配布するプロセスは、4つの段階で行われます。 まず、彼は再配分に関与する多くの銀行を選択します。 その後、ヴァシリー・イワノビッチは、これらの銀行にあるすべてのお金を引き出します。 その後、選択した各銀行に手数料を支払います。 最終的に、彼は選択した銀行のそれぞれに必要なだけのお金を預け入れ、合計でVasily Ivanovichは彼が口座に引き出したすべてのお金を、支払った手数料を差し引いて預けます。 さらに、選択された銀行のセットには、Vasily Ivanovichにお金がなかった銀行、またはVasily Ivanovichにお金を入れない銀行も含まれます。 番号iの銀行には_iルーブルの手数料があります。 ヴァシリー・イワノビッチが手数料を支払うのに十分なお金を持っていない場合、彼はお金の再分配に参加した銀行に引き出されたすべてのお金を与えます。



初年度の初めに、ヴァシリー・イワノビッチは、任意の銀行の預金に任意の数のルーブルを無料で入れることができ、彼はすべてのお金を合計で預金に入れます。



m年の終わりに、Vasily Ivanovichのすべてのアカウントのルーブルの最大総数を見つけます。



この例では、Vasily Ivanovichは最初に2番目の銀行にお金を支払います。 最初の1年後、彼は115ルーブルを持ち、再分配のために両方の銀行を選択します。 2ルーブルの手数料を支払った後、彼はすべてのお金を最初の銀行に入れます。 年の終わりに、彼は彼の銀行口座に113×1.15 = 129.95ルーブルを持っていました。



入力形式



最初の行には、正の整数t-テストの数が含まれています。 （1≤t≤50）



各テストの説明は、3つの整数n、m、kを含む行で始まります-銀行の数、年、ルーブルをそれぞれ獲得しました。 （1≤n≤10000、1≤m≤20、1≤k≤10 ⁹ ）次の行にはn個の整数が含まれ、i番目の数値はa _i -i番目の銀行の手数料（1≤a i≤10 ⁹ ） 次のn行のそれぞれには、m個の整数が含まれています。 i番目の行のj番目の数字はp _iです。jは、i番目の銀行の口座に対してj年目にVasily Ivanovichが受け取った追加のお金の割合です（0≤p _i、 j≤100）。



すべてのテストの銀行の総数は50,000を超えません。



出力形式



各テストケースについて、m年の終わりにVasily Ivanovichのすべてのアカウントの最大合計金額を個別の行に印刷します。 相対誤差が10 ^-6を超えない場合、回答はカウントされます。



例

入力データ	インプリント
1 2 2 100 1 1 10 15 15 10	129.95

タスク解析



Vasily Ivanovichは、すべてのお金を1つの銀行に保管することで常に利益をもたらすことを示しています。 最適な答えを検討してください。 Vasily Ivanovichのお金が複数の銀行に横たわる年があると仮定します。 そのような年の中で、最も少ない年を選択します。 各銀行について、当年度中にこの銀行に横たわっているお金から受け取ったm年後の割合を検討します。ただし、すべてのコミッションは除きます。 最大割合の銀行を選択してください。 すべてのお金を入れても、答えは悪化しません。毎年、資金の再配分に参加した多くの銀行が、最適な答えの多くの銀行のサブセットになるためです。



証明されたばかりの事実を考慮に入れて、問題は動的計画法によって解決されます。 dp _i、jをi年後のVasily Ivanovichの口座のルーブルの最大数と等しくします（i年の間に彼のお金がすべてj番目の銀行にあった場合）。 前年にお金を保管できるすべての銀行を並べ替えてから、dp _i、j =（max（dp _{i-1、k-a k} ） _{-a j} ）•p _j、iの 1からnまでのすべてのk。



j = k、dp _i、j = max（dp _i、j 、dp _i、j-1 •p _j、i ）の場合を個別に検討します。 答えは、すべてのkに対する最大dp _m、kに等しくなります。 その結果、一見したところ、ソリューションはO（n2m）に対して機能します。 ただし、dp _i-1、k -a _kはjに依存しないことに注意してください。 したがって、すべてのiについてmax（dp _i-1、k -a _k ）をサポートする場合、O（nm）の解を取得します。



問題C.ケプラー

アイデア： Vitaly Aksyonov

実装：アンドレイ・コマロフ

分析：アンドレイ・コマロフ



タスク条件



制限時間：2秒

メモリ制限：256メガバイト



2番目のジャイロスコープが故障すると、ケプラー天体望遠鏡はその後の運用に適さなくなりました。 NASAはこの損失を回復し、別の望遠鏡を宇宙に打ち上げることにしました。 望遠鏡に電気を供給するために、ソーラーパネルを使用することが決定されました。 ソーラーパネルのブランクは、サイズがn×mの長方形のパネルで、1×1セルで構成されています。



残念ながら、展開時にバッテリーを軌道に投入することはできません。 輸送を容易にするために、パネルは薄い素材で作られており、セルの境界に沿って曲げることができます。 科学者は、バッテリーが1×1のサイズに折り畳まれた空間に飛ぶことを決定しました。



これを行うために、次のようにバッテリー用のブランクが付属しています。現在のブランクの片側の長さが均等であれば、ブランクを半分に折り畳むことができます。 パネルはサイズの半分です（パネルの厚さは無視できます）。 側面の1つが奇数の長さ（パネルのサイズが（2n + 1）×m）の場合、時間mの超精密レーザーで1×mのサイズの断片を切り取り、2nの長さに沿って半分に折ります。 パネルの切り取られた部分は捨てられます。 その結果、科学者は1×1のパネルを手に入れ、軌道に飛び、そこで軌道を拡大します。



レーザーは、すべての折りたたみが発生するよりもはるかに長く機能します。 この方法で元のワークを1×1の正方形に折り畳むために、彼らが達成できる最短のレーザー時間を決定するのを助けます。



パネルの配置によって生じるバッテリーのサイズは重要ではないことに注意してください。レーザーの動作時間を最小限に抑える必要があります。



入力形式



最初の行には、テストクエリの数である整数t（1≤t≤1000）が含まれています。 次のt行にはクエリ自体が含まれています。 各リクエストは、2つの整数nおよびm（1≤n、m≤10 ⁹ ）で構成されます-太陽電池のブランクの初期サイズ。



出力形式



リクエストごとに1つの数字を印刷します-科学者が達成できる最短のレーザー時間。



例

入力データ	インプリント
3 1 1 4 4 3 2	0 0 1

タスク解析



可能なすべての折りたたみのためにパネルがどのサイズになるかを研究します。 いずれかの側面を修正し、その長さが時間とともにどのように変化するかを確認します。 最初の次元に対応する辺の例を考えてみましょう。 最初はパネルのサイズをn×mとします。 対象の辺の長さはnです。 さらに2つのケースが考えられます。

• 長さnの辺に沿って追加します。 この場合、新しい長さは⌊n/2⌋です
• 長さmの辺に沿って折ります。 この場合、長さは変わらず、nのままです。

したがって、辺の長さはn、⌊n/2⌋、⌊⌊n/2⌋/2⌋、...、1のみです。N=⌊log2n⌋+ 1のみです。 2番目の側面についても同様の考慮を行うと、その長さはM =⌊log2m⌋+ 1の値を取ることができます。



この問題を解決するために、動的プログラミングのアイデアを使用します。 a _i 、i∈[1..N]で、最初の辺の長さを降順に並べて示します。 b _iについても同様です。



次の値を計算します。dp [i、j] =「n×mパネルから_i ×b _jパネルを取得できる最小時間」。 次に、aとbは降順に並べられているため、a _N = 1、b _M = 1であり、これは問題に対する答えがdp [N、M]であることを意味します。 dp [i、j]は、ルールに従って計算できます。

1. dp [i、j] =∞
2. dp [i、j] = min（dp [i、j]、dp [i-1、j] +（（ai-1 mod 2）•bj）i> 1の場合
3. dp [i、j] = min（dp [i、j]、dp [i、j-1] +（（bj-1 mod 2）•ai）j> 1の場合
4. dp [1、1] = 0

タスクD.テスト

アイデア： Artem Vasiliev

実装： Artem Vasiliev

分析：アルチョム・ヴァシリエフ



タスク条件



制限時間：2秒

メモリ制限：256メガバイト



Artyomは、電子システムのトレーニングテストに合格します。 テスト問題にはn個のステートメントが含まれていますが、そのうちのいくつかは真であり、チェックする必要があります。 チェックボックスのいくつかをチェックすることにより、答えが正しいかどうかを確認できます。 質問に対する答えは、すべての真のステートメントがチェックされ、すべての偽のステートメントがチェックされない場合、正しいと見なされます。



Artyomは考えるのが面倒なので、フラグを置くためのすべてのオプションを単純に整理することにしました。 これを行うために、彼はそれらの配置のすべての2 ⁿバリアントのリストをコンパイルします。 リストには、フラグを配置するための各オプションが1回だけ存在する必要があります。



直感的に、彼には多くの本当の声明があるように思われるので、彼はチェックされたフラグの数を減らすために配置オプションを整理したいと考えています。 さらに、Artemは非常に怠zyであり、2つの連続したオプションについて、それらが異なる位置の数が2を超えないようにしたいと考えています。 アルテムを助けます。



入力形式



最初の行には整数n（1≤n≤16）が含まれています。



出力形式



2 ⁿ行を印刷します。 i行目に、n文字0または1-i番目の回答オプションの各フラグの状態、チェックボックスの場合は1、未定義の場合は0を出力します。 オプションのユニット数は増えないはずです。 2つの隣接する線が区別される位置の数は、2を超えてはなりません。



例

入力データ	インプリント
2	11 10 01 00

タスク解析



この問題では、2つのプロパティが満たされるように、長さnの0および1のすべての行をリストする必要がありました。1つはユニット数が減らないこと、もう1つは2つの隣接する行の差が2つ以下であることです。



プロパティを満足する長さnのすべてのビット文字列のリストを返すsolve（n、k）プロシージャを記述します。 各行には正確にk個のユニットがあります。 solve（n、k）の再帰アルゴリズムについて説明します：

1. kが0またはnの場合、単一行0 ⁿまたは1 ⁿからリストを返します
2. それ以外の場合は、再帰的に解決（n-1、k）を呼び出し、解決（n-1、k-1）
3. 最初のリストのすべてのビット文字列に、末尾0に割り当て、2番目のリストのすべての要素に末尾1を割り当てます
4. 最初のリストと展開された2番目のリストの連結を返します

今の解決策は、リストからすべてのビット文字列を推定することです（n、k）nから0までのすべてのk このソリューションの正しさを証明しましょう。 解決プロシージャが返すリストのプロパティを検討します。

1. リストsolve（n、k）の最初の要素は1 ^k 0 ^n-kです
2. k> 0の場合、リストの最後の要素（n、k）は1 ^k-1 0 ^n-k 1です。
3. k = 0の場合、リストの最後の要素（n、k）は0 ^nです

これらすべての特性を誘導により証明するのは簡単です。 その結果、solve（n、k）プロシージャが実際に正しく機能することがわかります。 ソルバの最後の要素（n、k + 1）とソルバの最初の要素（n、k）が2つ以下の位置で異なることを検証するために残っています。 solve（n、k + 1）の最後の要素：1 ^k 0 ^n-k-1 1、solve（n、k）の最初の要素：1 ^k 0 ^n-k 。 プロパティがこれらの2行にも適用されることは簡単にわかります。 したがって、長さnのすべてのビット文字列を列挙し、必要な特性を満たすアルゴリズムを取得しました。



タスクE.レーザー

アイデア：アンナマロバ

実装： Artem Vasiliev

分析：アルチョム・ヴァシリエフ



タスク条件



制限時間：2秒

メモリ制限：256メガバイト



レーザー研究所の科学者は、新しい種類のレーザーをテストしています。 これを行うには、n個の接続点がある特別な実験台を使用します。



レーザーはこれらのポイントの1つに固定され、特別なプログラマブル屈折デバイスは残りのn-1ポイントに固定されます。 各デバイスは次のように構成できます。いくつかの方向を選択し、屈折器をプログラムして、選択した方向から所定の角度で入射したビームを回転させることができます。 この角度は、1つの屈折器であっても、方向によって異なる場合があります。 さらに、各屈折器およびその上で選択された各方向について、角度での角度は、絶対値でこの屈折器に印加される電圧の絶対値を超えることはできません。 実験室のセットアップの設計により、同じ電圧がすべての屈折器に印加されます。



レーザーをテストするために、科学者は特定の方向を選択し、ビームを放出して、ゼロ以外の距離を移動して開始点に戻ることを望んでいます。 これを行うには、屈折器を構成する必要があります。 これを行う前に、屈折器に印加する電圧の大きさを選択する必要があります。 その後、各方向の屈折器と、各方向の回転を実行する角度を選択できます。



科学者は、計画された実験を実現できる最小電圧を知りたいと考えています。



入力形式



最初の行には整数n（2≤n≤150）-実験台上の取り付け点の数が含まれています。 次のn行には、2つの整数xi、yi-i番目の点の座標が含まれます。 （-1からnまでのすべてのiについて、-20000≤x _i 、y i≤20000、すべての点が異なります）。 最初の点はレーザーに対応し、残りはすべて屈折器に対応します。



出力形式



1つの実数-屈折器に印加する必要がある最小電圧を印刷します。 答えの絶対誤差または相対誤差は10 ^-8を超えてはなりません。



例

入力データ	インプリント
4 0 0 0 1 1 1 1 0	90.0

タスク解析



ソリューションの主なアイデアは、答えのバイナリ検索です。 最大たわみ角αを固定し、そのような答えで解の存在を確認します。 これを行うために、グラフ内のパスを見つける問題を減らします。



条件でP ₁ 、P ₂ 、...、P _nとして定義されているポイントを示します。 n（n-1）頂点のグラフを作成します。各頂点は、異なる点の順序付けられたペアです。 ベクトルP _i P _jとP _j P _kの間の角度がαを超えない場合、ペア（i、j）からペア（j、k）にエッジを描画します。 作成されたグラフには、n ^{3個以下の}エッジがあります。 ここで、そのようなグラフにフォーム（1、i）の頂点からフォーム（j、1）の頂点へのパスが存在する場合、そのようなαを使用して実験を実行できます。 グラフ内のパスを見つけるためのアルゴリズムを使用して、パスの存在を確認できます。



したがって、バイナリ検索の1つの反復はO（n ³ ）に対して機能します。つまり、アルゴリズム全体をO（n ³ log（1 /ε））で実装できることを意味します。 n ³角度以下）、このアルゴリズムはO（n ³ log（n ³ ））で実装できます。



問題F.ホイール

アイデア： Boris Minaev

実装： Boris Minaev

分析：ボリス・ミナエフ。



タスク条件



制限時間：2秒

メモリ制限：256メガバイト



この問題で問題となっている国には、かなり興味深い道路システムがあります。 この国の合計で、n + 1都市が首都であり、n都市が通常の都市です。 すべての普通の都市は、首都を中心とする円上にあります。 隣接するすべての普通の都市間の距離は同じです。 各都市は、首都だけでなく、2つの隣人と道路で接続されています。 この国を上から見ると、頂点が中心に接続されている通常のnゴンが表示されます。



この国には、同国で権力を掌握したい野党が2つあります。 そして誰もそれを平和的にやりたいとは思いません！ 念のため、各都市には戦車小隊があります。 まさに翌日の初めに、次のことが起こります。 各都市（首都を含む）では、野党のいずれかが同様に権力を掌握する可能性が高い。 このパーティは、この都市に配置された戦車小隊を自由に使用できます。 さらに、各政党は、可能な限り大きな規模の軍隊を1か所に集める予定です。 戦車小隊は、道路に接続している両方の都市が同じパーティに占領されている場合にのみ、道路を通過できます。



あなたはまた、権力を掌握したい地下運動の主催者です。 同じ都市にいることができる最大数の戦車小隊の数学的期待を知る必要があります。 組織を失望させないでください！



たとえば、3つの普通の都市があるとします。 次に、4つの都市すべて（3つの普通都市と首都）がペアで道路で接続されています。 その後、1/8の確率で、すべての都市が同じパーティにキャプチャされます。 この場合、軍隊の最大サイズは4です。3/ 8の確率で、2つの都市が一方の当事者に、2つの都市が他方に占領されます。 この場合、軍隊の最大サイズは2です。最後に、1/2の確率で、1つの政党が1つの都市で権力を掌握し、他の3つの都市で権力を掌握します。 この場合、最大軍隊サイズは3になります。この場合の答えの数学的期待値は、4×1/8 + 2×3/8 + 3×1/2 = 2.75です。



入力形式



最初の行には、正の整数t-テストケースの数が含まれています。 次のt行には、1つの整数n（3≤n≤500）-国の通常の都市の数が含まれています。 すべてのテストケースの通常の都市の総数が1000を超えないことが保証されています。



出力形式



各テストケースについて、1つの数字を印刷します。これは、同じ都市に存在できる小隊の最大数の数学的期待値です。 答えが正しいものと異なるのは10 ^-9以下である場合、答えは正しいと見なされます。



例

入力データ	インプリント
2 3 4	2.75 3.4375

タスク解析



問題の状態を形式化します。 一般性を失うことなく、資本は第一野党によって押収されたと仮定します。 他のすべての都市は1つの数字に匹敵します。 首都と都市が1つの政党によって押収された場合は0、それ以外の場合は1になります。 キャプチャされた都市に関するすべての情報は、長さnのビットマスクとして表すことができます。 可能性のあるすべてのビットマスクが同様に発生する可能性があります。 特定のビットマスクの場合、答えは明らかです-最大値（ゼロの数+ 1）および（マスク内の連続するユニットの最大数）。 マスクはループされることに注意してください。最後の次のビットが最初です。



多項式解を得るために、動的計画法を使用します。 パラメータは次のとおりです。

1. マスクの桁数
2. マスクのゼロの数
3. 行の最大ユニット数
4. 行の現在のユニット数

ただし、マスクループを考慮するためには、マスクの最初にあるユニットの数を保存する必要もあります。 このソリューションはO（n ⁵ ）で機能します。



最後のパラメーターを取り除くために、次の考慮事項を使用します。 1つのユニットで構成されるマスクは、個別に処理されます。 残りのすべてのマスクを検討します。 それぞれに少なくとも1つのゼロがあります。 ループ内のマスクビットをシフトして、最初のゼロが最初にくるようにします。 最初のビットをカットします。 現在、いくつかのマスクが数回繰り返されています。 マスクが（それが終了する単位の数+ 1）回繰り返されることに気付くのは簡単です。 これは、長さn-1のすべてのマスクを反復処理でき、マスクの左側にゼロを追加し、その出現確率に（終了する単位の数+ 1）を掛けることができることを意味します。 動的計画法で確率を掛ける必要のある数をすでに保存していることに注意してください。 1つのパラメーターを取り除くと、O（n ⁴ ）の解が得られます。



都市の数が増えたときに答えがどうなるかを考えてください。 非常に高い確率で、接続性の最大コンポーネントは資本を含むコンポーネントです。 したがって、漸近的回答は（n + 2）/ 2になる傾向があります。n= 150であっても、漸近的回答からの偏差が約10 ^-12であることを示すのは簡単です。 nが増加すると、漸近応答からの偏差が減少するだけであることも証明できます。



したがって、次のソリューションが得られます。 O（n ⁴ ）で動的プログラミングを使用すると、nの最初の150個の値に対する答えが見つかります。 nが大きい場合は、式（n + 2）/ 2を使用します。



オリンピアードのすべてのタスクの分析は、 ロシアコードカップの Webサイトでも入手できます。 次の段階は最終段階です。 必ずHabréでそれを伝えます。