Yandex.Algorithm。 昨年の予選ラウンドとチャンピオンシップに参加する最後のチャンスの分析

ご存知のように、別のACM ICPCチャンピオンシップは昨日終了しました。 モスクワ物理学技術研究所、ITMO、UrFU、ニジニノヴゴロド州立大学の優秀な成績を収めた学生、そしてサンクトペテルブルク州立大学の学生の皆さん、おめでとうございます。 今、私たちはすべての人をYandex.Algorithm 2016に参加するように招待します。今年のチャンピオンシップファイナルはミンスクで開催されます。







今年、伝統的な賞品に加えて、受賞者は初めてYandexでインターンシップを受ける機会があります。 5月22日に登録は終了し、予選ラウンドの他の参加者のみに従う必要があります。 予選ラウンドは今年5月21日から5月22日までの2日間続きます。 ラウンドは再びTCM / Timeシステムを使用して評価されます 。 タスクの難しさに興味がある人のために、昨年の資格のツアーを整理しました。 また、それを実践する機会もあります。



更新： Yandex.Algorithm 2016の予選ラウンドは既に開始されており、将来的に間違いなく分析する問題を解決するために来ています。 私たちの意見では、タスクは昨年ほど悪くありません。

A.タイプミス

Michaelは普通のインターネットユーザーです。 MichaelがYandexを使用してインターネット上で何かを検索すると、検索クエリでタイプミスが許可されることがあります。 もちろん、ほとんどの場合、YandexはMichaelが考えていたものを推測し、リクエストを修正できます。 たとえば、Michaelが「deoxyribonucleic」を封印して書いた場合（これは驚くことではありません）、Yandexは「deoxyribonucleic」のリクエストを修正します。



このタスクでは、ユーザーのリクエストのタイプミスを修正するプログラムを作成する必要があると考えたのでしょう。 これはそうではありません。このタスクに加えて、さらに5つのエキサイティングなタスクが提供され、競争の終わりまであまり時間がありません。 マイケルの次のリクエストにタイプミスが含まれているかどうかを確認してください。



入力データ

入力ファイルの最初の行には、Michaelのリクエストが含まれています。1〜5語で、小文字のラテン文字で構成され、単一のスペースで区切られています。 2行目には整数N（1≤N≤100）が含まれます：Yandex辞書に含まれる単語の数（心配しないでください、実際にはYandex辞書に含まれる単語の数は100以上です）。 3行目には、辞書の単語が含まれています。 各単語は、小文字のラテン文字で構成される文字列です。 単語は単一のスペースで区切られます。 クエリからの単語と辞書からの単語の両方が20文字を超えないことが保証されます。



インプリント

出力ファイルの唯一の行に、Michaelのクエリのすべての単語が既存の辞書に含まれている場合は「Correct」 （引用符なし）を、少なくとも1つの単語が辞書にない場合は「Misspell」 （引用符なし）を印刷します。



問題解決

タスクは、最初のセットのすべての単語が2番目のセットに属するかどうかを判断することでした。

この問題に制限がある場合、 O（N・M）で簡単な単純なソリューションで十分です。ここで、 NとMはそれぞれ最初と2番目のセットのサイズです。 それを実装するには、最初のセットの各単語が2番目のセットにあることを直接確認する必要があります。



かなり簡単な実装がPythonで取得されます。

import sys words = sys.stdin.readline().split() _ = sys.stdin.readline() d = sys.stdin.readline().split() print "Correct" if all(word in d for word in words) else "Misspell"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

B.最適なプレイリスト

アンナは通常のインターネットユーザーです。 アンナは音楽を聴いて、Yandex.Musicサービスを使用するのが大好きです。 ある日、Yandex.Musicの曲をランダムシャッフルモードで聴いているときに、アンナは、Grigory Lepsがお気に入りのグループEpidemicの後に突然演奏し始めたことに非常に腹を立てました。 アンナはinりに燃えて、サービスの技術サポートに怒った手紙を書き、その後、Yandex.Music開発チームは、再生する次の曲の選択を改善することを決定しました。



合計で、このサービスにはN曲あり、それぞれが少なくとも1回は聞きたいと思っています。 同時に、アンナは歌に再び耳を傾けることに反対しませんが、彼女は本当にジャンルの急激な変化に反対します。 音楽自体に加えて、Yandex.Musicデータベースには、一部の曲がどのようにジャンルが似ているかに関する情報が含まれています。 各エントリの形式は（a、b、U）であり、番号aの曲の直後に番号bの曲を含めると、ユーザーはU単位の不満を感じることになります。



アンナを含むすべてのユーザーが最も失敗した曲の切り替えに注意を払うことが知られているため、連続した曲の切り替えによるすべての苦情に対して、プレイリストを聴くことに対する最大の不満を最大と呼びます。



そのようなデータがあるため、Yandex.Musicは次の条件を満たすユーザーに最適なプレイリストを作成する必要があります。

• 各曲は少なくとも1回は含まれています。
• 隣接する曲の各ペアには、データベース内に対応するエントリがあります（これがどうなるかを知らずに曲を切り替えないほうが良いです）。
• プレイリストを聞くことに対する不満はできるだけ小さくする必要があります。

これらの条件を満たすプレイリストを作成できますか？



入力データ

入力ファイルの最初の行には、スペースで区切られた2つの整数NおよびM （1≤N≤100,000、1≤M≤200,000）が含まれています。それぞれ、アンナが聴きたい曲の数と、これらの曲の間の遷移に関するメモの数です。 次のM行には、スペースで区切られた3つの整数ai 、 bi 、 Ui （1≤ai、bi≤N、ai≠bi、1≤Ui≤1 000 000 000）が含まれています。番号aiの曲の直後のbiは、ユーザーがUi単位の不満を経験します。 録音中に1つの曲から別の曲への移行が2回発生しないことが保証されています。



インプリント

単一の数字を印刷します。最適に構成されたプレイリストを聴いているときにアンナが経験する最大の不満、またはプレイリストを構成できない場合は-1。



問題解決

追加のパラメーターUiなしで問題を解決することを学びます。

N個の頂点とM個のアークを持つ有向グラフを考えると、2つの隣接する頂点がアークで接続され、グラフのN個の異なる頂点すべてがこのシーケンスに含まれるように、一連の頂点を構築できるかどうかを判断する必要があります。

このグラフの強く接続されたコンポーネントは、1つの頂点に置き換えることができます。 これができるのは 強力に接続されたグラフの場合、グラフのすべての頂点が少なくとも1回出現する一連の頂点を作成できます。 この声明を証明しましょう。 頂点xで終わるK個の異なる頂点を持つシーケンスがあるとします。 まだ表現されていないy頂点を選択します。 グラフが強く接続されている場合、 xからyにつながる弧のチェーンが存在し、このチェーンがシーケンスに通過する頂点を追加します。 得られた新しいシーケンスでは、少なくともK + 1個の異なる頂点。

グラフの強く接続されたコンポーネントを新しい頂点に絞り込んだ後、方向付けられたグラフは循環せずに残ります。 頂点の初期シーケンスを構築できるようにするには、このグラフが頂点をトポロジカルに順序付ける唯一の方法を持っている必要があり、トポロジカルな収縮の任意の2つの隣接する頂点間にアークが存在する必要があることがわかります。

さらに、あるグラフで必要な頂点のシーケンスを作成できる場合、追加のアークを追加した後、このプロパティが保持されることに注意してください。

最適に構成されたプレイリストを聴くプロセスでアンナが経験する最大の不満について、バイナリ検索で問題への答えを探します。



したがって、問題を解決するための次のアルゴリズムを取得します。

バイナリ検索を使用して、Ui≤Uのアークのみをグラフに残す値Uを選択します。

結果のグラフの強く接続されたコンポーネントを別々の頂点に引き出します。

得られたグラフで、頂点のトポロジカルな順序を見つけ、隣接する頂点のすべてのペア間にアークがあることを確認します。

Uの特定の値に必要なシーケンスを見つけることができたかどうかに応じて、バイナリ検索をどの方向に移動するかを決定します。



便利なリンク：

en.wikipedia.org/wiki/Strongly_connected_component

en.wikipedia.org/wiki/Topological_sorting

C.ドキュメントのランキング

Ivanは通常のインターネットユーザーです。 Ivanのお気に入りのゲームの1つは「ハット」です。このゲームでは、隠された言葉をすばやく説明する必要があります。 面白いプレイをするために、彼はさまざまな検索クエリを尋ねて、インターネット上で異常な単語を検索します。



Ivanは、検索結果で1つのドキュメントが他のドキュメントよりも高い理由に常に関心がありました。 Yandex検索でこれについて尋ねると、Ivanはドキュメントがドキュメントの関連性の降順で自動的にソートされることを発見しました。 また、関連性は、特別なアルゴリズムによって選択された式に従って計算されます。



このタスクでは、関連式の単純化されたバージョン、つまりドキュメントパラメーターの線形結合を使用します。 ランキング式はN個のパラメーター（a1、a2、...、aN）で指定され、各ドキュメントはN個の数値パラメーター（f1、f2、...、fN）で記述されます。



関連性は次の式によって決定されます。





インターネットは急速に変化しており、一部のドキュメントは1分間に数回変化する場合があります。 もちろん、その後、このドキュメントのいくつかのパラメータを変更する必要があります。

文書パラメーターの変更に直面して最も関連性の高いものを見つけることができますか？



入力データ

入力の最初の行には、1つの整数N（1≤N≤100） -ランキング式のパラメーターの数が含まれます。 2行目には、 N個の整数ai（0≤ai≤100,000,000）が含まれます。



入力の3行目には、単一の整数D（10≤D≤100 000、N・D≤100 000） -ランク付けされるドキュメントの数が含まれます。 次に、 D行にはN個の整数fij （0≤fij≤100,000,000）-i番目のドキュメントの数値パラメーターが含まれます。



次の行には、1つの整数Q（1≤Q≤100 000） -ランキングシステムへのクエリの数が含まれています。 次のQ行はクエリを説明しています。 最も関連性の高い文書の発行要求は、 1 K（1≤K≤10）のペアで指定されます。 文書パラメーターを変更する要求は、4つの2 djv（1≤d≤D、1≤j≤N、0≤v≤100 000 000）によって与えられ、 d番目の文書のj番目のパラメーターがvになることを意味します。



インプリント

最初のタイプの各要求の後、関連性の高い順にK個の最も関連性の高いドキュメントのシリアル番号を1行に印刷します（番号は単一のスペースで区切る必要があります）。 常に、すべてのドキュメントが異なる関連値を持つことが保証されています。



問題解決

2番目のタイプのクエリを分析することから始めます。 このようなクエリを実行すると、関連性は1つのドキュメントのみで変更され、さらに、新しい関連性はO（1）で計算できることに注意してください。

最初のタイプのクエリを実行するには、関連性リストでK個の最大要素を見つける必要があります。 これには、バランスの取れた検索ツリーを使用できます。

C ++で実装する場合、標準コンテナstd :: mapを使用でき、Javaを使用する場合はTreeMapを使用できます。 これらのコンテナを使用する場合、ドキュメント関連の古い値をキーで削除し、その後新しい値でドキュメントを追加し、最大キーからの部分反復子パスにより最大値を検索できます。

2番目のタイプの操作は、で処理されます （キーによる削除と追加）、およびKの最大値を見つける操作 （少なくともC ++の場合）。

D.周波数リミッター

ローマンは普通のインターネットユーザーです。 他の多くの一般ユーザーと同様に、Romanは非常に短気です。 たとえば、現在、RomanはYandexのメインページでニュースの更新を待っており、ブラウザの[更新]をクリックし続けています。 膨大な数のリクエストでYandexを過負荷にしないために（ローマ人は非常に短気です！）、Romanからのすべてのリクエストはキューに追加され、そこから設定で指定された頻度を超えないようにニュースサービスに送信されます。



頻度制限は、2つの方法で設定できます。1秒あたりXリクエスト以下、またはY秒以下の1リクエストです。 各ローマのリクエストは、その時点で処理されます。その時点で処理されると、周波数制限に違反することはありませんが、当然、リクエストが送信された時点より前にはなりません。 詳細については例を参照してください。



サービスの動作をシミュレートして、各リクエストが処理されるポイントでリクエストとレポートの頻度を制限するプログラムを作成できますか？



入力データ

最初の行には、 X / Yの形式の周波数制限が含まれます。ここで、 XとYは2つの整数（1≤X、Y≤10000）で、少なくとも1つは1です。 Y = 1の場合、サービスは1秒あたりXリクエストを超えて処理するべきではありません。 X = 1の場合、サービスはY秒で複数のリクエストを処理しないでください。



2行目には、数値N（1≤N≤100,000）が含まれます。これは、ブラウザーの[更新]ボタンをクリックしてRomanがサーバーに送信したページ更新要求の数です。



次の行には、スペースで区切られたN個の整数ti（1≤ti≤1 000 000 000 000 000 000）が含まれます-要求を送信する時間をナノ秒（1秒で1 000 000 000ナノ秒）で指定します。 数値tiが減少しない順序で配置されていることが保証されます。



インプリント

スペースで区切られたN個の数字-各リクエストの処理時間を出力します。 説明の例を参照してください。



問題解決

この問題を解決するには、すべてのリクエストの時間を順番に読み取り、リクエストが処理された時間をアレイに書き込むだけで十分です。 i番目のリクエストの処理時間を取得するには、その到着時刻と（i-X）番目のリクエストの処理時間をY・1 000 000 000増やした最小値を取るだけで十分です（ i≤Xの場合、リクエストは受領後すぐに処理されます）。

E.カードサイズ

Alexeyは通常のインターネットユーザーです。 かつて、AlexseyはYandex.Mapsサービスを使用して、結局のところ、画面上の最終画像はおそらくサーバーから受信したいくつかの小さな長方形の画像から形成されると考えました。 Alexeiは、画面上に表示される画像の作成に使用できるほど多くのサイズの画像が存在することに興味を持ちました。



地図の表示領域は、Alexeyの画面でN×Mピクセルを占有します。 ペアの数（A、B）（1≤A≤N、1≤B≤M）に興味があるため、 A×Bの長方形を使用して、 N×Mの長方形をレイアウトし、重なり合ったり回転したりせずに互いに近づけます。 同時に、Alexeyはサーバーから大きな画像を送信するのは非常に高価であると確信しているため、 A・B> Rであるペア（A、B）には興味がありません。 Alexeyは、多数の小さな写真を送信することも収益性がないことも理解しているため、 A・B <Lであるペア（A、B）には興味がありません。



Alexeyが彼の質問に答えるのを手伝ってください。



入力データ

入力ファイルの唯一の行には、スペースで区切られた4つの整数N、M、L、R（1≤N、M≤1,000,000,000、1≤L≤R≤N・M）が含まれています。



インプリント

単一の数値：Alexeyの要件を満たす可能性のあるペアの数を出力します。



問題解決

長方形A × Bをレイアウトできるという条件から、長方形N × Mは、 NがAで除算され、 MがBで除算されることを意味します。 分周器Nと分周器MのリストDmで構成されるリストDnを作成します。 ご存じのように、任意の数Xのすべての約数を見つけることができます 。 このようなリストが2つあると、ネストされた2つのサイクルですべての候補ペア（A、B）をソートし、条件L≤A・B≤Rが満たされていることを確認できます。 条件が満たされている場合、応答を1増やす必要があります。



ボーナス：1,000,000,000までの数の除数の最大数は1344です。

F.道路の混雑

Juraは普通のインターネットユーザーです。 彼は世界の都市の歴史を読むのが大好きで、さらに旅行やこれらの旅行中にX世紀またはXVI世紀の特定の場所で何が起こったかを友人に伝えるのが大好きです。 ジュラが新しい都市に到着したとき、彼はすでにこのエリアのアトラクションのリストを持っています。残っているのは、これらの場所に正しくルーティングすることだけです。



良いルートを築くために、JuraはYandex.Mapsサービスを使用します。 彼は信号機のあるボタンに注意を引き、それを押しました。 マップ上の道路はさまざまな色で描かれています。 ジュラは、Yandexが交通渋滞をどのように判断するかに興味を持ち、インターネットで情報を検索することにしました。



このタスクでは、交通渋滞の判定を簡素化したバージョンを使用します。 マップサービスのすべての道路には、1〜Mの整数で番号が付けられます。 各道路について、 LiとRiの 2つの数字が知られています。 現在の時点で道路上にLi車が少ない場合、道路は無料と見なされ、地図上では緑色で描画されます。 現在の時点で道路上にRiを超える車が存在する場合、道路は混雑していると見なされ、地図上に赤で描画されます。 道路が無料でも混雑していない場合は、サービス上にオレンジで描かれます。



マップサービスを備えた道路の説明と、 N台の車の位置に関する情報が提供されます。 これらの道路をマップ上に描画する色を決定できますか？



入力データ

入力の最初の行には整数M（1≤M≤1,000） -道路の数が含まれています。 この後に、それぞれに2つの整数LiとRi（ 1≤Li≤Ri≤10 ）の M行が続きます-i番目の道路のパラメーター。 次の行には、単一の整数N（1≤N≤1,000） -現在道路を走行している車の数が含まれています。 次の行には、 N個の整数rj（1≤rj≤M） -車が位置する道路番号が含まれています。



インプリント

入力から道路ごとに1行、 M行を印刷します。 i番目の道路を赤でペイントする必要がある場合、 i番目の行にオレンジである場合は「赤」、「オレンジ」で印刷し、それ以外の場合は「緑」で印刷します。



問題解決

まず、タスクでは、各道路について、その車の数を計算する必要があります。 そして、各道路のパラメータに応じて、渋滞の程度を簡単に判断できます。

また、Pythonでかなり単純な実装が取得されます。

 import sys M = int(sys.stdin.readline()) LR = [] C = [0] * M for i in xrange(M): LR.append(map(int, sys.stdin.readline().split())) N = int(sys.stdin.readline()) for r in map(int, sys.stdin.readline().split()): C[r - 1] += 1 for i in xrange(M): print "Green" if C[i] < LR[i][0] else ("Red" if C[i] > LR[i][1] else "Orange")