思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

AtCoder Beginner Contest 129 D - Lamp

目次

結論

  • 次の状態が直前の状態に依存していると判断したら,動的計画法を解法の候補に入れる.

はじめに

  • AtCoderで出題された問題を復習しています.

  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います.

想定読者

  • 解説を読んで解き方はわかったものの,なぜその方法を思いつけるのか?と思った方.

筆者の実力

  • AtCoderのレートで緑下位

記事の特徴

  • なぜその発想に至ったのか,どうしたら解法を詰められるかといった点について,筆者なりの解釈をつづります.

  • 試行錯誤した過程から,得られた前提知識や着眼点を言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

D - Lamp (400点)

発想・解法とそれらを引きだすための方法・解釈

  • 最初の一歩は?

    • 愚直な解法を書き出す.

    • 同じような計算をしている部分を見つける.

  • 考察のキモ(Key Insight)は?

    • あるマスに着目したときに,あらかじめ上下左右にそれぞれ移動できるマスを数えておく.

    • グリッドを全探索して,移動できるマスを計算する.

    • 移動できるマスの数は,上下左右に移動できるマスの合計から重複を除いた数.

  • どうしたら思いつけそうか?

    • 図を書いてみる.

    • 縦方向と横方向を分けてみる.

    • 高得点問題では,愚直な解法が間に合うことが少ない.前処理を行うことで計算量が減らせるケースがある.

  • 実装のポイントは?

    • 移動できるマスの数:

      • 上下左右それぞれに移動できるマスの数を1で初期化.

      • 連続して移動できる場合は直前のマスから1増やす.

      • 移動できない場合は0.

      • 数えるときは,移動方向に対して反対側からループを回す.例えば,上に移動できるマスを数えるときは,グリッドの下側から数える.

    • 配列の参照外エラーを回避するため,配列の両端に要素を追加して n + 2個にする,もしくは,if文で参照外の領域を弾く.

PyPy3による回答例

# -*- coding: utf-8 -*-


def main():
    h, w = map(int, input().split())
    grids = [list(input()) for _ in range(h)]
    up = [[1 for __ in range(w)] for _ in range(h)]
    down = [[1 for __ in range(w)] for _ in range(h)]
    left = [[1 for __ in range(w)] for _ in range(h)]
    right = [[1 for __ in range(w)] for _ in range(h)]
    ans = 0

    # 上に移動できるマスの数
    for i in range(h - 1, -1, -1):
        for j in range(w):
            if (grids[i][j] == '.') and (i < h - 1):
                up[i][j] = up[i + 1][j] + 1
            elif grids[i][j] == '#':
                up[i][j] = 0

    # 下に移動できるマスの数
    for i in range(h):
        for j in range(w):
            if (grids[i][j] == '.') and (i > 0):
                down[i][j] = down[i - 1][j] + 1
            elif grids[i][j] == '#':
                down[i][j] = 0

    # 左に移動できるマスの数
    for i in range(h):
        for j in range(w - 1, -1, -1):
            if (grids[i][j] == '.') and (j < w - 1):
                left[i][j] = left[i][j + 1] + 1
            elif grids[i][j] == '#':
                left[i][j] = 0

    # 右に移動できるマスの数
    for i in range(h):
        for j in range(w):
            if (grids[i][j] == '.') and (j > 0):
                right[i][j] = right[i][j - 1] + 1
            elif grids[i][j] == '#':
                right[i][j] = 0

    # あるマス(i, j)に着目したときに,上下左右に移動できるマスの数を計算
    for i in range(h):
        for j in range(w):
            # 重複しているマスを除外
            ans = max(ans, (up[i][j] + down[i][j] - 1) + (left[i][j] + right[i][j] - 1) - 1)

    print(ans)


if __name__ == '__main__':
    main()

得られた知識・知見

  • 縦方向・横方向を分けて考える.

  • PyPy3の場合,ループで軽い処理をしているだけなら,計算量が 10^{7}オーダーでもTLEにならないケースがある.

感想

  • 実行制限時間ギリギリとはいえ,この実装でTLEしなかったことに驚きです.

  • Pythonのライブラリnumpyを使う解法や縦方向・横方向をまとめて処理するなど,キレイな解法を見て感動しました.自分で書けるよう精進します.

  • 前処理は,ABC018 C - 菱型カウントの考え方がとても参考になったと思っています.

  • コンテスト中ではないものの,自力でACできた点については,少しずつでも成長していると実感しています.

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.

更新履歴

  • 2019/06/14 作成
  • 2019/0x/xx 更新