Contents
対象読者
AtCoderを始めたばかりの初心者。TypeScriptで実装しながら、思考の流れも掴みたい人。
問題概要
https://atcoder.jp/contests/agc040/tasks/agc040_a
- 与えられた記号列
S（長さ N−1、各文字は<または>）に対して、a[i] < a[i+1]（S[i]=<）／a[i] > a[i+1]（S[i]=>）を満たす**非負整数列 a（長さ N）**のうち、要素和が最小になるものの和を求めます。 - 大小関係だけ決まっており、値は自由に選べるため、必要最低限の段差だけを作れば和が最小になります。
S = <<><のとき、aは0 1 2 1 2が最小（和 = 6）です。上昇区間は左から段差を1ずつ、下降区間は右から段差を1ずつ確保すると無駄がありません。- 結論として、左→右で
<による上昇の必要量を積み、右→左で>による下降の必要量を積み、各位置で大きい方を採用すればOK（和が最小）。
ポイント
なぜ「両方向スキャン」で最小になるのか
各位置 i に「左から見たとき必要な高さ」と「右から見たとき必要な高さ」の最大を置くと無駄がない。
S[i]='<'がk回続くなら、左端から 0,1,2,…,k と最小段差で積み上げるのが最小。S[i]='>'がk回続くなら、右端から 0,1,2,…,k と最小段差で積み上げるのが最小。- 同じ位置に左右からの要求がぶつかったら、大きい方に合わせるだけで十分（小さい方は満たされる）。
S = >><<
右から見ると最初の >> で右に向けて 2,1,0… の要求。
左から見ると << で 0,1,2… の要求。
各 i で max(leftNeed[i], rightNeed[i]) を取れば最少。
O(N) 時間・O(N) 追加メモリで解ける王道テクニック。
実装例（TypeScript／O(N)）
以下は左→右で < を処理し、右→左で > を処理したあと、合計を出す実装です。
import * as fs from "fs";
function main(input: string): void {
const S = input.trim();
const n = S.length + 1;
const a = Array(n).fill(0);
// 左→右：'<': a[i+1] >= a[i] + 1 の最低限を入れる
for (let i = 0; i < S.length; i++) {
if (S[i] === "<") a[i + 1] = a[i] + 1;
}
// 右→左：'>': a[i] >= a[i+1] + 1 を満たすよう上書き
for (let i = S.length - 1; i >= 0; i--) {
if (S[i] === ">") a[i] = Math.max(a[i], a[i + 1] + 1);
}
// 合計
const ans = a.reduce((s, x) => s + x, 0);
console.log(ans);
}
const input = fs.readFileSync(0, "utf8");
main(input);
計算量・注意点
- 時間計算量：O(N)
- 追加メモリ：O(N)
Nは最大 5×10^5 なので、1 パス × 2 回 + 累積でも十分高速。
よくある間違い
一方向だけで完了させようとする
< だけ（または > だけ）見て埋めると反対側の制約を満たせない。
>< の谷や <> の山で、左右両側からの必要量が衝突します。S = >< を左からだけ見ると 0 0 1 などにしがちで a[0] > a を満たさない。
右→左のスキャンが必須。
両方向スキャン＋maxで一発解決。
連続区間をループで個別処理して複雑化
<<< や >>> を区間としてまとめて処理するより、素直に 2 回走査するのが速くて安全。
境界条件やインデックスのズレでバグを生みやすい。
区間長を数えてから割り当てる実装は、結局同等の計算量で可読性が落ちる。
発展的な実装例
メモリ節約（部分和だけ使う）
アイデア：最終的に必要なのは合計だけ。ただし、各位置で max(left[i], right[i]) が必要。
2 配列を作らず、一時配列1本で再利用するのが現実的な最小化です（以下）。
// a を leftNeed 用に使い、右→左の走査で a[i] を max(a[i], need) に更新
const a = Array(n).fill(0);
for (let i = 0; i < S.length; i++) if (S[i] === "<") a[i + 1] = a[i] + 1;
let need = 0;
for (let i = S.length - 1; i >= 0; i--) {
if (S[i] === ">") need = need + 1; else need = 0;
if (a[i] < need) a[i] = need;
}
const ans = a.reduce((s, x) => s + x, 0);BigInt で安全に合計（理論拡張）
出力は 64bit 整数で足りますが、練習として BigInt 集計にしてみるのも手です。
let sum = 0n;
for (const v of a) sum += BigInt(v);
console.log(sum.toString());部分検証ユーティリティ
テストのしやすさ向上。競プロ本番前のローカル検証に便利です。
function isGood(a: number[], S: string): boolean {
for (let i = 0; i < S.length; i++) {
if (S[i] === "<" && !(a[i] < a[i + 1])) return false;
if (S[i] === ">" && !(a[i] > a[i + 1])) return false;
}
return true;
}まとめ（PREPで再確認）
<は左から昇順に、>は右から降順に“最低限の段差”を要求する。- 各位置の必要量は左右独立に決まり、合成時は最大値を採れば無駄がない。
- 2 回の線形スキャン＋
max。実装は配列 1 本でOK。 - O(N)・実装簡潔・バグ少なめ。競プロの定番テクとして暗記レベル。
