ダンジョンのデッドロック 1 Python3編
やや難解な問題文にひっかかってハマってしまったので、問題の意図するところを記述しておきます。
コード云々以前にアルゴリズムが組み立てられなかった人向けの記事です。
ダンジョンのデッドロック 1 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】
【問題文】
あなたは RPG のダンジョンの設計をしています。
そのダンジョンには N 個の部屋が用意されており、それぞれの部屋は 1, 2, ..., N で表されます。このダンジョンでは 1 部屋に 1 プレイヤーしか滞在できません。
また、プレイヤーは M 人いて、現在 i (1 ≦ i ≦ M) 番目のプレイヤーは部屋 S_i (1 ≦ S_i ≦ N) に滞在しています。
ダンジョンをクリアするには、プレイヤーはそれぞれ、部屋を移動する必要があります。
しかし、部屋を移動しようと思ってもその部屋はまだ別のプレイヤーが滞在しているかもしれません。その場合はプレイヤーは部屋を移動することができません。
(参考図)
そこで、それぞれのプレイヤーが部屋を移動できるか事前に判定することにしました。
あなたの仕事は、各 i (1 ≦ i ≦ Q) について、現在の状況から E_i 番目のプレイヤーが部屋 T_i に移動できるか判定することです。
ただし、滞在している部屋と移動先の部屋が同じ場合、つまり S_i = T_i (1 ≦ i ≦ M) の場合、そのプレイヤーは移動ができることとします。
また各 i (1 ≦ i ≦ Q) について、部屋を移動できると判定された場合でも、実際に移動はしないものとします。
◆入力される値
N M Q
S_1
S_2
...
S_M
E_1 T_1
E_2 T_2
...
E_Q T_Q
・1 行目には、ダンジョンの部屋の数 N ,プレイヤー数 M, 判定する回数 Q がこの順で半角スペース区切りで与えられます。
・続く M 行のうちの i 行目 (1 ≦ i ≦ M) には、i 人目のプレイヤーの現在滞在している部屋 S_i が与えられます。
・続く Q 行のうちの i 行目 (1 ≦ i ≦ Q) には、部屋の移動をするプレイヤーの番号 E_i, 移動先の部屋 T_i がこの順で半角スペース区切りで与えられます。
・入力は合計で M + Q + 1 行となり、 入力値最終行の末尾に改行が 1 つ入ります。
◆期待する出力
・合計 Q 行出力してください。各行の末尾に改行を入れ、余計な文字、空行を含んではいけません。
・i 行目 (1 ≦ i ≦ Q) には、現在の状況から E_i 番目のプレイヤーが部屋 T_i に移動することができる場合は "Yes" を、できない場合は "No" を出力してください。
◆問題文の整理
・ダンジョンの部屋は N 個
・プレイヤー数は M 人
・現在 i 番目のプレイヤーは、現在入力値 S 行 i 番目の部屋に滞在している
・このとき、現在入力値 E 行 i 番目のプレイヤーが入力値 T 行 i 番目の部屋に移動できるか(行き先が空室かどうか)を調べる
・ただし、滞在先と行き先が同じ部屋番号であった場合には、そのプレイヤーは移動できるものとする
・また各 i 番目のプレイヤーについて、部屋を移動できると判定された場合でも、実際に移動はしないものとする
◆入力される値の内容
N(ダンジョン部屋数) M(プレイヤー数) Q(判定する回数)
-
プレイヤーの現在滞在している部屋 S_i
-
部屋の移動をするプレイヤーの番号 E_i, 移動先の部屋 T_i
以上の形式で構成されます。
◆入力例2
15 10 10 N(ダンジョン部屋数) M(プレイヤー数) Q(判定する回数)
-
1 S 行目 *それぞれ i 番目のプレイヤーが現在滞在している部屋の番号
2
3
4
5
11
12
13
14
15
-
1 6 E 行目 *プレイヤー番号 i と、そのプレイヤーが行きたい部屋の番号
5 6
6 6
8 6
5 11
6 11
9 11
10 11
6 2
8 3
◆出力例2
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
◆この問題のポイント
i という数値がそれぞれの入力される値の箇所において何なのかを理解すること。これに尽きると思います。
結論から言ってしまえば、数値 i はプレイヤーにそれぞれ与えられる固有の番号です。前から順番に+1ずつ振り分けられるIDのようなものです。
しかしその認識だけでは、プログラミングに詳しくない人にとって「部屋 S_i 」という記述では理解するのが難しいでしょう。
これは、入力される値 S ブロックの i 番目の数値という意味です。私もこの問題で初めて読み解けるようになりました!
つまり・・・S が記述されているブロックの6番目の入力される数値は 11 ですが、これは「 11 番目の部屋にプレイヤー番号 6 番の人がいる」という意味になります。ややこしいですね~
S のブロックに書かれる 1 つの数字には二つの情報が込められているわけですね。
続く E の値が記述されているブロックでは、<部屋の移動をするプレイヤーの番号 E_i, 移動先の部屋 T_i >が与えられます。
つまり・・・ E が記述されているブロックの 6 番目の入力される数値は< 6, 11 >ですが、これは「S ブロックの 6 番目のプレイヤー(現在11番目の部屋にいる)が、次に部屋番号11番に行きたい」という意味になります。
これでおおかたの難所は越えたのですが、実はもう一つ落とし穴があります。笑
このダンジョンは、ワープで移動するというところです。
普通のローグライクなどRPGのダンジョンマップを想像するとうまくいきません。
たとえば、ホワイトボードに1~9の部屋を書いて、そこに各種プレーヤー番号を書いたマグネットを置くことでプレイヤーの有無を表現するようなイメージで考えてください。
部屋と部屋同士が道で繋がっている必要はないので、マップを書いて部屋の配置を考える必要はありません。
<あなたはRPGダンジョンの設計をしています>と冒頭で言ってしまっているあたり、ややいじわるな問題だなと感じます。笑
私が提出したコード。
info = input().split() room_num = int(info[0]) player_num = int(info[1]) times = int(info[2]) player_point_array = [0 for i in range(room_num)] player_num_array = [] #make player point list for i in range(player_num): a = int(input()) player_point_array[a - 1] = a player_num_array.append(a) #print(player_point_array) #print(player_num_array) #get player_num & where will it want to go for i in range(times): info_move = input().split() player_list_num = int(info_move[0]) move_for = int(info_move[1]) # print(player_list_num) # print(str(i + 1) + ":", end = "") # print(player_num_array[player_list_num - 1]) if player_num_array[player_list_num - 1] == move_for: print("Yes") elif player_point_array[move_for- 1] == 0: print("Yes") else: print("No")