S007の解法メモ

はじめに

プログラミングコンテストなどで見かける、特定のルールで圧縮された文字列に関する問題があります。例えば、「3(a2(b)) は abbabbabb になる」といったルールです。

今回の問題「S007:データヒストグラム」では、数字と括弧を用いた以下のような圧縮ルールが定義されていました。

• 数字(文字列) は、文字列を数字の回数だけ繰り返す。
• 数字が 1 の場合は省略可能。
• 括弧の中の文字列長が 1 なら括弧も省略可能。
• 例: 2(2u2lt4d)3(rb)pa -> uulltdddduulltddddrbrbrbpa

このルールに従った圧縮文字列が与えられ、展開後の（非常に長くなる可能性のある）文字列における 'a' から 'z' までの各文字の出現回数を求める、という課題です。最大で $2^{60}$ 文字にもなりうるため、実際に展開するわけにはいきません。

私は「S007:データヒストグラム」にて、Go言語で解答し満点を獲得できました。

この記事では、この問題を解くために考えたアプローチと、実際に提出して合格したGo言語のコードについて解説します。

解法の方針

この問題の鍵は、圧縮文字列の再帰的な構造に注目することです。圧縮文字列は、数字、英小文字、括弧によって構成されています。特に、括弧 () は入れ子構造を持つ可能性があり、これは再帰的な処理に適しています。

全体の流れとしては、圧縮文字列を先頭から1文字ずつ見ていき、その文字の種類に応じて処理を行います。

1. 数字: 連続する数字を読み取り、その数値を「乗数」として保持します。この乗数は、直後の文字または括弧ブロック全体に適用されます。
2. 英小文字: 現在保持している乗数分だけ、その文字のカウントを増やします。その後、乗数をデフォルトの1に戻します。
3. 開き括弧 (: 括弧の中身を解析するために、再帰的に処理関数を呼び出します。括弧の前に数字があれば、その乗数を再帰呼び出しの結果に適用し、括弧の中身全体が何回繰り返されるかを示します。
4. 閉じ括弧 ): 現在の括弧レベルの解析が終了したことを示します。再帰呼び出しから戻り、呼び出し元にその括弧内の文字カウント結果を返します。

各アルファベットの出現回数は、[26]uint64 のような配列を用いて管理します。インデックス 0 が 'a'、1 が 'b'、...、25 が 'z' に対応します。展開後の文字列長が $2^{60}$ に達する可能性があるため、カウンタには64ビット符号なし整数 (uint64) を使用します。

コード解説

以下に、実際に提出したGo言語のコードを示します。

package main

import (
	"fmt"
	"strconv"
	"unicode"
)

// parse 関数: 文字列 s の idx の位置から解析を開始し、
// 対応する部分文字列を展開した際の各文字のカウントを返す。
// idx はポインタ渡しされ、解析が進むにつれて更新される。
func parse(s string, idx *int) [26]uint64 {
	var counts [26]uint64      // 現在の解析レベルでの文字カウント
	currentMultiplier := uint64(1) // 直後の文字や括弧ブロックに適用される乗数

	for *idx < len(s) {
		char := rune(s[*idx]) // 現在注目している文字

		if unicode.IsDigit(char) {
			// 数字の場合: 乗数を読み取る
			start := *idx
			for *idx < len(s) && unicode.IsDigit(rune(s[*idx])) {
				(*idx)++ // 数字が続く限り idx を進める
			}
			// 文字列から uint64 型の乗数をパース
			m, _ := strconv.ParseUint(s[start:*idx], 10, 64)

            // 乗数が 0 の場合の特別処理
			if m == 0 {
				// 0 の後の文字または括弧ブロックをスキップする
				if *idx < len(s) {
					if s[*idx] == '(' {
						// 括弧ブロックの場合、対応する閉じ括弧までスキップ
						(*idx)++ // '(' をスキップ
						balance := 1
						for *idx < len(s) {
							if s[*idx] == '(' {
								balance++
							} else if s[*idx] == ')' {
								balance--
								if balance == 0 {
									break // 対応する ')' を見つけた
								}
							}
							(*idx)++
						}
						if *idx < len(s) {
							(*idx)++ // ')' をスキップ
						}
					} else if unicode.IsLower(rune(s[*idx])) {
						// 単一文字の場合、その文字をスキップ
						(*idx)++
					}
				}
				// スキップ後、次の要素のために乗数をリセット
				currentMultiplier = 1
				continue // ループの次のイテレーションへ
			}
			// 0以外の乗数を設定
			currentMultiplier = m

		} else if unicode.IsLower(char) {
			// 英小文字の場合: カウントを更新
			counts[char-'a'] += currentMultiplier // 乗数を適用してカウント
			currentMultiplier = 1                 // 乗数をリセット
			(*idx)++                              // 次の文字へ

		} else if char == '(' {
			// 開き括弧の場合: 再帰呼び出し
			(*idx)++ // '(' をスキップ
			// 括弧の中身を再帰的に解析
			subCounts := parse(s, idx)

			// 再帰呼び出しの結果 (括弧の中身のカウント) に乗数を適用して加算
			for i := 0; i < 26; i++ {
				counts[i] += currentMultiplier * subCounts[i]
			}
			currentMultiplier = 1 // 乗数をリセット

		} else if char == ')' {
			// 閉じ括弧の場合: 現在のレベルの解析を終了
			(*idx)++ // ')' をスキップ
			return counts // このレベルのカウント結果を返す

		} else {
			// 想定外の文字 (問題の制約上は発生しないはず)
			(*idx)++
		}
	}
	// 文字列の終端まで達した場合、最終的なカウントを返す
	return counts
}

func main() {
	var s string
	fmt.Scan(&s) // 標準入力から圧縮文字列 S を読み込む

	idx := 0 // 解析開始位置を 0 に初期化
	// 文字列全体を解析し、最終的なカウントを取得
	finalCounts := parse(s, &idx)

	// 結果を出力
	for i := 0; i < 26; i++ {
		char := byte('a' + i)
		fmt.Printf("%c %d\n", char, finalCounts[i])
	}
}

main 関数

• 標準入力から圧縮された文字列 S を受け取ります。
• 解析の開始位置を示す変数 idx を 0 で初期化します。
• parse 関数を呼び出して、文字列全体の解析を開始します。idxはポインタで渡され、parse関数内で解析位置が更新されます。
• parse 関数から返された最終的なカウント finalCounts を元に、'a' から 'z' までの各文字とその出現回数を指定されたフォーマットで出力します。

parse 関数

この関数は再帰的に呼び出され、与えられた文字列 s の idx の位置から解析を行います。

• counts [26]uint64 配列: 現在の解析レベル（括弧のネストレベル）における各文字のカウントを保持します。
• currentMultiplier uint64: 直前に読み取った数字、またはデフォルト値 1 を保持します。これは、次に来る文字や括弧ブロック全体に適用される繰り返し回数です。
• ループ処理: *idx が文字列 s の長さに達するか、閉じ括弧 ) に遭遇するまで文字を処理し続けます。
  • 数字の処理:
    • unicode.IsDigit で数字かどうかを判定します。
    • 連続する数字を読み取り、strconv.ParseUint で uint64 型の乗数 m に変換します。
    • 0 の処理**: 乗数が 0 の場合は、続く文字または括弧ブロックは展開結果に寄与しないため、スキップ処理を行います。括弧ブロックの場合は、対応する閉じ括弧まで idx を進めます。単一文字の場合は、その文字だけスキップします。その後、乗数を 1 にリセットしてループの次のイテレーションに進みます。
    • 0 以外の乗数の場合は currentMultiplier に設定します。
  • 英小文字の処理:
    • unicode.IsLower で英小文字かどうかを判定します。
    • counts 配列の対応する文字のインデックス (char - 'a') に currentMultiplier を加算します。
    • currentMultiplier を 1 にリセットします（数字がない場合のデフォルト値）。
    • idx をインクリメントして次の文字に進みます。
  • 開き括弧 ( の処理:
    • idx をインクリメントして ( をスキップします。
    • parse 関数を再帰的に呼び出し、括弧の中身 (...) を解析させます。再帰呼び出しは、対応する ) まで解析を進め、その中の文字カウント (subCounts) を返します。idx も適切に進められます。
    • 返された subCounts の各要素に currentMultiplier を掛けて、現在のレベルの counts に加算します。これにより、括弧の前の数字（繰り返し回数）が括弧の中身全体に適用されます。
    • currentMultiplier を 1 にリセットします。
  • 閉じ括弧 ) の処理:
    • idx をインクリメントして ) をスキップします。
    • 現在の解析レベル（括弧の中身）の処理が完了したので、countsを呼び出し元に返します。
• 関数の戻り値: ループが終了（文字列の終端に到達）した場合、または ) によって明示的に返された場合、その時点での counts 配列が返されます。

注意点・工夫点

• uint64の使用: 問題の制約で展開後の文字数が最大 $2^{60}$ となるため、標準の int (通常32bit or 64bit) ではオーバーフローする可能性があります。uint64を使用することで、この巨大な数値を正確に扱えます。
• ポインタ idx の使用: parse 関数が文字列のどの位置まで解析を進めたかを呼び出し元や後続の処理に伝えるために、インデックス idx をポインタで渡しています。これにより、再帰呼び出しから戻った後も、正しい位置から解析を再開できます。
• currentMultiplierの管理: 乗数は直後の1要素（文字または括弧ブロック）にのみ適用されるため、要素を処理するたびに 1 にリセットすることが重要です。
• 乗数 0 のスキップ処理: 乗数が 0 の場合、後続の要素は展開結果に現れません。この部分を効率的にスキップすることで、不要な再帰呼び出しや計算を避けています。特に、深いネスト構造を持つ括弧ブロックをまるごとスキップできるのは大きな利点です。

まとめ

このGoコードは、圧縮文字列の再帰的な構造を利用し、文字列を実際に展開することなく各文字の出現回数を計算します。uint64を用いて巨大なカウント数を処理し、ポインタを使って解析位置を効率的に管理することで、制約内で問題を解くことができます。特に、乗数が 0 の場合のスキップ処理は、パフォーマンス向上に寄与する重要なポイントです。