畑を掘る

プログラマー-縄張りを奪う

問題の説明

奪い合いゲームをする縄張りゲームの縄張り(land)は全部でN行4列で構成されており、各格子に点数が書かれている.1行目から地面を踏んで1行ずつ降りると、1行の4コマのうち1コマしか踏まない.しかし、奪い合いゲームでは、行ごとに同じ列を連続的に踏むことができないという特殊なルールがあります.
たとえば、
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
道が指定されている場合、1行目で4番目の格子(5)を踏むと、2行目の4番目の格子(8)を踏むことができません.
最後の行が下がるまで、解関数を完了し、得られるスコアの最大値を返します.上の例では、1行目の4番目の格(5)、2行目の3番目の格(7)、3行目の1番目の格(4)、地面を踏んで16分が最高点になるので、16に戻ればよい.

せいげんじょうけん

行の個数N:10000以下の自然数

列の数は4つで、土地は2次元に並んでいます.

点:100以下自然数

I/O例

landanswer [[1,2,3,5],[5,6,7,8],[4,3,2,1]] 16

に近づく

最初はグリディだと思っていました.最初に一番点数の高い格子を選び、その後下がることができる格子の中から一番点数の高い格子を選ぶと、正解が得られます.
しかし,この方法の特徴は,点数が同じであれば次の行を考慮することである.同じ点数が複数ある場合は、次の行を考えることができるので、どれが一番いいかを考えなければなりません.

ナレーション

[プログラマー]縄張りを奪う/パイソン-TEAM EDA
上の解説を見て、私のやり方は完全に間違っているわけではありません.
他人の解答を見れば見るほど、自分の頭が硬くなったのではないかと思います.どうやってそんなに接近方法を見つけることができますか.この方法が思いつかず、どうしようも考えられず・・・

そうやって作られた草

def solution(land):
    row = len(land)

    for i in range(1, row):
        land[i][0] += max(land[i - 1][1:])
        land[i][1] += max(land[i - 1][0], land[i - 1][2], land[i - 1][3])
        land[i][2] += max(land[i - 1][0], land[i - 1][1], land[i - 1][3])
        land[i][3] += max(land[i - 1][:3])

    return max(land[-1])

前の行の列以外の最大値を行のすべての要素に追加します.これにより,ローダウンによりスコアを得る機能が実現される.
これにより、出発地ごとに得られる最適点数が記録される.ここで最大の値を返すと,問題が求める答えを求めることができる.

他人の解答

def solution(land):

    for i in range(1, len(land)):
        for j in range(len(land[0])):
            land[i][j] = max(land[i -1][: j] + land[i - 1][j + 1:]) + land[i][j]

    return max(land[-1])

問題では,1行あたりの要素数は4個と断定されているので,上記のように実現できる.
これはダブルforゲートで、上記のように実現できます.