Contents
対象読者
- AtCoder初級〜中級（ABC常連）
- アルゴリズムはまだ自信がないけど最短解を身につけたい人
- TypeScriptで競プロを書いている／書きたい人
問題概要
N 人が一直線に並び、各人は東（E）または西（W）を向いています。任意の 1 人をリーダーに選ぶと、リーダー以外の全員がリーダーの方向を向くように命じます。
向きを変える人数が最小になるようにリーダーを選んだとき、その最小人数を求めてください。
- 制約: 2 ≤ N ≤ 3×10^5、S は ‘E’ と ‘W’ からなる長さ N の文字列
- 入出力例:
入力 ：5 WEEWW
出力 ：1
3 番目（0-indexなら 2）の人をリーダーにすると、向きを変えるのは 1 人だけで最小です。
解き方の全体像
リーダーを位置 i に決めると、
- **左側（0..i-1）**の人たちはリーダーのいる右を向く＝Eを向く必要あり → もともと W の人が裏返る
- **右側（i+1..N-1）**の人たちは左（＝W）を向く必要あり → もともと E の人が裏返る
よって「コスト（裏返る人数）」はleft_W[i] + right_E[i]
で表せます。ここで
left_W[i]= 区間 [0, i-1] にある ‘W’ の個数right_E[i]= 区間 [i+1, N-1] にある ‘E’ の個数
これを **累積カウント（prefix/suffix）**で O(N) で作り、全 i の最小値をとれば OK。
ポイント
- 「累積和」というより「累積個数」を使う問題
- リーダー自身は裏返らない → 数えない（オフバイワン注意）
- 片側だけ数えれば反対側は全体から差し引けるため、O(1) メモリの片パス解も可能
累積カウントの設計
prefixW[i]= 位置 i の左側（0..i-1）の ‘W’ の個数- 実装は
prefixW[0] = 0から始め、prefixW[i] = prefixW[i-1] + (S[i-1]==='W'?1:0)
- 実装は
suffixE[i]= 位置 i の右側（i+1..N-1）の ‘E’ の個数- 実装は
suffixE[N-1] = 0から始め、suffixE[i] = suffixE[i+1] + (S[i+1]==='E'?1:0)
- 実装は
各 i のコストは prefixW[i] + suffixE[i]。最小を答えに。
実装例（TLE）
最初適当に実装したらTLEになりました・・・。
参考にのせておきます。
import * as fs from "fs";
// エントリポイント inputに入力データ全体が入る
function main(input: string): void {
const [nRaw, S] = input.trim().split(/\r?\n/);
const N = Number(nRaw);
let min = Infinity;
for(let i = 0; i<N; i++){
if(i === 0) {
let count = 0;
for(let j=1; j< S.length; j++){
if(S[j]==="E") count++;
}
min = Math.min(min, count)
} else {
let count = 0;
for(let j=0; j< i; j++){
if(S[j]==="W") count++;
}
for(let j=i+1; j< S.length; j++){
if(S[j]==="E") count++;
}
min = Math.min(min, count)
}
}
console.log(min);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
const inputData: string = fs.readFileSync("/dev/stdin", "utf8")
main(inputData);
実装例（TypeScript / Node.js）
// ABC098C - Attention（O(N), 累積カウント）
// 使い方: ts-node main.ts < input.txt
import * as fs from 'fs';
const lines = fs.readFileSync(0, 'utf8').trim().split('\n');
const N = Number(lines[0].trim());
const S = lines
.trim();
const prefixW = new Array<number>(N).fill(0); // left_W[i]
for (let i = 1; i < N; i++) {
prefixW[i] = prefixW[i - 1] + (S[i - 1] === 'W' ? 1 : 0);
}
const suffixE = new Array<number>(N).fill(0); // right_E[i]
for (let i = N - 2; i >= 0; i--) {
suffixE[i] = suffixE[i + 1] + (S[i + 1] === 'E' ? 1 : 0);
}
let ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < N; i++) {
const cost = prefixW[i] + suffixE[i];
if (cost < ans) ans = cost;
}
console.log(ans.toString());
例で手計算してみる（WEEWW）
prefixW= [0,1,1,1,2]（各 i の左側にある W の数）suffixE= [2,1,0,0,0]（各 i の右側にある E の数）cost(i)=- i=0: 0+2=2
- i=1: 1+1=2
- i=2: 1+0=1 ← 最小
- i=3: 1+0=1
- i=4: 2+0=2
答えは 1。
計算量とメモリ
- 時間計算量: O(N)
- 追加メモリ: O(N)（
prefixW/suffixEを使う場合） - O(1) メモリの片パスでも書けます（次章）
発展的な実装例（片パス・O(1) メモリ）
全体の E の個数 totalE を数えておき、左から走査。
位置 i のとき、
- 左側の W の個数 =
seenW - 右側の E の個数 =
totalE - seenE - (S[i]==='E' ? 1 : 0)seenEは「これまでに見た E の個数」（位置 i より左）。- (S[i]==='E'?1:0)は「リーダー自身は除外」。
import * as fs from 'fs';
const lines = fs.readFileSync(0, 'utf8').trim().split('\n');
const N = Number(lines[0].trim());
const S = lines.trim();
let totalE = 0;
for (const c of S) if (c === 'E') totalE++;
let seenW = 0;
let seenE = 0;
let ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < N; i++) {
const rightE = totalE - seenE - (S[i] === 'E' ? 1 : 0);
const cost = seenW + rightE;
if (cost < ans) ans = cost;
// update seen counters AFTER using them
if (S[i] === 'W') seenW++;
else seenE++;
}
console.log(ans.toString());
よくある間違い
- リーダー本人を数えてしまう：右側 E を数えるときは
iを含めない - オフバイワン：
prefixW[i]は「左側だけ」、suffixE[i]は「右側だけ」 - 二重ループで O(N^2)：全 i で左右を毎回数え直さない
- 左右の向きの取り違え：左側は E、右側は W に合わせる
まとめ
- 「左側の W + 右側の E」を各位置で評価するだけの、累積カウント典型。
- 実装は
prefixW/suffixE（見通し重視）か、totalE + 片パス（省メモリ）の二択。 - 制約 3×10^5 に対して O(N) で余裕。競プロの累積パターンの入門に最適。
