YurtigoによるオリジナルのMighty Morphin Power Rangers
3月19日は、ロシアコードカップ2017スポーツプログラミングチャンピオンシップのウォームアップラウンドでしたが、このラウンドは最終結果には影響しませんが、チャンピオンシップシステムとその目的を理解することができます。 今日は、ラウンドの結果について話し、その目的を分析したいと思います。
A. 宇宙船
B. バスレンジャー
C. 魔法の武器
D. 騎士と嘘つき
E. ボックス
ラウンドの登録者数は2789人で、昨年の2倍です。 提案された5つのタスクすべてを解決できたのはそのうちの1人だけでした！ ミハイル・イパトフ、おめでとうございます。 さらに4人が4人に対処しました。 GNU C ++ 14は最も人気のある言語であり、565の問題解決策が送られました。 2位と3位は、Python 3.5（525ソリューション）およびGNU C ++ 11（409ソリューション）が占めています。
A.宇宙船
テストごとの制限時間-2秒
テストごとのメモリ制限-256メガバイト
スペースレンジャーは、敵に囲まれたエイリアンの宇宙船に乗っていました。 自分を解放するには、特定の順序ですべての敵を破壊する必要があります。
レンジャーの周囲にはn人の敵がいて、それらのi番目の敵は力f iを持っています。 外に出るには、レンジャーはすべての敵を破壊する必要があり、最後に破壊された敵の力が他のすべての敵の力の合計と等しくなるようにします。
レンジャーには残り時間がほとんどないため、これを行う方法を理解する時間はありません。 彼はあなたの助けが必要です。 敵を破壊するために必要な順序を回復します。
入力データ
入力の最初の行には、自然数n-敵の数（2≤n≤105）が含まれます。
2行目には、各敵の強さ（–109≤f i≤109）を指定するn個の整数f iが含まれています。
インプリント
数字f iを、それらに対応する敵を破壊する必要がある順に印刷します。 適切なオプションがいくつかある場合は、いずれかを印刷します。 少なくとも1つの適切な破棄順序が存在することが保証されます。
ボスの強さがxの場合、すべての敵の強さの合計は2xであることに注意してください。 したがって、ボスの力を見つけるには、すべての敵の合計戦力を計算し、それを2で割る必要があります。その後、そのような力を持つ敵を見つけ、最後の敵の値で配列fのこの値を変更する必要があります。
B.バスレンジャー
テストごとの制限時間-2秒
テストごとのメモリ制限-256メガバイト
スペースレンジャーはバスで秘密の会議に行きます。
主な悪役はバスを注視しており、彼の意見では、レンジャーの一人が乗っています。 キャビンにはn列の座席があり、各座席には通路の左右に2つの座席があります。 行には、バスの先頭から1からnまでの番号が付けられています。 最後の停留所では、 k人がバスに交代し、悪役は誰がどの場所に、どの順番で着いたかを知っています。 当初、すべての座席は無料でした。
悪役は、バスに入ったときに各レンジャーが自分の場所をどのように選択するかを知っています。
- 赤いレンジャーは前に座るのが大好きです。 したがって、利用可能な座席の中で、彼は常に最も低い番号の列を選択します。 この列の2つの場所が空いている場合、彼は通路の左側に座っています。
- 青いレンジャーも前に座るのが好きです。 ただし、赤とは異なり、番号が最も小さい行の2つの場所が空いている場合は、青が右側に配置されます。
- 黒レンジャーは後ろに座ることが大好きです。 空いている席の中で、彼は常に最大数の列の場所を選択し、空いている場所が2つある場合は、通路の左側に座っています。
- 黄色のレンジャーも後ろに座るのが好きです。 しかし、黒とは異なり、最大数の列で2つの場所が空いている場合、黄色が右側に座っています。
- ピンクのレンジャーは好みがなく、空いている席に座ることができます。
主な悪役は、 k人の乗客のうちどれが各レンジャーになり得るかを知りたいと思っています。 乗客が搭乗した有名な場所については、この情報を印刷してください。 すべてのレンジャーがこのバスに乗る必要はないことに注意してください。
入力データ
最初の行には、番号nおよびk-バスの行数と乗客数（1≤n≤109、1≤k≤min（2•105、2n））が含まれます。
次のk行は、乗客がバスに入った順に説明しています。
これらの行のi番目には、番号x iおよびy iが含まれます-i番目の乗客が座った場所（ 1≤x i≤n 、 1≤y i≤2 ） 、 x iは行の番号、 y i =これが通路の左側の場所である場合は1 、右側の場合はy i = 2です。
乗客が座っている座席はすべて異なります。
インプリント
最初の行に番号s 1-赤いレンジャーになる可能性のある乗客の数を印刷し、次にスペースの後にs 1番号-昇順でこれらの乗客の番号（乗客は、与えられた順に1からkまでの番号が付けられます入力ファイル）。
次の4行では、他のレンジャーに関する情報を同じ形式（青、黒、黄色、ピンク）で印刷します。
乗客を順番に処理し、乗客ごとに乗客を決定します。 ピンクのレンジャーはどこにでも座ることができるので、すべての乗客が彼になることができます。
場所ごとに、無料かどうかを覚えておく必要があります。 unordered_setを取得して、占有された場所を保存します。 次の乗客が赤いレンジャーかどうかを確認します。 これを行うには、赤が座る場所を見つけます。 1からnまでの系列をループします。 空きスペースがある行がある場合、空きがある場合は左の行を選択し、そうでない場合は右の行を選択します。これは赤が置かれる場所になります。 彼は明確に座席を選択しているため、この乗客が赤かどうかを判断できます。この座席に着いたことを確認する必要があります。 同じ方法で、青、黄、黒がどこにあるかを見つけます：違いは、行を並べ替える順序（1からnまたはその逆）と、行の場所を選択する順序（最初の左または右）です。 乗客を処理した後、私たちは彼の座席を使用済みとしてマークします。
このソリューションはO（nk）で機能し、 O（k）メモリを使用します。
ソリューションを改善するために、空き領域がある行が見つかると、各サイクルが停止することに注意してください。 これは、最初と最後の未使用行をすばやく見つける必要があることを意味します。 これらの値-firstおよびlastをサポートします。 最初は、 first = 1 、 last = nです。 ループの各反復の後、これらの値を更新します。 最初の行がビジーのときに最初に1ずつ増加し、 最後の行がビジーのときに最後に 1ずつ減少します。 k / 2を超える行を占有することはできないため、 最初と最後はO（k）ステップかかります。 したがって、改善されたソリューションはO（k）に対して機能し、すべてのテストに合格します。
C.魔法の武器
テストごとの制限時間-2秒
テストごとのメモリ制限-256メガバイト
魔法の武器を組み立てるには、緑、赤、青の3つのフラグメントを組み合わせる必要があります。
緑、赤、青のレンジャーは、魔法の武器を収集する方法はいくつあるのだろうと考えました。 各レンジャーの既知のフラグメントセット。 緑のレンジャーには緑の断片、赤のレンジャーには赤、青には青があります。
武器を組み立てるときは、次の3つの規則を順守する必要があります。
- 赤い断片のモデル番号の最初の桁は、緑色のモデルの最後の桁と等しくなければなりません。
- 赤いフラグメントモデル番号の最後の桁は、青いフラグメントモデルの最初の桁と等しくなければなりません。
- 使用される3つのフラグメントはすべて、異なるモデル番号を持っている必要があります。
レンジャーの少なくとも1人が、おそらく同じモデルの異なるフラグメントを組み立てるときに使用する場合、武器を組み立てる2つの方法は異なると見なされます。 各レンジャーのフラグメントのモデル番号を知っています。 単一のレンジャーは、同じモデルの複数のフラグメントを持つ場合があります。 レンジャーが武器を収集できるさまざまな方法を理解するのに役立ちます。
入力データ
入力の最初の行には、数字g 、 r 、およびbが含まれます。それぞれ、緑、赤、および青のレンジャーのフラグメントの数（1≤g、r、b≤105）です。
次の行には、 g番号x i-緑のレンジャーが持っているモデル番号（0≤x i≤109）が含まれています。
次の行には、 r番号y i-赤いレンジャーが持っているモデル番号（0≤y i≤109）が含まれています。
次の行には、 b番号z i-青いレンジャーが持つモデル番号（0≤z i≤109）が含まれます。
インプリント
1つの数字を印刷-武器を収集する方法の数。
配列が好ましい： R [a] [b] -赤いレンジャーのフラグメントの数。最初の数字はaで、最後の数字はbです。 G [a] -最後の桁がaに等しい緑のレンジャーのフラグメントの数。 B [b]は、最初の桁がbである青いレンジャーのフラグメントの数です。
異なるレンジャーが同じフラグメントモデルを持っていなかった場合、答えは値G [a]•R [a] [b]•B [b]のすべてのaおよびbの合計に等しくなります。
モデルのペアが一致する状況を考慮するために、赤と青、赤と緑、青と緑のレンジャーに対して同じモデル番号を持つフラグメントのペアの数をそれぞれ計算します（たとえば、std :: mapを使用）。 最初と最後の数字を持つ数字のみが一致することに注意してください。 包含-除外式を使用し、回答からそのようなペアの数を引き、3つのレンジャーすべてが同じモデルを持っている場合、フラグメントのトリプルの数の2倍を追加します。
D.騎士と嘘つき
テストごとの制限時間-2秒
テストごとのメモリ制限-256メガバイト
スペースレンジャーは2行のk人の兵士で軍隊を編成しました。 彼は、この構造の隣人を同じ列の左右の兵士、および同じ位置にいるが異なる列にいる兵士と見なします。 レンジャーは、軍隊には常に真実を語る騎士と嘘をつく嘘つきがいて、彼らが尋ねられた少なくとも一つの質問に答えていることを知っています。
レンジャーは多くの質問のうち1つまたは2つを選択しました。
- 「隣人の正確にx人が騎士だというのは本当ですか？」
- 「あなたの隣人の正確にあなたが嘘つきであるというのは本当ですか？」
そして、各兵士に尋ねた。 すべての兵士は、同じxおよび/またはy値で質問されました。
突然、すべての兵士が質問にすべて「はい」と答えました。 今、スペースレンジャーは、自分の軍隊に入れることができる騎士の最小数と最大数に興味を持っています。 彼がそれを理解するのを助けてください。 条件から2番目の例を分析してみましょう：5人の兵士の各ランクで、「あなたの隣人のちょうど1人が騎士だというのは本当ですか？」と「あなたの隣人のちょうど2人が嘘つきだというのは本当ですか？」
軍隊は完全に嘘つきで構成することができます（彼らは嘘をついて、最初の質問に答えましたが、ランクの極端な者は2番目の質問の真実に答えました）。 この場合、騎士の最小数-0に到達します。別のオプション：2位と4位の各ランクには騎士がいて、残りは嘘つきです。 この場合、すべての騎士は本来のとおりに真実を語り、各嘘つきは嘘をつき、2番目の質問に答えます（各嘘つきにはちょうど1人の隣人、嘘つきがいます）。 この場合、騎士の最大数-4に達します。
入力データ
唯一の入力行には、3つの整数k 、 x 、 yが含まれます。1行の兵士の数と質問からの数（1≤k≤105、–1≤x、y≤3）です。
x = –1の場合、これはレンジャーが最初の質問をしなかったことを意味します。
y = –1の場合、これはレンジャーが2番目の質問をしなかったことを意味します。
レンジャーが少なくとも1つの質問をしたことが保証されています。
インプリント
データk 、 x、およびyの構築方法がない場合は、-1を出力します。
それ以外の場合、最初の行には1つの数値（軍隊の騎士の最小数）と2番目の行（軍隊の騎士の最大数）を含める必要があります。
プロファイルに沿った動的プログラミングにより問題を解決します。 例えば、騎士の最大数を見つけましょう。 dp [i] [mask_prev] [mask_cur]を最初のi列の配置に含めることができる騎士の最大数、 mask_curを i番目の列のマスク、 mask_prevを （i-1）番目とします。
次に（i + 1）番目の列のマスクを調べ、 i番目の列の兵士の隣人の制限が満たされているかどうかを確認します。これは、すべての隣人がわかっているためです。 最初と最後の列の制約には、隣接するものがないため、個別にチェックする必要があります。
ベース： dp [2] [mask_prev] [mask_cur]は、 mask_prevがmask_curの左側にある場合、 mask_prevおよびmask_curのユニット数に等しくなります。
遷移： dp [i + 1] [mask_cur] [mask_next] = dp [i] [mask_prev] [mask_cur] + ones（mask_next）ここで、 ones（x）はマスクxのユニット数です。
答えは、すべてのdp [k] [mask_prev] [mask_cur]の中で最大になり、 mask_curはmask_prevの右側になります。 最後に、 k = 1の場合は個別に考慮する必要があります。この場合、前の列がないためです。
E.ボックス
テストごとの制限時間-2秒
テストごとのメモリ制限-256メガバイト
黒いレンジャーは長方形の箱を作りたいと思っています。 このために、彼はn個の長方形の金属シートのうち6 個を使用する予定で、 i番目のシートのサイズは a i x b iメートルです。
ボックスの各面は、金属の固体シートでなければなりません。 シートを曲げたり切断したりすることはできません。ボックスを折り畳むシートは、その端からはみ出してはなりません。 シートはランダムに回転できます。
黒いレンジャーは、最大体積の平行六面体を作りたいと思っています。 彼を助けてください。
入力データ
最初の行には、1つの数値n-ブラックレンジャーの金属シートの数（6≤n≤200 000）が含まれます。
次のn行は、数値ai 、 biのペア-i番目の金属シートの寸法（1≤a i 、b i≤106）を示します。
インプリント
単一の整数を印刷-これらの金属シートから組み立てることができる直方体の最大体積。
これらのシートから長方形の箱を組み立てることが不可能な場合は、-1を印刷します。
ソリューションの主なアイデアについて話しましょう。 まず、2つまたは3つの側面が一致するすべての平行六面体を個別に検討します。これはO（n）で実行できます。
次に、3つの側面をすべて異なるものにします。 次の無向グラフを作成します。頂点は辺の可能な長さであり、サイズa×bのシートが少なくとも2つある場合、数字aとbをエッジで接続します。 問題は、結果のグラフで三角形を考慮することで軽減されました。これは、 O（n2 / w）またはO（nsqrt（n））で実行できます （ここで、 wは機械語のサイズ32または64を表し、この要因はビット圧縮を使用して三角形を見つけるときに発生します）。
次は？
資格審査にご招待します！ 4月2日、16日、29日に開催されます。 各ラウンドの上位200人のプログラマーが資格を取得します。 彼らは特別な証明書を受け取り、記念すべき賞品-チャンピオンシップのロゴが付いたクールなTシャツを競います。 そして、予選ラウンドで優秀な50人のプログラマーが決勝戦に進み、75万ルーブルの賞金を競います。 今すぐ参加しよう ！