Skip to content

B38

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

B38

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
B38.go
B38.go
 
 
B38.js
B38.js
 
 
B38.php
B38.php
 
 
B38.py
B38.py
 
 
B38.ts
B38.ts
 
 
README.md
README.md
 
 

README.md

了解しました。以下では、問題のアルゴリズムについて、図解付きでステップごとの処理をできるだけ丁寧に説明していきます。

🧠 問題の要点（再確認）

  • 草が N 本並んでいて、それぞれ高さを持つ。

  • 高さは1以上の整数で、制約 S に従って高さを割り当てる：

    • S[i] === 'A' ⇒ 草 i < 草 i+1
    • S[i] === 'B' ⇒ 草 i > 草 i+1

  • 高さの合計を最小にするような割り当てを求める。

🧪 例題

入力:

N = 7
S = 'AABBBA'

目標:

S に従って草の高さ H[0] ~ H[6] を割り当て、合計を最小に。

🛠 アルゴリズム手順：図解付き

🟢 Step 1: 初期化

const height: number[] = new Array(N).fill(1);

すべての草の高さをまず 1 にする。

Index:   0 1 2 3 4 5 6
Height: [1 1 1 1 1 1 1]
         ↑ ↑ ↑ ↑ ↑ ↑
         | | | | | |
         A A B B B A  ← Sの内容

🔵 Step 2: 左から順に 'A' 条件を満たすように増加

i = 0: S[0] = 'A' ⇒ height[1] > height[0] にする

height[1] = height[0] + 1 = 2

[1 2 1 1 1 1 1]
   ↑ A条件満たすように

i = 1: S[1] = 'A' ⇒ height[2] > height[1] にする

height[2] = height[1] + 1 = 3

[1 2 3 1 1 1 1]
     ↑ A条件

i = 2: S[2] = 'B' ⇒ 無視（後で処理）

i = 3: S[3] = 'B' ⇒ 無視

i = 4: S[4] = 'B' ⇒ 無視

i = 5: S[5] = 'A' ⇒ height[6] > height[5] にする

height[6] = height[5] + 1 = 2

[1 2 3 1 1 1 2]
                  ↑ A条件

🟠 Step 3: 右から順に 'B' 条件を満たすように補正

i = 5: S[5] = 'A' ⇒ 無視

i = 4: S[4] = 'B' ⇒ height[4] > height[5]

height[4] = height[5] + 1 = 2

[1 2 3 1 2 1 2]
               ↑ B条件満たすように調整

i = 3: S[3] = 'B' ⇒ height[3] > height[4]

height[3] = height[4] + 1 = 3

[1 2 3 3 2 1 2]
            ↑ B条件

i = 2: S[2] = 'B' ⇒ height[2] > height[3]

  • 既に height[2] = 3, height[3] = 3 → 調整必要
height[2] = height[3] + 1 = 4

[1 2 4 3 2 1 2]
         ↑ B条件

i = 1: S[1] = 'A' ⇒ 無視

i = 0: S[0] = 'A' ⇒ 無視

✅ 最終的な高さ配列

[1, 2, 4, 3, 2, 1, 2]

💯 高さの合計値

1 + 2 + 4 + 3 + 2 + 1 + 2 = 15

✅ 図で流れを一括表示

Step 1 (Init):
[1, 1, 1, 1, 1, 1, 1]

Step 2 (A補正):
[1, 2, 3, 1, 1, 1, 2]

Step 3 (B補正):
[1, 2, 4, 3, 2, 1, 2]

最終合計: 15

💡 なぜこれが最適？

  • 高さを必要最低限（1）からスタート。
  • Aに従って昇順を 左→右 に貪欲に増やす。
  • Bに従って降順を 右→左 に補正する。
  • 無駄に高さを大きくしない ⇒ 合計が最小

📌 実装の再掲（TypeScript）

function computeMinimumTotalHeight(N: number, S: string): number {
    const height: number[] = new Array(N).fill(1);

    for (let i = 0; i < N - 1; i++) {
        if (S[i] === 'A' && height[i] >= height[i + 1]) {
            height[i + 1] = height[i] + 1;
        }
    }

    for (let i = N - 2; i >= 0; i--) {
        if (S[i] === 'B' && height[i] <= height[i + 1]) {
            height[i] = height[i + 1] + 1;
        }
    }

    return height.reduce((sum, h) => sum + h, 0);
}

必要であれば、動作のアニメーション、他の例パターン（すべてA、すべてBなど）についても分析可能です。ご希望があればお知らせください。

提出日時 問題 ユーザ 言語 得点 コード長 結果 実行時間 メモリ
2025-07-29 16:11:26 B38 - Heights of Grass myoshizumi Go (go 1.20.6) 1000 1137 Byte 1 ms 1652 KiB 詳細
2025-07-29 16:09:09 B38 - Heights of Grass myoshizumi PHP (php 8.2.8) 1000 1288 Byte 16 ms 21292 KiB 詳細
2025-07-29 16:06:54 B38 - Heights of Grass myoshizumi Python (CPython 3.11.4) 1000 1267 Byte 20 ms 10580 KiB 詳細
2025-07-29 16:00:07 B38 - Heights of Grass myoshizumi TypeScript 5.1 (Node.js 18.16.1) 1000 1312 Byte 41 ms 43056 KiB 詳細
2025-07-29 15:57:14 B38 - Heights of Grass myoshizumi JavaScript (Node.js 18.16.1) 1000 1111 Byte 43 ms 43100 KiB 詳細