paiza Aランクレベルアップ問題集【マップの判定･縦横】解いてみたPart1【Python3】

前置き

• Part2

• 問題文

paizaのレベルアップ問題集はコードの公開が許可されてるとのことなので､ 自分のコードに対する理解の確認も兼ねてPython3でのAランクレベルアップ問題集の解説を順次行っていきたいと思いました｡
(Aランク以上の問題を解いてるときにBランクレベルの問題で用いたアルゴリズムの組み合わせが必要な場合が多く､ 理解の整理の必要性を感じた)

ネタバレ全開の記事になってるのでまだ解いてない方はブラウザバック推奨です

STEP: 1 盤面の情報取得

問題文
https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_snake_map_step1

step1.py

def int_input():
    return [int(i) for i in (lambda x: x.split())(input())]
    # 入力をint型のリストにして返す


def main():
    line = int_input()
    h_rows, w_columns, n_num = line[0], line[1], line[2]
    array = [] #変数名にmapを使うのは良くない(map関数と被るので､ 昔よくやってました)
    for h in range(h_rows):
        array.append(input())
    spots = []
    for n in range(n_num):
        spots.append(int_input())
    for spot in spots:
        print(array[spot[0]][spot[1]])


if __name__ == '__main__':
    main()

とくに難しいところはないと思います､ もっと複雑なマップの入力を格納する問題ではNumpyを使うといいと思います｡(←この判断のタイミングが大事だと思う)

STEP: 2 盤面の情報変更

問題文
https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_snake_map_step2

step2.py

def int_input():
    return [int(i) for i in (lambda x: x.split())(input())]
    # 入力をint型のリストにして返す


def main():
    line = int_input()
    h_rows, w_columns, n_num = line[0], line[1], line[2]
    array = []
    for h in range(h_rows):
        array.append(list(input())) #入力した文字列をリストに変換した
    spots = []
    for n in range(n_num):
        spots.append(int_input())
    for spot in spots:
        array[spot[0]][spot[1]] = '#'
    for h in range(h_rows):
        for w in range(w_columns):
            print(array[h][w], end='') #改行させないためには引数にendオプションを利用する
            if w == w_columns-1:
                print('')


if __name__ == '__main__':
    main()

より複雑な問題でも頻出な考えなので､ 構文のように素早く書けるようになりたいです(マップを格納するオブジェクトに適切な型を用いてるかは常に意識したい)｡

STEP: 3 マップの判定・横

問題文
https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_snake_map_step3

step3.py

def int_input():
    return [int(i) for i in (lambda x: x.split())(input())]


def main():
    line = int_input()
    h_rows, w_columns = line[0], line[1]
    for h in range(h_rows):
        line = input()
        line = '#' + line + '#' #橋の処理をifでやるとややこしいので端に初めから'#'を両辺に足した
        for w in range(w_columns):
            if line[w] == '#' and line[w+2] == '#':
                print(f'{h} {w}')


if __name__ == '__main__':
    main()

両端の処理でif文を使うと煩雑になりやすいのです､ 煩雑なif文はバグの元なので避けたいです｡

STEP: 4 マップの判定・縦

問題文
https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_snake_map_step4

step4

import numpy as np


def int_input():
    return [int(i) for i in (lambda x: x.split())(input())]


def main():
    line = int_input()
    h_rows, w_columns = line[0], line[1]

    map_array = []
    for h in range(h_rows):
        map_array.append(list(input()))
    map_array = np.array(map_array) #Numpyとリストの変換は基本的にこれおｋ
    sharp_array = np.array([list(('#')*w_columns)])
    map_array = np.concatenate([sharp_array, map_array, sharp_array], 0) #concatenateメソッドを用いると次元を自由にとって行列の結合ができるので便利

    for h in range(h_rows):
        for w in range(w_columns):
            if map_array[h][w] == '#' and map_array[h+2][w] == '#':
                print(f'{h} {w}')


if __name__ == '__main__':
    main()

Python標準のリストですと､ 縦横の入れ替えはけっこうめんどうになることが多いので今回はNumpyを使いました｡

• →Numpyを使わずに転置行列を作る手法が載っています

-Final問題- マップの判定・縦横

問題文
https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_snake_map_boss

step5.py

import numpy as np


def int_input():
    return [int(i) for i in (lambda x: x.split())(input())]


def main():
    line = int_input()
    h_rows, w_columns = line[0], line[1]

    map_array = []
    for h in range(h_rows):
        map_array.append(list(input()))
    map_array = np.array(map_array)
    sharp_array = np.array([list(('#')*w_columns)])
    map_array = np.concatenate([sharp_array, map_array, sharp_array], 0)
    sharp_array = np.array([list(('#')*(h_rows+2))]).T #すでに行の両端は延長してあるので長さを+2してる
    map_array = np.concatenate([sharp_array, map_array, sharp_array], 1) #縦方向のときは引数に縦に相当する次元1を追加する

    for h in range(h_rows):
        for w in range(w_columns):
            if map_array[h+1][w] == '#' and map_array[h+1][w+2] == '#':
                if map_array[h][w+1] == '#' and map_array[h+2][w+1] == '#':
                    print(f'{h} {w}')


if __name__ == '__main__':
    main()

print(map_array)したときに

[['#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#']
 ['#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#']
 ['#' '.' '.' '.' '.' '.' '.' '.' '.' '.' '.' '#']
 ['#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#']
 ['#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#']
 ['#' '.' '.' '.' '.' '.' '.' '.' '.' '.' '.' '#']
 ['#' '#' '.' '#' '.' '#' '.' '#' '.' '#' '.' '#']
 ['#' '.' '#' '.' '#' '.' '#' '.' '#' '.' '#' '#']
 ['#' '#' '.' '#' '.' '#' '.' '#' '.' '#' '.' '#']
 ['#' '.' '#' '.' '#' '.' '#' '.' '#' '.' '#' '#']
 ['#' '.' '.' '.' '.' '.' '.' '.' '.' '.' '.' '#']
 ['#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#' '#']]

上のような配列が出力されるはずです｡

step4で使った解法を用いるとほぼコピペでいけます｡ 単体でこの問題が出題されたら端の処理で無駄な労力を使いがちだと思います｡ アルゴリズムがよくないと思ったときは妥協してはいけないなと改めて思いました(両端の処理をifで行ったり､ Numpyを用いずに解いてたら最後の問題はかなり冗長なコードになってたと思います｡ )更に複雑な問題だと'#'を1､ '.'を0に置き換える等も考えれます(接してるマスの和で評価したりするときに強い､ また処理速度も当然速くなる)｡

※全ての端での分岐処理の必要な問題でこの手法が最適なわけではないです｡ 配列が都度都度変化するもの等の場合あらたにオブジェクトを生成してることになるので処理は遅くなります｡

終わりに

難易度Bの中では標準レベルの難しさだと思いますが､ このように考え方を分割すれば難易度C適正の方でも解けると思いました｡ 実戦ではこのような丁寧な誘導がないことが多いのでこのような問題の分割の仕方を考えるのも大事だとわかります｡ 時間があるときに残りの問題も解いていきたいと思いました｡

あとNumpyはほんと便利なので(Pythonの標準ツールと思っていいレベルで)どんどん使いましょう(各種競技プログラミングでも使えるみたいです)｡ 型さえ気を付ければ速くて多機能で幸せになれます!

• NumPyの行列演算入門
  ←基本的なNumpyでの操作がまとまっています