🐎

AtCoder Beginner Contest 302 B問題解説

2023/05/21に公開

Python

AtCoder

tech

今回はAtCoder Beginner Contest 302のB問題です．
そうです．まさかのB問題で躓きました．はぁ・・・・
言語はPython3(PyPy3)になります.

ちなみに前回はcollectionライブラリのCounterモジュールを使った問題を解説してますので，よければご覧ください．

まずは問題を見てみましょう．

問題文

縦 H マス × 横 W マスのマス目があり、各マスに 1 つずつ英小文字が書き込まれています。上から i 行目かつ左から j 列目のマスを (i,j) で表します。
マス目に書き込まれている英小文字は H 個の長さ W の文字列 S_1 ,S_2, …, S_Hによって与えられ、 S_i の j 文字目が、(i,j) に書き込まれた英小文字を表します。

マス目の中に、s, n, u, k, e がこの順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる場所がただ 1 つ存在します。
そのような場所を見つけ、そのマスの位置を出力の形式に従って出力してください。

ただし、s, n, u, k, e がこの順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる場所とは、 5 つのマスの組 (A_1, A_2, A_3, A_4, A_5) であって、次をすべてみたすものをさします。

A_1, A_2, A_3, A_4, A_5 に書き込まれた英小文字はそれぞれ s, n, u, k, e である。
1≤i≤4 について、A_i と A_i+1 は頂点または辺を共有している。
A_1, A_2, A_3, A_4, A_5の中心はこの順に一直線上に等間隔で並んでいる。

制約

5≤H≤100
5≤W≤100
H,W は整数
S_i は英小文字のみからなる長さ W の文字列
与えられるマス目の中に条件をみたす場所がただ 1 つ存在する

入力

入力は以下の形式で標準入力から与えられる。

H W
S_1 
S_2	
⋮
S_H

出力

次の形式にしたがって、5 行出力せよ。

条件をみたす場所のうち s, n, u, k, e が書かれたマスがそれぞれ (R_1, C_1),(R_2,C_2)…,(R_5,C_5) であるとき、 i 行目には R_i と C_i をこの順に空白区切りで出力せよ。

すなわち、以下のように出力せよ。

R_1 C_1
R_2 C_2
⋮
R_5 C_ 5

これあれですね，問題文に記号が増えるほど，こちらに書き起こすのがめっちゃめんどくさくなりますね．もしかしたら大変すぎる時は引用だけになるかもです．

以下解説です．また言葉の使い方やその他ミスがあればご指摘ください．

躓いたポイント

1. 自由度をコードに反映させる
2. 多重ループの抜け方（本問は考えなくて良かった

ほぼ1のせいです．難しく考えすぎて，最初コード書き終えた時にテストで回したらポインター(みたいなやつ)が自由に動き回ってました🫠

2は結果的に考える必要ありませんでした．なぜならsnukeの文字は行列の中に1パターンしかなかったから，かつオーダーも気にしなくてよかったからです．てことで解説では考慮しませんが一応躓いたポイントなのでご紹介だけ．

解き方

1. sを見つける.
2. sの周囲に存在する次の文字nを見つける(なかったら次のsを探す)
3. 2と同様の手順を他の文字に対しても行う

ここでポイントになることは，欲しい文字列は行列の中に一直線に存在することです．途中で折り返して文字を見つけたりしてはいけません．（私はここで躓きました）
さてどうしましょうか？

答えは簡単でした.sのマスからから横と縦を(i,j)(i×2,j×2)(i×3,j×3)(i×4,j×4)と移動させればいいじゃないか！　
ということで，それをコード化しましょう．

H,W = map(int, input().split())
l = [input() for _ in range(H)]

for i in range(H):
  for j in range(W):
    if l[i][j] == "s":
      for k in range(-1, 2):
        for n in range(-1, 2):
          try:
            if l[i+k][j+n] == "n" and i+k >= 0 and j+n >= 0:
              if l[i+k*2][j+n*2] == "u" and i+k*2 >= 0 and j+n*2 >= 0:
                if l[i+k*3][j+n*3] == "k" and i+k*3 >= 0 and j+n*3 >= 0:
                  if l[i+k*4][j+n*4] == "e" and i+k*4 >= 0 and j+n*4 >= 0:
                    for m in range(5):
                      print(i+k*m+1, end=" ")
                      print(j+n*m+1)
                    
          except IndexError:
            continue

気をつけることはマス目の移動範囲は縦横-1〜1であること，またIndexErrorが起きる可能性もあることです．
IndexErrorを起こさないために条件分岐でもいいのですが，めんどくさいのでtry-exceptで無理やり通しちゃいましょう！(プロ竸以外でこんな力技やったらダメです)

次は別解の紹介

別解

ここでは移動する方向が自分自身のマスを除く8パターンしかないことに注目します．
自分の思いついた方法じゃないので紹介だけ．こんな方法もあるんだって感じで見てもらえたら嬉しいです．(でもこっちの方がスマートだと思う)

H, W = map(int, input().split())
l = []
 
for i in range(H):
    l.append(list(input()))
 
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
 
for i in range(H):
    for j in range(W):
        for k in range(8):
            str = ""
            for t in range(5):
                x = i+t*dx[k]
                y = j+t*dy[k]
                if x < 0 or x >= H or y < 0 or y >= W:
                    break
                str += l[x][y]
            if str == "snuke":
                for t in range(5):
                    x = i+t*dx[k]+1
                    y = j+t*dy[k]+1
                    print(x, end=" ")
                    print(y)

やってることは同じですが，こうやって移動方向をリストに入れて回すってやり方身につけたいですね．

問題文

制約

入力

出力

躓いたポイント

解き方

別解

Discussion