5月29日に、 ロシアコードカップ2016チャンピオンシップの予選2回目が開催されました。 今回、参加者は再び2時間以内に5つの問題を解決しなければなりませんでした。 2回目の予選ラウンドでは3891人が戦い、 200人が6月19日に開催される予選ラウンドに参加する権利を得ました。 そして今日、提案された問題の解決策に慣れることをお勧めします。
問題A.ペティアと教科書
状態
制限時間2秒
256 MBのメモリ制限
今日部屋を掃除しているときに、ペティアは彼の古いロシア語の教科書を見つけました。 彼は子供の頃からこの主題が好きではないので、彼はそれからページを引き裂き始めました。
教科書には、 iとn - i + 1ページが相互に接続されるように1からnまでの番号が付けられたnページが結合されています-それらの1つが破れた場合、2番目も教科書から脱落します。 Petyaは、教科書からページを引き裂くプロセスを本当に気に入っていますが、まだそれを制御したいと考えています。また、ある時点で、残りのページからページの順番にどの番号pがあるかを知りたいと思っています。 このタスクで彼を助けてください。
入力形式
入力には、いくつかのテストスイートが含まれます。 最初の行には、テスト数t （1≤t≤1000）が含まれています。
以下の各tテストは、次のように説明されています：テストの説明の最初の行には、2つの数値n 、 q （2≤n≤100、 nは偶数、 1≤q≤100）が含まれています-教科書のページ数とリクエストの数。 次のq行には、2種類のクエリが含まれています。
- -i-Petyaは番号iのページを引き出します。
- ？ p-Petyaは、残りのページから順番にpthを持つ番号を見つけたいと考えています。
削除されたページが最初のタイプのリクエストに存在し、2番目のタイプのリクエストの現在のページ数がp以上であることが保証されます。
出力形式
2番目のタイプのリクエストごとに、探しているページの番号を別々の行に印刷します。
例
入力データ
2
4 4
？ 3
-2
？ 2
？ 1
6 5
-3
？ 3
-1
？ 2
？ 1
インプリント
3
4
1
5
5
2
解決策
このタスクでは、彼らが尋ねたものを書くだけでした。 サイズがnの isDeleted配列を格納するだけで十分です。isDeleted[i]は、ページ番号iがすでに削除されているかどうかを意味します。 最初のリクエストを処理するには、 isDeleted [i]およびisDeleted [ n - i + 1]をfalseに設定し、2番目のリクエストを処理するには、 isDeleted配列でインデックスp- thを見つければ十分です。
解の漸近的挙動： O（t•q•n） 。
問題V.グレゴリーと銀行
状態
制限時間2秒
256 MBのメモリ制限
グレゴリーは、ある大企業の会計で働いています。 彼は買い手から銀行振込を受け取り、売り手にお金を転送します。
グレゴリーは、彼の会社がサービスを提供している銀行の唯一のアクセス可能な支店を通じてすべての送金を送受信します。 この部門の仕事はかなり奇妙です。 毎日、銀行は次の2つの方法のいずれかで機能します。顧客が送金を行うか、送金のみを受け入れることができます。 同時に、グレゴリーは複数の操作を実行できません。その日に許可されている操作の種類に応じて、1回の転送を受信するか、1回の転送を行います。 あなたの裁量で取引相手を選ぶことができます。 同時に、グレゴリーの長は彼に必然的に銀行に行き、毎日送金を送受させます。
グレゴリーは、買い手からお金を受け取るためのn個のリクエストと売り手にお金を送るためのm 個のリクエストを処理する必要があります。 グレゴリーは銀行の勤務スケジュールを知っており、お金がいつ送金されるかについて各買い手と売り手に同意することもできます。
当初、グレゴリーが管理する口座にはお金がありません。 それから彼は毎日銀行に来て、口座でお金を受け取るか、彼から送金します。 同時に、彼はいくつかの売り手を返済できないことが判明する可能性があることを理解しています。 グレゴリーは、合意された支払い日に、売り手のサービスの支払いに必要な金額よりも少ない金額がアカウントにある場合、支払いを行うことができません。 この場合、口座からの送金は行われず、グレゴリーは上司からre責を受けます。 気分を害した売り手は商品の配送を拒否し、グレゴリーの会社とは対話しなくなりました。
グレゴリーは、決済日について売り手と買い手との合意を望み、支払いできない売り手ができるだけ少なくなるようにします。 彼がそれをするのを助けてください！
入力形式
入力には、いくつかのテストスイートが含まれます。 最初の行には、テスト数t （1≤t≤1000）が含まれています。
各テストの説明は次のとおりです。テストの説明の最初の行には、番号nおよびm （1≤n、m≤100）-それぞれ買い手と売り手の数が含まれています。 2行目には、 n個の数値a i （1≤a i≤1000）が含まれています。これは、 i番目の買い手がリストする金額です。 3行目には、 m個の数値b j （1≤b j≤1000）が含まれています-j 番目のセラーに転送される金額。 テストの説明の最後の行には、文字列sが含まれます（長さsはn + mで 、 sにはn +文字とm文字-が含まれます）。 s [k]は+です。k日目に銀行が送金のみを受け入れ、銀行が送金の送信のみを行う場合、 s [k]は-です。
出力形式
テストごとに、個別の行に回答を印刷します。これは、グレゴリーが支払うことができない販売者の最小数です。
例
入力データ
3
2 1
1 5
4
+-+
1 3
1
2 2 2
-+-
2 2
2 2
3 3
+-+-
インプリント
0
3
1
解決策
この問題を解決するという考えは、欲張りに基づいています。 買い手と売り手のランダムな配置を検討してください。
バイヤーa iとa jのペアがあり、 i < jとa i < a jであるとします。 iとjは、選択されたランダム配置の位置です。 それらを交換しても、Grigoryのアカウントの金額はiからjの間隔で増加するため、答えが悪くなることはありません。 したがって、バイヤーがa iの降順で送金することは有利です。
同様に、支払い可能な販売者が2人いる場合は、 b jの昇順で販売する方が収益性が高いことを証明できます。
唯一の微妙な点は、支払いが不可能な売り手の存在です。 明らかに、Gregoryがx個の売り手で支払うことができない場合、彼らが最も高価であることはより有益です。
上記に基づいて、問題の解決策を取得します。 シーケンスa iとb jをソートし、その後プロセスをシミュレートし、グレゴリーの現在のバランスを維持します。
問題C.名前ジェネレーター
状態
制限時間2秒
256 MBのメモリ制限
史上最高の作家、ヘンク・モーバックスは、彼が次のベストセラーを書くことをすでに理解していますが、彼のキャラクターの名前はまだ決めていません。 以前の本に関しては、彼は特別に考案された文字列をk個の異なる空でない部分に分割することで名前を受け取ります。 特定の文字列をk個の異なる名前に分割できるかどうかをHenkが理解できるようにします。
入力形式
ファイルの最初の行には、テスト数t （1≤t≤1000）が含まれています。
各テストは2行で説明されています。 テストの説明の最初の行には、小文字の英字で構成される長さが100以下の文字列が含まれています。 2行目には、1つの正の数k （1≤k≤5）が含まれます。これは、指定された行を分割するのに必要な行数です。
出力形式
各テストの結果は、次の形式で表示する必要があります。
説明した方法でソース行を分割できる場合、出力ファイルにはk + 1行が含まれている必要があります。 最初の行にはYESが含まれている必要があります。 （ i + 1）番目の行にはi番目の名前が含まれている必要があります。 元の文字列は、出力順序で文字列を連結して取得する必要があります。
説明した方法でソース行を分割できない場合、出力ファイルにはNO行が含まれている必要があります。
例
入力データ
3
aaa
2
aaa
3
abc
3
インプリント
はい
a
ああ
いや
はい
a
b
c
解決策
まず、すべてのkについて、 k （ k + 1）/ 2以上の長さのすべての文字列をk個の個別の文字列に分割できることに注意してください。 これを行うには、長さ1、2、...、 k -1およびn - k （ k -1）/ 2の部分文字列を使用します。 k≤5なので、少なくとも15の長さのすべての行を分割することを学びました。また、長さが15未満の行については、分割するすべてのk -1の位置で繰り返しを開始し、結果の分割のすべての行が真であるかどうかを確認します違います。
タスクD. Tシャツ
状態
制限時間2秒
256 MBのメモリ制限
Ilya、Vanya、Vladはチームプログラミングコンテストに長い間関わってきました。 今年はnチームの大会があり、それぞれにTシャツが贈られました。 Tシャツのタイプには、授与された競技会に応じて1からnまでの番号が付けられていると想定しています。
すべての男の子には、お気に入りのTシャツがあります。 つまり、各男の子には1からnまでの数字の順列があります。最初のTシャツが最もお気に入りで、最後のTシャツが最も愛されていないTシャツの数です。
今、彼らは競争に参加しています。 彼らは、すべてのコンテストで同じTシャツを着たいと考えています。 しかし、Tシャツの好みは異なる可能性があるため、コンテストの前に1枚からn枚の数字を紙に書き、順番に1つの数字を消します。 その数が最後に残っているTシャツは、この時間を着ています。
みんなは常に最適な形で消し去ります。つまり、誰もが最後に彼が一番好きなTシャツがあることを確認しようとしています。 そのため、連中は最後に残るTシャツの数を見つけるプログラムを書くように依頼することにしました。
入力形式
入力には、いくつかのテストケースが含まれます。 最初の行には1つの数値t （1≤t≤50）-テストの数が含まれます。 以下はテストの説明です。
各テストは次のように定義されます。最初の行には、1つの正の整数n （1≤n≤13）-男が参加した競技の数が含まれます。
次の行には、1からnまでの順列（イリヤのTシャツの好み）が含まれています。
次の行には、1からnまでの順列（VaniのTシャツの設定）が含まれています。
次の行には、1からnまでの順列が含まれています-VladのTシャツの好み。
連中は次の順番で行く：イリヤ、ヴァンヤ、ヴラド。
出力形式
テストケースごとに、1つの数字を印刷します。これは、最後に残るTシャツの番号です。
例
入力データ
3
4
1 3 2 4
4 1 2 3
1 2 3 4
5
1 3 2 4 5
5 3 2 1 4
1 3 2 4 5
3
1 2 3
1 2 3
1 2 3
インプリント
1
3
1
解決策
この問題を解決するために、サブセットで動的プログラミングを使用します。 dp [i] [mask]で、 i番目の参加者が移動した場合に達成できる最適なTシャツ番号を示し、 マスク番号の設定ビットに一致するTシャツを利用できます。 簡単に説明すると、どのTシャツを消すかを選び 、値dp [（ i + 1）％3] [ mask 1]を使用して取得するTシャツを見つけます。ここで、 マスク 1は対応するビットをゼロにすることでマスクから取得されます。
タスクE.ブリッジテスト
状態
4秒の制限時間
256 MBのメモリ制限
島に位置する小さな州は、その輸送システムを開発しています。 いくつかの島は、任意の2つの島の間で橋に沿って一方向しか存在しないような方法で橋で接続されています。つまり、橋のシステムは木を形成します。 ブリッジの長さはさまざまです。
これらの橋を皆のために開く前に、それらの信頼性を確認する必要があります。 これを行うには、 q日以内に、2人の労働者が1つの島から別の島へのパスに沿って1の固定速度で移動します。 それらはそれぞれ、おそらく異なる時点から開始して、独自の方法で移動します。 ブリッジは、その日、両方の作業者が特定のゼロ以外の期間、同時にブリッジに沿って走行した場合、 i日目にテストされたと見なされます。 qテスト日ごとに、その日に少なくとも1つのブリッジがテストされたかどうかを判断します。
入力形式
最初の行には、2つの数値nとq （1≤n、 q≤10 5 、n≥2）が含まれています。それぞれ、島の数とテスト日です。 次のn -1行は、 u i v i l i （ 1≤u i 、 v i≤n、1≤l i≤10 9 ）の形式でブリッジを記述します-ブリッジの端とその長さ。 次のq行にはそれぞれ、2つの作業パスの説明が含まれています。 各パスは、3つの数値b i 、 e i 、 s i （1≤b i 、 e i≤n、1≤s i≤10 9 、 b i ≠ e i ）-パスの最初と最後の頂点、および時間どの労働者が動き始めます。
出力形式
クエリへの回答を含むq行を印刷します。 i番目の行に、少なくとも1つのブリッジがi番目の日にテストされた場合はYESを印刷し、そうでない場合はNOを印刷します。
例
入力データ
8 6
1 2 3
1 3 1
1 4 2
2 5 5
2 6 1
5 7 2
5 8 4
5 3 2 7 4 2
8 6 1 1 7 6
4 5 1 4 5 10
7 8 3 3 4 5
6 7 6 5 1 2
2 1 10 8 3 3
インプリント
はい
はい
いや
いや
いや
はい
解決策
すべてのリクエストをオンラインで互いに独立して解決します。 まず、2つのパスの交差点を見つけ、各パスのこの交差点のみを残します。
2つのパスの交差点を見つける方法は？ これを行うには、2番目のパスの各端を最初のパスに「投影」します。 パスs → tへの頂点uの射影は、パスs → tにある頂点で、ツリー内の距離でuに最も近い頂点です。 この頂点は、次の頂点のいずれかです。
- sまたはt ;
- LCA（ s 、 t ）;
- LCA（ s 、 u ）がパスs → tにある場合 ;
- LCA（ t 、 u ）がパスs → tにある場合 。
最初のパスへの2番目のパスの各頂点の投影間のパスは、目的の交差点になります; s ' → t'で示します。
この後、次の2つのケースを考慮する必要があります。
- パスは、この交差点に沿ってさまざまな方向に進みます。 この場合、両方のワーカーが同じポイントにいる時点を見つけることができます（半分積分できることを忘れないでください）。 この後、この時点が頂点ではなくエッジに対応することを確認するために残ります。
- パスは同じ方向に進みます。 この場合、ある時点で両方のワーカーが1つのエッジにいた場合、これはパスs ' → t' の最大長のエッジにも当てはまることがわかります。 s ' → t' の最大エッジ長がMの場合、 | t 1 - t 2 | < M 、ここでt 1およびt 2-移動開始の時間。
上記のソリューションでは、パス上の最大エッジと2つの頂点間の距離の検索であるLCA検索が使用されました。 これはすべて、たとえば、 O （（ n + q ）log n ）時間およびO （ n log n ）メモリでバイナリアップ手法を使用して実現できます。
***
ロシアコードカップチャンピオンシップは、ロシアのIT産業の発展を目的としたMail.Ruグループの取り組みの1つであり、 IT.Mail.Ruリソースによって統合されています。 IT.Mail.Ruプラットフォームは、ITに興味があり、この分野で専門的に開発しようと努力している人々のために作成されました。 このプロジェクトは、テクノパークMSTUでの教育プロジェクトであるロシアのAiカップ、ロシアのコードカップ、ロシアのデベロッパーカップのチャンピオンシップを組み合わせたものです。 バウマン、モスクワ州立大学テクノスフィア M.V. MIPTのロモノソフとテクノトレック。 さらに、IT.Mail.Ruでは、人気のあるプログラミング言語の知識をテストしたり、ITの世界から重要なニュースを学んだり、関連するイベントやITトピックに関する講義の放送を見たり見たりするためにテストを使用できます。