POH Lite4 エンジニアでも恋がしたい-転職初日にぶつかった女の子が同僚だった件 ミッション3

ミッション1 / ミッション2 / ミッション3 / 共通解

<?php
    $input = file('php://stdin', FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);

    $una = array_shift($input);
    $una = explode(' ', $una);
    $max = 0;

    for($i=0; $i<$una[1]; $i++){
        $tmp =  array_sum(array_slice($input, $i, $una[0]));
        if($tmp > $max){
            $max = $tmp;
        }
    }
    print($max);

問題文にある解き方をそのままなぞっただけです。
とっても簡単。

https://paiza.jp/poh/enkoi-ending/e9dcd311
なん…だと！？
単純にやり過ぎたようだ。
答えは合ってるはずだが、効率が悪すぎてタイムオーバーになってしまいました。
もう少し効率の良い方法を考えてみましょう。

<?php
    $input = file('php://stdin', FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);

    $una = array_shift($input);
    $una = explode(' ', $una);
    $now =  array_sum(array_slice($input, 0, $una[0]));
    $max = $now;

    for($i=$una[0]; $i<$una[1]; $i++){
        $now = $now + $input[$i] - $input[$i-$una[0]];
        if($now > $max){
            $max = $now;
        }
    }
    print($max);

https://paiza.jp/poh/enkoi-ending/5d116982
見事にハワイでハネムーンをゲットしました。

動作をサンプルで解説します。
まず左端の4+5+1=10点を前提として計算、MAXも10点と仮置きし、ここをスタート地点とする。
次に右隣の10点をプラス、左端の4点をマイナスすると、これが次の5+1+10=16点となる。
現在のMAX10点を超えているので最大値を更新。
次に右隣の3点をプラス、左端の5点をマイナスすると、これが次の1+10+3=14点となる。
現在のMAX16点以下なのでそのまま。
これを右端に移動するまで繰り返す。

最初のやつに比べて計算量が激減し、全テストケースを時間内に解くことができました。
というわけで、今回は最後まで簡単でした。

しかし正直、このゲーム絶対つまらないだろ。