受講レベル診断テスト

あなたはカエルです。N個の足場が1列に並んでおり、i番目の足場に飛ぶと Ci のコストがかかります。あなたは1回のジャンプで、1つ先か2つ先の足場にしか飛べません。 スタート（0番目）からゴール（N-1番目）まで、合計コストを最小にしてたどり着くための考え方として、最も適切なものはどれでしょう？

あなたはゲームのスコア分析官です。1試合ごとに記録されたスコアの変動リスト [+10, -5, +20, +15, -30, ...] が100万試合分あります。 「第i試合から第j試合までの正味のスコア変動は？」という形式のクエリが、10万回飛んできます。この大量のクエリを効率的にさばくための最適なアプローチはどれでしょう？

SNSで、あるインフルエンサーAさんが「この投稿は、私のフォロワーのフォロワーまで届けたい！」と考えています。 Aさんから見て「友達（距離1）」と「友達の友達（距離2）」にあたる人々の数を、重複なく数え上げるのに最も適したアルゴリズムはどれでしょう？

ある問題に対する2つのアルゴリズムAとBがあります。データサイズをNとしたとき、それぞれの計算量は以下の通りです。

• アルゴリズムA: O(N²)
• アルゴリズムB: $O(N\log N)$

データサイズNが100万のとき、実行速度はどちらがどのくらい速いと予想されますか？

あなたは魔法薬の調合師です。薬のレシピに「魔法水をちょうどKミリリットル加える」とありますが、大事なKの値が書かれたページが破れてしまっています。ただし、以下のことは分かっています。

• 魔法水がKミリリットル未満だと薬は黒く変色する。
• 魔法水がKミリリットル以上だと薬は白く輝く。
• Kは1から1,000,000までの整数のいずれか。

最小の試行回数でKを特定するには、どのような戦略をとるべきですか？

広大な2次元マップ上に、N個の宝箱が点在しています。Nは最大10万ですが、マップの広さは 109×109 と非常に広大です。 宝箱の「X座標の大小関係」と「Y座標の大小関係」だけを保ったまま、この問題を小さなグリッド上の問題として扱いたい場合、どのような前処理が有効ですか？

あなたは大規模な計算サーバーのタスク管理をしています。複数のタスクが随時追加され、それぞれに「優先度」が設定されています。
システムは常に、現在溜まっているタスクの中から「最も優先度の高い」ものを次に取り出して実行しなければなりません。この処理を効率的に実現するのに最も適したデータ構造は？

N個の都市があり、M本の双方向の道路建設計画があります。計画は (都市A, 都市B) のペアで与えられます。
「都市Xと都市Yは、現時点の計画で（間接的にでも）繋がっていますか？」という形式の質問に、何度も高速で答えたい。この目的に特化した、非常に高速なデータ構造は？

あなたはパン屋さんです。1円、5円、10円、50円、100円、500円の硬貨が無限にあります。 N円の買い物に対し、できるだけ少ない枚数の硬貨でお釣りを渡したいです。この問題を解くためのアルゴリズムとして、最も適切でないものはどれですか？

あなたはコンサートホールの管理人です。1年分のホールの予約がN件入っており、各予約は「利用開始日」と「利用終了日」で記録されています。 この1年間で、ホールが最も多くの予約で重複していた日の、予約重複数はいくつかを効率的に求めたいです。