' P '

whatever I will forget

累積和

累積和に関して。下記問題にかなり詰まったのでメモ
atcoder.jp

累積和というアルゴリズムに関して

f:id:mankozooyork:20200614022054p:plain

  • 前処理として、に対象範囲数字の累計和を求めておくarrayを用意しておく(要素は+1となる)
  • 求めたいレンジのcumsum[index+1] - cumsum[i]を行う

qiita.com

わからなかったこと

  • 全探索以外の解き方がわからなかった
  • 累積和を使うのか?となってもそれをどう使うのかわからなかった

考え方

まずこんな感じでリーダーはループ一回ずつ変わるとする
f:id:mankozooyork:20200603090459p:plain

右端まで探索した際、Wを見ている人とEを見ている人、それぞれの累積和を求める
f:id:mankozooyork:20200603090556p:plain

あとは下記のようなロジックを考える
f:id:mankozooyork:20200603090624p:plain

サンプル

import java.util.Scanner;

public class Main104 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        char[] s = sc.nextLine().toCharArray();
        sc.close();

        int[] wCnt = new int[n];
        int[] eCnt = new int[n];
        for(int i=0; i<n; i++) {
            if(s[i] == 'W') {
                wCnt[i]++;
            } else {
                eCnt[i]++;
            }
            if(i != 0) {
                wCnt[i] += wCnt[i-1];
                eCnt[i] += eCnt[i-1];
            }
        }

        int ans = 0;
        for(int i=0; i<n; i++) {
            if(i == 0) {
                ans = eCnt[n-1] - eCnt[0];
            } else if(i == n-1) {
                ans = Math.min(ans, wCnt[n-2]);
            } else {
                ans = Math.min(ans, wCnt[i-1] + (eCnt[n-1] - eCnt[i]));
            }
        }
        System.out.println(ans);
    }
}

さらに深いところ、いもす法

freestylewiki.xyz

satanic0258.hatenablog.com

imoz.jp