累積和に関して。下記問題にかなり詰まったのでメモ
atcoder.jp
累積和というアルゴリズムに関して
- 前処理として、に対象範囲数字の累計和を求めておくarrayを用意しておく(要素は+1となる)
- 求めたいレンジの
cumsum[index+1] - cumsum[i]
を行う
わからなかったこと
- 全探索以外の解き方がわからなかった
- 累積和を使うのか?となってもそれをどう使うのかわからなかった
考え方
まずこんな感じでリーダーはループ一回ずつ変わるとする
右端まで探索した際、Wを見ている人とEを見ている人、それぞれの累積和を求める
あとは下記のようなロジックを考える
サンプル
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); } }