paiza開発日誌

IT/Webエンジニア向け総合求人・学習サービス「paiza」(https://paiza.jp ギノ株式会社)の開発者が開発の事、プログラミングネタ、ITエンジニアの転職などについて書いています。

【累積和、しゃくとり法】初級者でも解るアルゴリズム図解

f:id:paiza:20150120113516j:plain
2014年12月3日より2015年1月7日まで開催した、paizaオンラインハッカソンVol.4Lite「エンジニアでも恋したい」は、トータルで3問有りましたが全て解けましたでしょうか? 各問題の成否によりストーリーが変わるのであえて間違えて解いた方もいらっしゃると思いますがw (プレゼント対象期間は終了しましたが、問題チャレンジは可能なので、未チャレンジの方は是非チャレンジください!)

問題1、問題2は解説するほどのむずかしさでもないので省きますが、問題3は多少工夫が必要なので、問題3について今回もPOH恒例の「図解解説」をしてみたいと思います。既に解けた方もそうでない方も、今回の解説を読んで、それぞれの方法すべてを実装してみると勉強になると思いますので、是非試してみてください。

■どのような高速化ステップがあるのか?

今回の問題ですが、解法の大きなパターンとしては、1.全てのパターンを調べて最も大きい数字を探す「全探索」、2.前処理をして計算回数を減らす「累積和」、3.加算と減算を繰り返して区間の総数を求める「しゃくとり法」の3パターンになるかと思います。

◆実行速度順位

  1. しゃくとり法
  2. 累積和(しゃくとり法と殆ど差はないと思われます)
  3. 全探索

全探索と、累積和としゃくとり法での差は明確ですが、累積和としゃくとり法は余り差がありません。どちらのやり方でも100点が取得可能です。

■問題文の再確認

まずは問題文の確認をしてみましょう。


あなたは野田さんに好かれたい一心でパズルRPGゲーム 「パズル&ウナギーズ」 (パズウナ)を開発することにしたました。
パズウナの画面上にはコマが一列に並んでおり、それぞれのコマには点数が表示されています。
そこへ敵のウナギが現れると、区間の長さが指定されます。
プレイヤーは一列に並んでいるコマから、指定された区間の長さで区間の中に含まれるコマの合計点数が最大だと思う区間を考え、区間を指定します。
この指定した区間のコマの合計点数を、敵ウナギにダメージとして与えることが出来ます。


この時、合計点数の値が指定できる各区間の中で最大だった場合、敵ウナギにクリティカルヒットを与えることが出来ます。
f:id:paiza:20150120112145p:plain
あなたはゲームアプリ自体の実装は終わりましたが、一列に並んでいるコマの点数の中で決められた長さの区間で最大の点数になる答えを用意するのを忘れていました。
これではクリティカルヒットの判定出来ません。
1行目に区間の長さ t と コマの総数 n がスペース区切り
2行目以降に n 個のコマの点数 m_i が改行区切りで与えられます。
区間合計点数の最大値(クリティカルヒットが出る区間の合計点数)を出力するプログラムを作成してください。


例えば
3 7 #区間の長さ, コマの個数
4 #1個目のコマの点数
5 #2個目のコマの点数
1 #3個目のコマの点数
10 #4個目のコマの点数
3 #5個目のコマの点数
4 #6個目のコマの点数
1 #7個目のコマの点数


のような入力が与えらた場合、下図に示したようにコマが並び、区間の長さ t = 3 となります。
このとき、4番目から6番目の数字までの区間が最大になり17点を獲得できることになります。

paizaオンラインハッカソンVol.4Lite「エンジニアでも恋したい」


■全探索による解法

「全探索」は全てのパターンを調べて最も大きい数字を探す方法です。この解法だと60点しか取得が出来ません。

◆全探索の処理手順

  1. 与えられた全コマに対してループ
    1. 指定区間の合計値算出
    2. 区間の合計値を合計値配列に格納
  2. 合計値配列の最大値を出力

左から各マスの番号をi_1,i_2,i_3……i_7と置きます(以下全ての説明で各マスの番号をこのように表す)

3つの区間合計を出す場合で考えてみます。

i_1からi_3の区間に関しての合計を計算する処理の場合、i_1+i_2+i_3となり4+5+1で10点ということになります。
同じように右に一つずらした区間をi_2からi_4の区間を見るとi_2+i_3+i_4となります。

以下図のような手順で各点数を求めて最も大きい数字を探します。

f:id:paiza:20150120112145p:plain

この際に必要な計算回数は、図の7マスの区間の広さ3の場合、
( 7(マス)-3(区間)+1 ) * 3(各区間で必要な計算回数 3つのマスへの配列アクセス) = 15回
という計算が必要となります。

一般化するとt 区間の広さ、n マスの総数 とする時 ( n - t + 1) * t となります。

問題中の条件のが以下になり
1 ≦ t ≦ n ≦ 300,000
問題中の条件のが以下になりここから、問題の条件中で最も計算回数が悪くなる数字は t = 150,000、n = 300,000となります。この際の計算回数は式に当てはめると 22,500,150,000回(225億飛んで15万回)となります。

◆全探索コード(Ruby

strs = gets.split(' ')
t, n = strs[0].to_i, strs[1].to_i
m = Array.new(n)
n.times {|i|
    m[i] = gets.to_i
}

ans = 0
(n-t+1).times{|i|
    tmp = m.slice(i,t).inject(:+)
    if ans < tmp
       ans = tmp
    end
}

puts ans

◆全探索コード(PHP

<?php
fscanf(STDIN, "%d %d", $t, $n);
$m = array();
for($i = 0; $i < $n; $i++){
    fscanf(STDIN, "%d", $m[$i]);
}

$ans = 0;
for($i = 0; $i < $n-$t+1; $i++){
    $tmp = array_sum(array_slice($m, $i, $t));
    if($ans < $tmp)
        $ans = $tmp;
}
echo $ans;

※単純なコードなのでRubyPHPのみです、あしからず。。

■累積和による解法

累積和による解法は、前処理をして、計算回数を減らす手法です。このやり方であれば100点が取得可能です。

◆累積和の処理手順

  1. 与えられた全コマに対してループ
    1. 累積和表配列に累積和を格納
    2. 累積和表配列を使って区間合計を算出、合計値配列に格納
  2. 合計値配列の最大値を出力

まず元のデータから、累積和の表を作ります。i_n番目までの合計値を求めた表です。

f:id:paiza:20150120112157p:plain

まず初期値0のデータの先頭につけて考えると実装しやすくなります。
0+4を行い累積は表の2番目に追加します。
4+5とは累積和表の2番目+元データの2番目となります。累積和表の3番目に追加します。
9+1とは累積和表の3番目+元データの3番目となります。累積和表4番目に追加します。

このようにすることにより、7回の加算処理により累積和表が完成します。
一般化すると n 回の計算で表が完成します。

この累積和表は、各地点での1番目からの合計値となるので「知りたい区間の末尾」知りたい区間の先頭の一つ手前」を行うと求める事が出来ます。この時行われる計算回数が
t = 3, n = 7とした時、( 7 - 3 + 1) * 2(始点-終点を行うために必要な配列へのアクセス回数)となります。

一般化すると
( n - t + 1 ) * 2

となります。
ここでは前処理を含んだ計算回数を求めるので累積和表の作成の為の計算回数 n を加えて
n + ( n - t + 1 ) * 2
が計算回数となります。
入力例では 7 + (7 - 3 + 1)*2 となり17回の計算で結果が求まります。この計算回数は先に書いた全探索よりも回数が多くなっていますが、例えば t = 150,000、n = 300,000を当てはめると600,002回の計算で済む事になります。

◆累積和コード(Ruby

strs = gets.split(' ')
t, n = strs[0].to_i, strs[1].to_i
m = Array.new(n)
m_t = Array.new(n+1)
n.times {|i|
    m[i] = gets.to_i
}

m_t[0] = 0
n.times {|i|
    m_t[i+1] = m[i]+m_t[i]
}

ans = m_t[t] - m_t[0]
(n-t).times{|i|
    tmp = m_t[i+1+t] - m_t[i+1]
    if ans < tmp
       ans = tmp
    end
}

puts ans

◆累積和コード(Java

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    int n = sc.nextInt();
    int[] m = new int[n];
    int[] m_t = new int[n+1];

    for (int i=0; i<n; i++)
      m[i] = sc.nextInt();

    for (int i=0; i<n; i++)
        m_t[i+1] = m[i] + m_t[i];

    int ans = m_t[t] - m_t[0];
    int tmp = 0;
    for (int i=0; i < n-t; i++) {
        tmp = m_t[i+1+t] - m_t[i+1];
        if (ans < tmp)
            ans = tmp;
    }

    System.out.println(ans);
  }
}

◆累積和コード(PHP

<?php
fscanf(STDIN, "%d %d", $t, $n);
$m = array();
$m_t = array();
for($i = 0; $i < $n; $i++){
    fscanf(STDIN, "%d", $m[$i]);
}

for($i = 0; $i < $n; $i++){
    $m_t[$i+1] = $m[$i] + $m_t[$i];
}

$ans = $m_t[$t] - $m_t[0];
for($i = 0; $i < $n-$t; $i++){
    $tmp = $m_t[$i+1+$t] - $m_t[$i+1];
    if($ans < $tmp)
        $ans = $tmp;
}

echo $ans;

◆累積和コード(Python

t, n = map(int, raw_input().split())
m = []
for i in xrange(n):
    m.append(input())
m_t = [0]

for i in xrange(n):
    m_t.append(m[i]+m_t[i])

ans = m_t[t] - m_t[0]
for i in xrange(n-t):
    tmp = m_t[i+1+t] - m_t[i+1]
    if ans < tmp:
        ans = tmp

print ans

◆累積和コード(Perl

@s = split(/ /,<STDIN>);
chomp($t = $s[0]);
chomp($n = $s[1]);
@m = ();
@m_t = ();
for($i = 0; $i < $n; $i++){
    chomp($tmp = <STDIN>);
    push @m, $tmp;
}

push @m_t, 0;
for($i = 0; $i < $n; $i++){
    push @m_t, $m[$i]+$m_t[$i];
}

$ans = $m_t[$t] - $m_t[0];
for($i = 0; $i < $n-$t; $i++){
    $tmp = $m_t[$i+1+$t] - $m_t[$i+1];
    if($ans < $tmp){
        $ans = $tmp;
    }
}

print $ans;

◆累積和コード(C)

#include <stdio.h>
#include <string.h>
#include <math.h>

int main(){
    int t, n, i, ans;
    int m[1000000];
    int m_t[1000001];
    int tmp = 0;

    scanf("%d %d", &t, &n);
    for(i = 0; i < n; i++){
        scanf("%d", &tmp);
        m[i] = tmp;
    }

    m_t[0] = 0;
    for(i = 0; i < n; i++){
        m_t[i+1] = m[i] + m_t[i];
    }

    ans = m_t[t] - m_t[0];
    for(i = 0; i < n-t; i++) {
        tmp = m_t[i+1+t] - m_t[i+1];
        if(ans < tmp){
            ans = tmp;
        }
    }

    printf("%d\n", ans);

    return 0;

}

◆累積和コード(C++

#include <iostream>
using namespace std;
int main() {
    int t, n; cin >> t >> n;
    int m[300000];
    int m_t[300001];

    for(int i = 0; i < n; i++) {
        cin >> m[i];
    }

    m_t[0] = 0;
    for(int i = 0; i < n; i++) {
        m_t[i+1] = m[i] + m_t[i];
    }

    int ans = m_t[t] - m_t[0];
    int tmp;
    for(int i = 0; i < n-t+1; i++) {
        tmp = m_t[i+1+t] - m_t[i+1];
        if(ans < tmp){
            ans = tmp;
        }
    }

    cout << ans << endl;
    return 0;
}

◆累積和コード(C#

using System;
public class ClassName {
    static void Main(){
        string[] str = Console.ReadLine().Split(' ');
        int t = int.Parse(str[0]);
        int n = int.Parse(str[1]);
        int[] m = new int[n];
        int[] m_t = new int[n+1];

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

        for(int i=0; i<n; i++){
            m_t[i+1] = m[i] + m_t[i];
        }

        int ans = m_t[t] - m_t[0];
        int tmp = 0;
        for(int i=0; i < n-t; i++){
            tmp = m_t[i+1+t] - m_t[i+1];
            if(ans < tmp)
                ans = tmp;
        }

        Console.WriteLine(ans);
    }
}

◆累積和コード(JavaScript

var input_lines = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
    input_lines += chunk;
});
process.stdin.on('end', function() {
    input_lines = input_lines.split('\n');

    tmp = input_lines[0].split(" ");
    t = parseInt(tmp[0])
    n = parseInt(tmp[1])

    m = []
    for(i=0; i<n; i++){
        m.push(parseInt(input_lines[1+i]));
    }

    m_t = [0];
    for(i=0; i<n; i++){
        m_t.push(m[i]+m_t[i]);
    }

    ans = m_t[t] - m_t[0];
    for(i=0; i<n-t; i++){
        tmp = m_t[i+1+t] - m_t[i+1];
        if(ans < tmp){
            ans = tmp;
        }
    }

    console.log(ans);
});

■しゃくとり法による解法

加算と減算を繰り返して区間の総数を求めることで、計算回数を減らす手法です。こちらのやり方でも100点が取得可能です。

◆しゃくとり法の処理手順

  1. 与えられた全コマに対してループ
    1. 最初の指定区間は通常の加算処理を行う。次の区間の先頭の一つ手前を減算、新たに加わる区間の末尾を加算し合計値配列に格納
    2. 区間合計を合計値配列に格納
  2. 合計値配列の最大値を出力

f:id:paiza:20150120132629p:plain

この方法はまず、最初の区間は普通に加算をし、次の区間の先頭の一つ手前を引き、新たに加わる区間の末尾を加算するという方法になります。このようにすることで全探索で行っていた t 回ループ(指定区間の長さ分のループ)を省く事が出来ます。そのため t (指定区間)の長さが長い場合ほど全探索よりも高速になります。

入力例から考えるとまず 3 区間の合計値の計算が行われ、次の区間からは1回の加算と1回の減算が行われて行きます。3 + (7 - 3) * 2回が計算回数となり11回の計算で結果が求まります。一般化すると
n + (n - t) * 2となり
t = 150,000、n = 300,000を当てはめると600000回の計算回数で済むことになります。

◆しゃくとり法コード(Ruby

strs = gets.split(' ')
t, n = strs[0].to_i, strs[1].to_i
m = Array.new(n)
n.times {|i|
    m[i] = gets.to_i
}

ans = m.slice(0,t).inject(:+)
tmp = ans
(n-t).times{|i|
    tmp += m[t+i]
    tmp -= m[i]
    if ans < tmp
       ans = tmp
    end
}

puts ans

しゃくとり法の各言語のコードについては、前回のPOH4結果発表ブログで掲載しておりますので、そちらをご確認ください。【結果発表】これで私は結婚できた!嫁を射止めたコード23選 - paiza開発日誌

■計算量についての考えてみる

「累積和」と「しゃくとり法」では、「全探索」との差は明確です。しかし今回問題の場合「累積和」と「しゃくとり法」については余り差がないので、どちらのやり方でもよいと言えます。強いて言うならば、「累積和」のやり方だと実装も若干累積和の方が複雑になりがちというのと「別の配列をもう一個用意する」というよな形になりがちなので、実装次第ではメモリが少し多めに必要かもしれません。

計算量の詳細は、
累積和の式
n + ( n - t + 1 ) * 2
整理すると
3n - 2t + 2

しゃくとり法の式
n + (n - t) * 2
整理すると
3n - 2t

となるので累積和の方が同じ入力値なら常に2回計算量が多いだけです。

◆累積和が有利になるとしたら

ただし、問題の質が変わった場合を仮定すると考え方も変わります。例えばi_4からi_6の区間の合計を求めよのような問題になった時、「しゃくとり法」の場合は特定の区間だけを求めることは出来ずに、その区間が現れるまでずらして行く作業が必ず行われてしまいます。

この場合、累積和での計算量は

n(累積和作成の計算) + 2(区間i_4の一つ前と区間i_6を引き算する処理)

n(1つ目の区間の計算) + (n - t - (t - 6)) * 2
1つ目の区間の計算 + i_4,i_6区間目までずらす回数 * 2

という計算になり
n = 7, t = 3の場合でいうと
累積和が
7 + 2
= 8

しゃくとり法が
7 + (7 - 3 - (7-6)) *2
7 + (3)*2
= 13

のようになりしゃくとり法が不利ということがわかります。

◆累積和が不利になる場合

累積和は、一回前処理として n 個の累積和を出します。その為、n=1000,t=100などの場合、最低でも1000回の計算が前処理でかかる事になります。その為、例えば二つの指定区間合計のみの計算をするような場合には( t * 2 で済んでしまう場合 )不利になります。

◆しゃくとり法が使えない場合

他にも、区間がi_2からi_4とi_1からi_5のように区間の広さが変化する場合はしゃくとり法が説明したアルゴリズムでは適応不可能になり、累積和、もしくは全探索の解法となります。


■まとめ

POH4の問題3は「全探索」だと60点、「累積和」か「しゃくとり法」だと満点が取れる内容でした。POHは元々アルゴリズムを意識し、学ぶきっかけになる事を目指しているイベントでもあるので、今回は60点だった場合にもヒントを出すなど、よりとっつきやすくしたつもりですが、いかがでしたでしょうか。paizaではこのほかにも色々な問題を用意しているのでご興味が有る方は覗いてみてください!

paizaオンラインハッカソンのレポートは今回で終了ですが、次回開催の準備も進めておりますので是非次回も皆様のご参加をお待ちしております!

■おまけ

最後まで読んでいただきありがとうございました。paiza会員登録すると、下記の野田ちゃん壁紙3種類がダウンロードできます!是非お気軽にご登録下さい!
f:id:paiza:20150114220025j:plain
f:id:paiza:20150114220105j:plain
f:id:paiza:20150114220120j:plain




paizaではスキルのあるエンジニアがきちんと評価されるようにし、技術を追い続ける事が仕事につながるようにする事で、日本のITエンジニアの地位向上を図っていければと考えています。特にpaizaではWebサービス提供企業などでもとめられる、システム開発力や、テストケースを想定できるかの力(テストコードを書く力)などが問われる問題を出題しています。

テストの結果によりS・A・B・C・D・Eの6段階でランクが分かります。自分のプログラミングスキルを客観的に知りたいという方は是非チャレンジしてみてください。

http://paiza.jp