スポンサーリンク

【LeetCode】 649. Dota2 Senate 解答・解説【Python】

スポンサーリンク
スポンサーリンク
この記事は約6分で読めます。

 

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

 

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

 

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

 

 

ポイント

 

 

詳細

 

問題

 

原文

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

  • Ban one senator’s right: A senator can make another senator lose all his rights in this and all the following rounds.
  • Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.

Given a string senate representing each senator’s party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".

 

Example 1:

Example 2:

 

Constraints:

  • n == senate.length
  • 1 <= n <= 104
  • senate[i] is either 'R' or 'D'.

 

 

内容(和訳)

Dota2の世界には、RadiantとDireの2つの党があります。

Dota2の上院は、2つの政党からなる上院議員で構成されています。現在、上院はDota2ゲームの変更を決定しようとしています。この変更の投票は、ラウンドをベースにした手順です。各ラウンドで、各上院議員は次の2つの権利のいずれかを行使できます。

  1. 上院議員は、別の上院議員の権利を禁止することができます。上院議員は、このラウンドと次のすべてのラウンドすべてですべての権利を失うようにすることができます。
  2. 勝利を宣言する:この上院議員は、まだ投票する権利を持っている上院議員がすべて同じ政党からのものである場合、勝利を宣言し、ゲームの変更を決定することができます。

各上院議員の所属政党を表す文字列senateが与えられます。文字’R’と’D’はRadiant党とDire党を表します。次に、上院議員がn人いる場合は、与えられた文字列のサイズはnになります。

ラウンドをベースにした手順は、指定された順序で最初の上院議員から最後の上院議員まで開始されます。この手順は、投票が終了するまで続きます。手順中、権利を失った上院議員はすべてスキップされます。

すべての上院議員が賢く、自分の党のために最善の戦略を実行すると仮定します。最終的に勝利を宣言し、Dota2ゲームを変更する党を予測してください。出力は「Radiant」または「Dire」です。

 

 

簡潔にまとめなおしてみる。

Radiant党とDire党があり、どちらかの勝利を決める。

各党員は以下のどちらかを行うことができる。

・相手チームを1人永遠に行動不能にする

・相手チームが0人だったら勝利宣言を行う

全員の行動が終わったら残っているチームメンバーで第二、第三ラウンドと繰り返す。

 

なので、相手チームのメンバーを全員行動不能にすることを考える。

 

 

※Bardによる翻訳

 

解答

 

解答1:Python, キュー, iterative

 

 

 

 

終わりに

補足・参考・感想

 

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

 

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

 

 

他の問題もどうぞ

 

前:1207. Unique Number of Occurrences

 

次:872. Leaf-Similar Trees

 

LeetCode 解答・解説記事一覧

 

コメント