Mujin Programming Challenge 2018 C-右折
C - 右折
コンテスト参加してないけど色々と勉強になった＆個人的に好きな問題
なのでできるだけ丁寧に解説してみる

問題概要

N*Mマスの障害物があるマップが与えられる．
あるマスから障害物に当たらずに1マス以上進み，右折して1マス以上進むルートは全体で何パターン考えられるか

制約

$\displaystyle 2≤N,M≤2×10^3$

考えたこと

スタート地点を決めてそこからいけるルートを数える全探索は流石に間に合わなさそう
この手のA->B->CのルートというのはBから見るのがやりやすい
ので，右折する場所を固定して上下左右何マス進めるかカウントしていく
何マス進めるかはメモ化して高速に行うことでO(NM)で計算できる
(この前のD - We Love ABCも真ん中に着目するという点では似た問題かも？(想定解法DPだったけど))

実装

この手のマップでルート探索系の時の下準備

こういうマップが与えられてルートを探すのはわりとよくあるが
最初に周囲を壁で囲ってしまえば全て=='#'で判定できるので(個人的に)楽
壁判定ミスって数時間詰まったトラウマからそうするようになった

入力例1を例に白が移動可能，灰色が壁とすると f:id:awaawa4423:20180807213812p:plain:w600
左が入力，右が実際に扱う二次元配列(mapとしてる)の中に入るもの
範囲が(0,0)～(N-1,M-1)から，(1,1)～(N,M)に代わるのでその点は注意

何マス進めるかというカウントについて

本問題の入力例1を例にとって考えてみる

上方向に何マス進めるか
まずup=[N][M]という配列を作り全部-1で初期化

左上から順に探索してそのマスに障害物がなければ以下のように更新していく

$up[y][x] = up[y-1][x]+1$

(あるマス(x,y)の一つ上のマス(y-1,x)が上にkマス進めるなら，そのマスは上にk+1マス進める
これに加え障害物のマスを-1としておけばその真下が0となる)
f:id:awaawa4423:20180807214644p:plain:w200 f:id:awaawa4423:20180807215221p:plain:w200
するとup[y][x]がその点から上方向に何マス進めるかを示す．
左方向に何マス進めるかというのも同様に求まる．

が，下・右方向については下・右から更新していかなければならない．
そのため上でやった左上から辿るのとは真逆の順に辿って右下からも更新していく．

#左上から順に更新
for y in range(1,N+1):
    for x in range(1,M+1):
        if map[y][x] == '.':
            up[y][x] = up[y-1][x]+1
            left[y][x] = left[y][x-1]+1

#右下から順に更新
for y in reversed(range(1,N+1)):
    for x in reversed(range(1,M+1)):
        if map[y][x] == '.':
            down[y][x] = down[y+1][x]+1
            right[y][x] = right[y][x+1]+1

答え

結局何が求めたかったかという話
右折するルートが何パターンあるかという話だったので，
あるマスから上，下，左，右方向にそれぞれU，D，L，Rマス進めるとするとそのマスを右折位置としたルートは U*R + R*D + D*L + L*Uパターンあるので各マスについてこれを足し合わせるだけ

自分のコード
Submission #2968359 - Mujin Programming Challenge 2018

実行時間について

f:id:awaawa4423:20180807221414p:plain
＿人人人＿
＞　TLE　＜
￣Y^Y^Y^￣
まあN,M<=2 * 10³でO(NM)になるので…Pythonだと10⁶オーダーで2secは結構怪しい部類
参考qiita.com

今回の処理は結構簡単な部類なのでPyPyでやってみるとなんとか通る(それでもC++よりは全然遅いが)
f:id:awaawa4423:20180807223536p:plain

感想

こういうmapでルート探索するの好きなんじゃ(得意とは言ってない)
ちゃんと考察して詰めるとコードもすっきりして綺麗になる感じなのも好き
実行時間についてはまあ，わかったうえでPython使ってるから仕方ないねって感じ
Pythonで解いてTLE吐いたらC++で書き直すっていうムーブも選択肢としてできるようになりたい
~~(今回のはN,M <= 10³でもよかったんじゃない？と思った)~~

あとMarkdownでちゃんと数式入れるの難しい…難しくない