あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

トップ > 競プロ > square869120Contest #6 C Infinite Grid ※嘘解法/バグありAC (Go)

square869120Contest #6 C Infinite Grid ※嘘解法/バグありAC (Go)

競プロ AtCoder square869120Contest #6 400点 Go

irisruneです。400点問題は解けましたが記事執筆中にバグに気付きました、最後に書くので考えてみてください。

atcoder.jp

10^9個ではなく数百個くらいでも変わらないかな？とは思っていましたが、それを解法に結び付けるには至りませんでした。結構強引に解こうとしたのでコードは長いです。

package main

import (
    "fmt"
)

func searchRoute(board []string, boardRoute [][][]bool, h int, w int) {
    for i := h - 1; i >= 0; i-- {
        for j := w - 1; j >= 0; j-- {
            if j == w-1 {
                for k := 0; k < h; k++ {
                    if k > i {
                        boardRoute[i][j][k] = ([]rune(board[i])[j] == '.') && boardRoute[i+1][j][k]
                    } else if k == i {
                        boardRoute[i][j][k] = ([]rune(board[i])[j] == '.')
                    } else {
                        boardRoute[i][j][k] = false
                    }
                }
            } else {
                if i == h-1 {
                    for k := 0; k < h; k++ {
                        boardRoute[i][j][k] = (boardRoute[i][j+1][k] && ([]rune(board[i])[j] == '.'))
                    }
                } else {
                    for k := 0; k < h; k++ {
                        boardRoute[i][j][k] = ((boardRoute[i+1][j][k] || boardRoute[i][j+1][k]) && ([]rune(board[i])[j] == '.'))
                    }
                }
            }
        }
    }
}

func checkToGoal(boardRoute [][][]bool, h int) bool {
    for i := 0; i < h-1; {
        iNext := i
        for j := h - 1; j > i; j-- {
            if boardRoute[i][0][j] {
                iNext = j
                break
            }
        }
        if iNext == i {
            return false
        }
        i = iNext
    }
    return true
}

func checkRoop(boardRoute [][][]bool) bool {
    for i, lineRoute := range boardRoute {
        if lineRoute[0][i] {
            return true
        }
    }
    return false
}

func main() {
    var h, w int
    fmt.Scan(&h, &w)

    board := make([]string, h)
    for i := range board {
        fmt.Scan(&board[i])
    }

    boardRoute := make([][][]bool, h)
    for i := range boardRoute {
        lineRoute := make([][]bool, w)
        for j := range lineRoute {
            route := make([]bool, h)
            lineRoute[j] = route
        }
        boardRoute[i] = lineRoute
    }

    searchRoute(board, boardRoute, h, w)
    if checkToGoal(boardRoute, h) && checkRoop(boardRoute) {
        fmt.Println("Yay!")
    } else {
        fmt.Println(":(")
    }
}

解き方の方針は、

  1. 元のボードの各マスから右端のマスそれぞれに到達可能かを動的に求める。
  2. 左上のマスから右下のマスまでボードを繋げた時に（左端→右端→左端→右端…と辿って）有限回で到達可能か検査する。
  3. いずれかの行で同じ行の左端から右端へ到達可能かを検査する。
  4. 2.と3.を両方満たすならば条件を満たすと判定する。

という形です。一番複雑になったのは1.で、3重ループを回している上にボードの下端や右端での処理が個別になされています。

2.と3.を満たせば条件を満たすことの証明をしてみます、まず2.自体が必要条件になっていることは明らかだと思います。 ただし検査方法がやや強引で、

  1. 左上から到達できる右端マスで一番下のものを探す。
  2. 到達した右端マスと同じ行の左端マスからも同様に到達できる右端マスで一番下のものを探す。
  3. 最終的に右下に到達したらtrueを返す。

という形になっています。この検査を行うために3次元配列を作ったり色々面倒なことをしていると言ってもいいです。

次に3.ですが、条件になっている[10^9]回（実質的に無限回）で右下に到達できることと、有限回で右下に到達できることはイコールではありません。 問題ページの入力例4がまさにそれで、1枚のボード内では右下に到達することができますが2枚目のボードの右端に到達することすらできません。

ボードが非常に多くの枚数繋がっている条件下では、どこかの行で右にのみ移動して左端から右端に到達できる必要があります。この場合、有限回で右下に到達できるならボードの枚数がどれほど多くても同様に右下に到達することができます。

コードレビュー

  • 3重ループにif文が組み合わさってネストが非常に深い。
  • ルート構築処理における代入文が長くわかりにくい。

雑記

  • 今回は文字列から（部分文字列ではなく）文字を取り出す手法を導入しました。覚えることがまだまだありますね。

  • D問題は自力70点の解説460点でした。あと少しだったんですけどね。

バグについて

実はこのテストケースが右下に到達できないという判定になります。

6 5
....
###.
..#.
#.#.
#.##
#...

原因についてですが、右端の到達できるマスのうち一番下のマスについてしか次のステップで見ていないためです。 むしろこれでよくACできましたね