Skip to content

B39

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

B39

Folders and files

NameName
Last commit message
Last commit date

parent directory

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

README.md

以下に、TypeScript実装の各処理について、図を交えながらできる限り詳細に解析・解説します。

✅ 問題の構造（再掲）

  • D日間の間に 1日1仕事 できる。
  • 各仕事 i は X[i]日目以降 に開始可能で、報酬は Y[i] 円。
  • 最大収益を得たい。

✅ 解法概要（図付き）

ステップ①：日付ごとの仕事分類

🔹入力例

N = 5, D = 4
jobs = [
  [1, 1],  // 1日目以降：1円
  [2, 4],  // 2日目以降：4円
  [2, 3],  // 2日目以降：3円
  [3, 4],  // 3日目以降：4円
  [4, 2],  // 4日目以降：2円
]

🔸処理

日付をキーとする配列 jobByDay[1..D] を作る：

jobByDay = [
  [],        // 0 は未使用
  [1],       // 1日目に解禁される仕事
  [4, 3],    // 2日目に解禁
  [4],       // 3日目に解禁
  [2],       // 4日目に解禁
]

ステップ②：日を進めて貪欲に選択（ヒープ活用）

🔸ヒープ：常に最大報酬を取り出せる構造

ヒープ構造のイメージ（例）

MaxHeap.push(3)
MaxHeap.push(5)
MaxHeap.push(2)
        5
       / \
      3   2

pop() ⇒ 5（最大の報酬）

ステップ③：各日ごとの処理（図解付き）

✅ Day 1:

  • jobByDay[1] = [1]
  • Push 1 into maxHeap
Heap: [1]
Pop: 1 ⇒ total = 1

✅ Day 2:

  • jobByDay[2] = [4, 3]
  • Push 4, 3 into heap
Heap: [4, 3]
Pop: 4 ⇒ total = 1 + 4 = 5

✅ Day 3:

  • jobByDay[3] = [4]
  • Push 4 into heap
Heap: [4, 3]
Pop: 4 ⇒ total = 5 + 4 = 9

✅ Day 4:

  • jobByDay[4] = [2]
  • Push 2 into heap
Heap: [3, 2]
Pop: 3 ⇒ total = 9 + 3 = 12

✅ 最終結果

total = 12

✅ 各ステップの可視化まとめ

Day 仕事追加 (Y) Heap状態 Pop (最大) 合計
1 [1] [1] 1 1
2 [4, 3] [4, 3] 4 5
3 [4] [4, 3] 4 9
4 [2] [3, 2] 3 12

✅ 補足：ヒープ操作の詳細（図）

push(4) 後のヒープ構造

例：push(4) されたとき：

1. Insert: [3]
2. push(4) → [3, 4]
3. Swap to restore heap: → [4, 3]

pop() 時の構造変化

Heap: [4, 3, 2]
Pop → 4 (root)
Replace with 2 → [2, 3]
Swap → [3, 2]

✅ 時間・空間計算量の分析

処理項目 計算量 備考
job分類（O(N)） O(N) 各仕事を1回処理
各日ヒープpush O(N log N) 最大N件、1回あたりlogN
各日ヒープpop（D回） O(D log N) 最大D日間でpopされる
合計 O(N log N + D log N) 高速

✅ まとめ

  • 本問題は「日付制約つき最大選択問題」
  • 鍵は「毎日、報酬最大の仕事を貪欲に選ぶ」戦略
  • TypeScriptでの実装でも型安全・高速処理が可能

必要であれば、TypeScriptコードにインラインで図やログを埋め込むデバッグバージョンも提供可能です。希望があればお知らせください。

提出日時 問題 ユーザ 言語 得点 コード長 結果 実行時間 メモリ
2025-07-30 17:52:42 B39 - Taro's Job myoshizumi Go (go 1.20.6) 1000 2386 Byte 39 ms 12456 KiB 詳細
2025-07-30 17:51:02 B39 - Taro's Job myoshizumi PHP (php 8.2.8) 1000 1510 Byte 118 ms 95048 KiB 詳細
2025-07-30 17:47:29 B39 - Taro's Job myoshizumi Python (CPython 3.11.4) 1000 1538 Byte 176 ms 60012 KiB 詳細
2025-07-30 17:41:22 B39 - Taro's Job myoshizumi TypeScript 5.1 (Node.js 18.16.1) 1000 2649 Byte 229 ms 118112 KiB 詳細
2025-07-30 17:38:44 B39 - Taro's Job myoshizumi JavaScript (Node.js 18.16.1) 1000 2466 Byte 240 ms 118920 KiB 詳細