HackerRank Week of Code 35 参加日記

1044位/9458人の酷い結果。以下、易問は省略。

3D Surface Area

HxWの平面上の各セル上に、立方体がいくつか積み重なっている。外部に面している面積を求めよ。

X面からみた面積、Y面からみた面積、Z面からみた面積をそれぞれ求めて足せば良い。
https://www.hackerrank.com/contests/w35/challenges/3d-surface-area/submissions/code/1304126485

Matrix Land

n行m列のマトリックスがあり、各セルには点数が設定されている。1行目の任意のセルから、n行目の任意のセルまで移動したとき、得られる合計得点の最大値を求めよ。ただし、セルの点数は通過後にゼロになる。また、セルからの移動は左右と下のみ可能である。
1 <= n x m <= 4 * 10^6

3日考えて解けなかったDPの問題。これは悔しい。
移動制約により、ある点に到着するルートは2通りしかない。

パターン１：ある点より左いずれかに降りてきて、点を通過して右から戻ってくる（通過しない場合も含む）
パターン２：ある点より右いずれかに降りてきて、点を通過して左から戻ってくる（通過しない場合も含む）
パターン１だけ考えてみる。

上の矢印で表されるのは、「その行だけを考えたときの、(x, y)より右の合計最大値」であり、
msr[x, y] = Max(msr[x, y + 1] + A[x, y], 0)
と表すことができる。

上の矢印で表される部分をmslit[x, y]と定義すると
mslit[x, y] = Max(mslit[x, y-1] + A[x, y], dp[x - 1, y] + A[x, y] + msr[x, y + 1])
と表すことができる（dp[x,y]は点(x,y)に来るルートの最大点）。
この合計値を求めて、最大のものを解答すればよい。パターン２も同様。