エンジニアでも恋がしたい!のミッション3

マンガ版「エンジニアでも恋がしたい!」〜転職初日にぶつかった女の子が同僚だった件〜|paizaオンラインハッカソン4 Lite

これのミッション3が100点にならなくて箱根にしか行けなかったあなたへ。(僕もです)

poh_mission3

要素数 n の中の、与えられた幅 t での各区間の最大値を求めよ、という問題。
まぁ大体の人が普通にやるとこうなると思う。

using System;
public class Hello
{
    public static void Main()
    {
        int t,n;
        string[] temp = Console.ReadLine().Split(' ');
        t = Int32.Parse(temp[0]);
        n = Int32.Parse(temp[1]);

        int[] values = new int[n];

        for( int i=0; i < n; ++i ){
            values[i] = Int32.Parse(Console.ReadLine());
        }

        int max = 0;
        int sum;

        for( int i=0; i < (n - t + 1); ++i )
        {
            sum = 0;

            for( int j=0; j < t; ++j ){
                sum += values[i+j];
            }

            max = Math.Max(max, sum);
        }

        Console.WriteLine(max);
    }
}

 
しかしこれだとテストケース4でタイムオーバーとなり、
60点どまりで結婚は出来るがハワイには行けず箱根で新婚旅行になる。

poh_mission3_2

これを100点にするにあたって、paizaのサイトで
「累積和、しゃくとり法でググってみよう」
とヒントが出ていたのでちょっと色々探してみたわけですよ。

解説するのがちょいめんどくさいので、100点になったコードを載せます。
分かれば「あ、そういうことなの」っていうホント単純なものです。
ソース読むと多分すぐに分かります。

using System;
public class Hello
{
    public static void Main()
    {
        int t,n;
        string[] temp = Console.ReadLine().Split(' ');
        t = Int32.Parse(temp[0]);
        n = Int32.Parse(temp[1]);

        int[] values = new int[n];
        for( int i=0; i < n; ++i ){
            values[i] = Int32.Parse(Console.ReadLine());
        }

        // 計算(初回)
        int max = 0;
        int tmp_max = 0;
        for( int i=0; i < t; ++i ){
            max += values[i];
        }
        tmp_max = max;
        int count = t;

        // 計算(しゃくとりの本体)
        while( count < n )
        {
            tmp_max += (values[count] - values[count - t]);
            max = Math.Max(max, tmp_max);
            count++;
        }

        Console.WriteLine(max);
    }
}

 
はい、これだけです。

要は、最初に1回計算しておいて、次に計算する区間との差分を考えるだけで
計算量が減らせるよねっていう事です。

初回計算:4 + 5 + 1
2回目計算:5 + 1 + 10

初回と2回目では5と1が同じ数字なので、2回目の計算の際は10が入ってきて4がいなくなるのです。
つまり初回の計算に10を足して、4を引くだけで2回目の計算は終わっちゃうのです。

これは幅tが長いほど有効な方法になります。
どれだけ幅が長くても、左端と右端の差分を前回の計算に足し込むだけなので。

これで提出してみると、テストケース4と5が通って晴れてハワイ旅行に行けました。
https://paiza.jp/poh/enkoi-ending/fdf5cf7a

 

このしゃくとり(尺取)法というのは、他にも応用の利く考え方のようなので
頭の片隅に置いておいて使える時には使いましょうって感じですね。

こういう計算量の話は、入りだすと本業忘れそうなので趣味にしておくのが吉かな…

  • このエントリーをはてなブックマークに追加