Clever Geek Handbook

オリンピック趣味。 分割して征服する

みなさんこんにちは。 月曜日があなたにとって最も楽しい日ではない場合は、少しリラックスして私の趣味を楽しむことをお勧めします。 私の趣味は、オリンピックのプログラミングの問題を解決することです。脳を揺さぶり、想像力を刺激し、エネルギーを与えます（常にポジティブではありません）。 信じられない？ 自分で試して、正直に問題を解決し、待望の受諾を得て、受け取った感情を楽しんでください。



今日、問題は私たちに問題番号10474を投げました 。 これは、時間内に単純なアルゴリズムを適用するためのタスクであるため、複雑で独創的なものを期待しないでください。 いくつかの標準アルゴリズムを使用して問題を解決することに興味がない場合は、このトピックをスキップしてください。他のすべての人はcatを歓迎します。 私たちは、いくつかのアルゴリズム、最も便利なソリューションの選択、そしてもちろん、受け入れられるのを待っています！





タスクをランダムに選択します。 タスクが単純すぎる場合、または解決方法を想像できないタスクの場合、数日間の苦痛の後、別のタスクを選択します。 しかし、真剣に、私はランダム性に加えて、たった1つのことだけにとらわれないように、さまざまなタスクを選択しようとします。 私の選択はあまり成功していないように見えるかもしれませんが、これは私の仕事ではなく、単なる趣味であるため、これを断言して取るようにお願いします。



簡単なタスクに出会ったら、その最も迅速な、または最も美しい解決策を見つけ、時間を無駄にしたとは思わないでしょう。 まあ、あなたの決定を共有することを忘れないでください、それは確かに私のものよりも美しくて速くなります。 ハブの視聴者はまともだから、まだ誰も知らないアルゴリズムを考え出すことさえできるかもしれません;）



タスク条件



ビジネスに取り掛かろう。 私が言ったように、今日は問題番号10474を解決します

私は問題の条件の無料翻訳をもたらします：

ラジュとミーナはマーブル（おそらくゲームの名前）をプレイするのが大好きです。 彼らは多くのナンバープレートを持っています。 最初に、Rajuは数字の昇順でタブレットを次々に配置します。 それからミーナはラジュに最初のナンバープレートの番号を探すように頼みます。 彼女は3人まで数えます。 ラージュが正しい番号に電話した場合、ポイントを獲得します。そうでない場合、ポイントはミーナを獲得します。 一定回数試行すると、ゲームは停止し、ポイントが最も多いゲームが勝ちます。 今日、あなたはラジュとしてプレイする機会があります。 上級者として、あなたはコンピューターを使用しています。 しかし、Meenaを過小評価しないでください。彼女は、あなたが正しい答えを得るのに費やした時間を追跡するプログラムを書いています。 Rajuの役割を果たすのに役立つプログラムを作成する必要があります。



入力データ：

いくつかのテストが可能ですが、65以下です。テストは、N-プレートの数とQ-Meenaリクエストの数の2つの数字で始まります。 この後に、N個のタブレットに書かれた数字を含むN行が続きます。 これらの番号は順序付けられていません。 次はクエリのあるQ行です。 10000を超える入力数値はなく、すべての数値は負ではありません。

NとQが0になると、入力は終了します。



出力データ：

アルゴリズムの制限時間：3秒。

各テストについて、テストのシリアル番号が表示されます。

要求ごとに、1行が表示されます。 文字列の形式は、要求された番号がラベル内で見つかったかどうかによって異なります。 2つのオプション：

  • 番号xを持つ最初のラベルが位置yで見つかった場合、「X found at y」。 ポジションには次のように番号が付けられます：1、2、3 ...
  • 番号xのラベルがない場合、「X not found」。
例：

入力：

4 1

2

3

5

1

5

5 2

1

3

3

3

1

2

3

0 0



結論：

事例＃1：

4で5

事例2：

2見つかりません

3で3が見つかりました



このタスクはアルゴリズム問題のクラスに属し、より正確には「分割して征服する」セクションに属します。



これは誰にとっても小さな手がかりです。 これ以上読むことなく、独自のソリューションを作成することをお勧めします。 次に、結果を私のものと比較することは興味深いでしょう。



私たちのタスク：番号付きのプレートを配置し、番号付きの最初のプレートの番号を見つけます。 この問題を解決するための2つのオプションを考え出しました（さらに、小さい数字の数を決定して数字を検索するだけでなく、額の中に）。 そのため、両方のオプションを連続して検討し、どちらが優れているのか、なぜかを判断します。



解決策



オプション1


配列を並べ替える価値があると判断し、その中から数字を見つけました。 今では多くの人が私を「キャップ」と呼ぶことを知っています。 私がタスクを担当するサイトでは、ソリューションの品質の主な基準はプログラムの実行時間です。 アルゴリズムの実行時間を短縮するために、クイックソートと配列内のバイナリ検索を使用します。 つまり この問題を解決するために、入力配列を数字ですばやくソートするためのアルゴリズムを順次実装し、次にバイナリ検索アルゴリズムを実装します。



これらのアルゴリズムの知識、そして最も重要なのは、それらを実装する機能は、実際のプログラミングに役立ちます。したがって、特に両方とも非常に単純であるため、これまでに実装したことがない人のためにアルゴリズムを理解することをお勧めします。



ここでは、クイックソートアルゴリズムについて詳しく説明します 。 手順の簡単な説明のみを行います。

1.配列内の要素が選択されます-参照要素。 通常、それらは中心要素を取りますが、他の要素を選択したほうがよい場合があります。それは配列のプロパティに依存します。

2.参照番号よりも小さい要素はすべて配列の左側に移動し、要素は右側の参照よりも大きくなります。 T.O. 配列を2つのサブセットに分割します。 支持要素の左側には、支持要素よりも小さい要素があり、右側も同様です。

3.両方のサブアレイで、要素の数が2つ以上の場合、すべてのステップが再度実行されます。



クイックソートには、作業を高速化する修正があります。 興味がある場合は、修正を実装して、実際にアルゴリズムの加速を確認してください。



順序付けられた配列のバイナリ検索アルゴリズムはさらに単純です。

1.配列の中心要素が選択され、配列が2つのサブ配列に分割されます。

2.選択したアイテムが目的のアイテムよりも大きい場合は、同じスキームに従って左側のサブアレイで検索を続けます。 少ない場合は、右側にあります。

その結果、目的の要素にすばやく到達します。



注意が必要なのは、同じ番号のプレートが存在する場合、バイナリ検索で必ずしも最初に目的の番号が見つかるとは限らないことだけです。 目的の番号の最初の出現のインデックスが決定されるように、バイナリ検索手順を実装する必要があります。



最初の解決策：受け入れられた0.368



オプション2


条件に説明されている制限に注意を払うと、入力数が10000を超えない場合、別のソリューションが表示されます。 タブレットに数字を入力する前に、10,000個の要素に対してMの配列を作成できます。

M [i] = 0（番号iのプレートがない場合）

M [i] = r。ここで、rは番号iのプレートの数です。



数値を入力すると、この配列をすぐに埋めることができます。 配列を埋めるときに、一意の番号の数を決定します。



次に、さらに2つの配列（または、必要に応じて構造体の配列）を作成します。 最初の要素の配列には、昇順で一意の番号が含まれます。 位置の2番目の配列には、位置[i]が要素数[i]の最初の位置の番号である位置が含まれます。 これらの配列は、配列Mを1回通過することで埋めることができます。

0. pos = 0-現在の位置、j = 0-現在の一意の番号

1. M [i]！= 0を探しています

2.新しい数値を要素[j] = iに入れます

3.位置[i] = pos

4. M [i]、j ++の位置をシフトします

5.すべての10,000の数値を渡していない場合（または作業を高速化するために最大値を覚えている場合）、手順1に進みます。



これで要素の配列ができました。ここで再びバイナリ検索を使用して数値を検索します。 elements配列で見つかった番号のインデックスを使用して位置の配列から回答を発行します。



2番目の解決策：受け入れられた0.248



2番目のオプションが最初のオプションよりも高速だったのはなぜですか？ これら2つのアプローチの主な違いは、2番目のバージョンでは、最も時間がかかるソートを放棄したことです。 時間の並べ替えを無駄にする代わりに、必要以上のRAMを盗みました。 また、同じ番号のプレートが存在する場合、要素の少ない配列でバイナリ検索が実行されます。

2番目のオプションは、入力数が4バイトの容量によってのみ制限されている場合は適用できません。 オリンピックでは、しばしば発生するこの種の条件に注意を払う価値がある場合があり、問題の代替ソリューションを示唆しています。



では、なぜタスクはアルゴリズムの分割統治セクションに関連するのですか？ 使用されている両方のアルゴリズムがこのセクションに属しているためです。クイックソートでは配列を2つの部分に分割してからソートし、バイナリ検索では目的の領域を半分に分割することで常に検索を絞り込みました。



この問題には他の解決策もあります。より高速な解決策を見つけてください。 最初のソリューションを他のソートアルゴリズムと比較することは興味深いでしょう。 別の並べ替えで最初のオプションを実装している場合は、コメントを購読解除します。 さまざまな種類の速度に関する独自の統計を収集してみましょう。

ここで決定を確認できます（登録が必要です）。



PSウェブサイトhttp://uva.onlinejudge.org/ 、タスクの出所である私は、FFでの読み込みを突然停止しました。 これがブラウザの問題かどうかはわかりませんが、サイトは他のブラウザで開きます。 突然同じ問題が発生した場合は注意してください。



私の決定は、いつものように、 オプション1とオプション2からダウンロードできます。



受け入れられました（0.248）。 頑張って



UPD： dimoclus氏のプロンプトのおかげで、Accepted（0.108）（ ダウンロード ）の2番目のオプションを高速化することができました

UPD：また、実行速度が0.104のKapJI氏の決定にも注意してください。



UPD：ハブのリーダーであるAlekseyは、uva.onlinejudge.orgサイトのすべてのユーザーの中で最高の時間 （0.052）を獲得しました。 これが彼の解決策です。 おめでとうございます！

追加の招待を持っているPSは、Alexeyに後悔しないでください。彼は私たちと共有するものがあると思います。


More articles:


All Articles