プロフィール
AtCoder PR

AGC040AをTypeScriptで解く：〈と〉から最小総和を作る両方向スキャン

 
AtCoder AGC040A解説
記事内に商品プロモーションを含む場合があります
Contents
  1. 対象読者
  2. 問題概要
  3. ポイント
  4. 実装例（TypeScript／O(N)）
  5. よくある間違い
  6. 発展的な実装例
  7. まとめ（PREPで再確認）

対象読者

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（和が最小）。

問題文

長さ N−1 の文字列 S が与えられます． S の各文字は < または > です．

長さ N の非負整数列 a1​,a2​,⋯,aN​ は， すべての i (1≤i≤N−1) について次の条件をみたす時，良い非負整数列と呼ばれます．

  • Si​= < のとき： ai​<ai+1​
  • Si​= > のとき： ai​>ai+1​

良い非負整数列の要素の総和としてありうる最小の値を求めてください．

制約

  • 2≤N≤5×105
  • S は < と > のみから成る長さ N−1 の文字列．

入力

入力は以下の形式で標準入力から与えられる．

S

出力

良い非負整数列の要素の総和としてありうる最小の値を出力せよ．

入力例 1

<>>

出力例 1

3

a=(0,2,1,0) は良い非負整数列であり， この場合の要素の総和は 3 になります． 要素の総和が 3 より小さい良い非負整数列は存在しません．

ポイント

なぜ「両方向スキャン」で最小になるのか

各位置 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)・実装簡潔・バグ少なめ。競プロの定番テクとして暗記レベル。
RELATED POST