この記事では、SDOI 2015の「立体図」問題の解法を詳しく解説します。この問題は、複雑な3Dブロックの描画と光のシミュレーションを要求する、難易度の高いシミュレーション問題です。

問題概要

この問題では、m×nのグリッド上に積まれた立方体の立体図を、複数の平行光源の下で描画します。各セルには高さ（積まれた立方体の数）が与えられ、最大9方向からの光（赤、緑、青のいずれか）が照射されます。出力は、指定されたフォーマットに従った文字ベースの立体図です。

実装の手順

この問題を解決するには、以下の3つの主要なステップが必要です。

1. 出力フォーマットの決定: 出力するキャンバスのサイズ（行数と列数）を計算します。
2. 立方体の描画: 計算されたサイズのキャンバス上に、各立方体を正しく配置して描画します。
3. 光の計算: 各光線がどの立方体のどの面を照らすかを計算し、表示する色を決定します。

データ構造の定義

まず、問題を解くために必要なデータ構造を定義します。

• grid[m][n]: 各セルの立方体の数。
• light[3][3]: 9方向の光の情報。各セルは 'R', 'G', 'B', または '*' (光なし)。
• canvas[M][N]: 出力用の2次元文字配列。
• isLit[x][y][z][face][part][color]: 6次元のブール配列。座標 (x, y) の高さ z にある立方体の、face 面の part 領域が、color の光に照らされているかどうかを示します。
• tempLit[x][y][z][face][part]: 5次元のブール配列。特定の1つの光について、照らされているかどうかを一時的に保持します。

ステップ 1：出力フォーマットの決定

出力キャンバスの行数 (M) と各行の最大列数 (N_i) を計算します。

行数 M の計算

各立方体の正面は9行、上面は4行ですが、積み重ねや配置位置によって高さが変わります。以下の式で最大の行数を求めます。

M = 0
for i in 1..m:
    for j in 1..n:
        // height: そのセルの立方体の数
        height = grid[i][j]
        // 正面の高さ
        front_height = 9 + (height - 1) * 8
        // 上面を含めた高さ
        total_height = front_height + 4
        // 奥行きを考慮した高さ（後ろの行ほど高い）
        rows = total_height + (m - i) * 4
        M = max(M, rows)

各行の列数 N_i の計算

各行の最大列数も、立方体の配置によって動的に変化します。同じく最大値を計算します。

for i in 1..m:
    N[i] = 0
    for j in 1..n:
        height = grid[i][j]
        // 正面の幅
        front_width = 9 + (j - 1) * 8
        // 側面を含めた幅
        side_width = front_width + 4
        // 奥行きを考慮した幅
        cols = side_width + (m - i) * 4
        N[i] = max(N[i], cols)
    // 下から4行は、右端が欠けるため調整
    // この調整は描画時に行います。

先頭の空白除去

出力の左端に不要な空白列が生じる場合があるので、それを除去します。

def remove_leading_spaces(canvas, M, N):
    start = 0
    for col in range(1, N[1] + 1):
        all_empty = True
        for row in range(1, M + 1):
            if canvas[row][col] != '\0':
                all_empty = False
                break
        if all_empty:
            start += 1
        else:
            break
    return start

ステップ 2：立方体の描画

各立方体をキャンバス上の正しい位置に描画します。描画順序は 後ろから前、左から右、下から上 で行います。

for i in 1..m:            // 後ろの行から
    for j in 1..n:        // 左の列から
        for k in 1..grid[i][j]:  // 下のブロックから
            draw_cube(i, j, k)

function draw_cube(x, y, z):
    start_row = M - (13 + (m - x) * 4 + (z - 1) * 8) + 1
    start_col = 1 + (m - x) * 4 + (y - 1) * 8

    for row in range(start_row, start_row + 13):
        dx = row - start_row
        if dx < 9:
            N[row] = max(N[row], start_col + 12)
        else:
            N[row] = max(N[row], start_col + 12 - (dx - 8))

        for col in range(start_col, start_col + 13):
            dy = col - start_col
            // 立方体の各文字を canvas[row][col] に代入
            // 詳細な文字マッピングは、図のパターンに従います

ステップ 3：光の計算

ここが問題の核心です。各光線について、照らされる面と領域を計算します。光の方向は9通りあり、それぞれについて計算ロジックが異なります。

光の色の変換

function color_to_index(c):
    if c == 'R': return 0
    if c == 'G': return 1
    if c == 'B': return 2
    return -1  // エラー

光の当たり判定の基本

ある光源に対して、ある立方体の領域が光に届くかどうかは、他の立方体による遮蔽を考慮して決定します。遮蔽判定の基本アイデアは、光源からの距離と高さの差を比較することです。

例えば、北からの光の場合、以下のルールで判定します。

// 南側の立方体 (位置 k) が、北側の立方体 (位置 j) の影になるか
b = (k - j) - (grid[i][j] - grid[i][k])
if b > 0: // 前面（南面）は隠れない
if b > 1: // 上面も隠れない

9方向の光の処理

ここでは、代表的なケースとして「垂直光」と「南からの光」の実装例を示します。

垂直光（真上からの光）

この光は、各セルの一番上の立方体の上面のみを照らします。

function process_vertical_light():
    color_idx = color_to_index(light[2][2])
    if color_idx == -1: return  // 光がない場合
    for i in 1..m:
        for j in 1..n:
            top_z = grid[i][j]
            for part in 0..3:
                isLit[i][j][top_z][0][part][color_idx] = true
                // 0: 上面

南からの光

この光は、北側の立方体の上面と南面に影響を与えます。

function process_south_light():
    color_idx = color_to_index(light[3][2])
    if color_idx == -1: return

    // 初期化: 全ての面が照らされると仮定
    for i in 1..m:
        for j in 1..n:
            for z in 1..grid[i][j]:
                for part in 0..3:
                    tempLit[i][j][z][0][part] = true  // 上面
                    tempLit[i][j][z][2][part] = true  // 南面

    // 遮蔽判定: 自分より北側の立方体だけが影を作る
    for i in 1..m:          // 光源の列
        for j in 1..n:      // 光源の行
            for k in (i-1)..1:  // 北側の立方体をチェック
                for z in 1..grid[k][j]:
                    b = (i - k) - (grid[i][j] - z)
                    for part in 0..3:
                        tempLit[k][j][z][0][part] = tempLit[k][j][z][0][part] and (b > 0)
                        tempLit[k][j][z][2][part] = tempLit[k][j][z][2][part] and (b > 1)

    // 結果を記録
    for i in 1..m:
        for j in 1..n:
            for z in 1..grid[i][j]:
                for part in 0..3:
                    isLit[i][j][z][0][part][color_idx] = isLit[i][j][z][0][part][color_idx] or tempLit[i][j][z][0][part]
                    isLit[i][j][z][2][part][color_idx] = isLit[i][j][z][2][part][color_idx] or tempLit[i][j][z][2][part]
                    // リセット
                    tempLit[i][j][z][0][part] = false
                    tempLit[i][j][z][2][part] = false

色の決定

各領域がどの色の光に照らされているかをもとに、表示する文字を決定します。

function mix_color(x, y, z, face, part):
    r = isLit[x][y][z][face][part][0]
    g = isLit[x][y][z][face][part][1]
    b = isLit[x][y][z][face][part][2]

    if r:
        if g:
            if b: return 'W'  // 白
            else: return 'Y'  // 黄
        elif b: return 'P'    // 紫
        else: return 'R'      // 赤
    elif g:
        if b: return 'C'      // シアン
        else: return 'G'      // 緑
    elif b: return 'B'        // 青
    else: return 'K'          // 黒（無光）

まとめ

この問題は、一見複雑に見えますが、出力フォーマットの決定、立方体の描画、光の計算という3つの明確なステップに分解することで、計画的に実装することができます。特に光の計算では、各方向の光の特性を理解し、正しい遮蔽判定を実装することが重要です。コードは長くなりがちですが、各部分のロジックを丁寧に実装すれば、必ず解ける問題です。