![想定解法
● DP (重み付き区間スケジューリング)
? DP[i][j] := i限目までにj個の科目を受講したときの最大の幸福度。
O(N * M2
)となる。N ≤ 8, M ≤ 300なのでこれで大丈夫。
※ 曜日を要素にとって
DP[i][j][k] := 曜日iのj限目までにk個の科目を受講したときの最大の幸福度。
としても良い。しかし、これは少し複雑になるので、1日にN限あるときの曜日di
のai
限目
をai
+ di
* Nのように表すと次元が1つ減り、Happyになれる。](https://image.slidesharecdn.com/c-160924150135/85/C-5-320.jpg)
![別解
● ビットDP (+ DP)
? DP[i][j][k] := i曜日に、時間割で使用している時間の集合jで今までにk個の科目
を受けたときの最大の幸福度。
DP2[i][j] := i曜日までに、j個の科目を取ったときの最大の幸福度.
O(2N
* M2
)である。N ≤ 8, M ≤ 300なので間に合う。
※ この解法は、想定解法よりも難しいと思います。](https://image.slidesharecdn.com/c-160924150135/85/C-7-320.jpg)
![SSII2022 [OS3-02] Federated Learningの基礎と応用](https://cdn.slidesharecdn.com/ss_thumbnails/ssii2022-os3-02-220607020834-2b5f93ff-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]SoftTriple Loss: Deep Metric Learning Without Triplet Sampling (ICCV2019)](https://cdn.slidesharecdn.com/ss_thumbnails/yokota20190920dlhack-190920011134-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]A closer look at few shot classification](https://cdn.slidesharecdn.com/ss_thumbnails/acloserlookatfew-shotclassification-190304034759-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Blind Video Temporal Consistency via Deep Video Prior](https://cdn.slidesharecdn.com/ss_thumbnails/20201030deepvideoprior-201030024757-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Discriminative Learning for Monaural Speech Separation Using Deep Embe...](https://cdn.slidesharecdn.com/ss_thumbnails/201912227dldiscriminativeleraningformanaouraspeechseparationusingdeepembeddingfeaturessumissionver2-191227001259-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Taskonomy: Disentangling Task Transfer Learning](https://cdn.slidesharecdn.com/ss_thumbnails/dlreadingyokota20180706re2-180706055345-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]When Does Label Smoothing Help?](https://cdn.slidesharecdn.com/ss_thumbnails/yokota20191227dl-191227001522-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Viewers also liked (6)
More from Takumi Yamashita (20)
Recently uploaded (6)
C : 解説
- 1. C: Unhappy Class 原案: arrows 解説: arrows
- 2. 問題概要 ● 月曜日から金曜日にそれぞれ、1限からN (2 ≤ N ≤ 8) 限までの時間割の枠がある ● M (0 ≤ M ≤ 300) 個の受講可能な科目があり、科目iは、di (0 ≤ di ≤ 4) 曜日のai (1 ≤ ai ≤ N) 限目からki (ai + ki -1 ≤ N) コマ連続で行われ、それを受講することで幸福度ti (1 ≤ ti ≤ 100) を得ることができる ● M個のうち最大L (0 ≤ L ≤ min(N*5, M)) 個までの科目を他の科目と重ならないよう に受講できるので、得られる幸福度を最大化せよ
- 3. ダメな解法 ● 全探索 それぞれの科目について取るか取らないかのいずれかを指定するのに O(2M )。 そして取る科目が互いに重ならないかどうかをチェックするのにO(N) かかるので、この方法だと、O(2M * N) となる。 N ≤ 8, M ≤ 300 なので間に合わない。
- 4. 考察 ● 時間割のコマ(時間軸)を棒(‘|’)で区切り、時間が早い順に考える {これまでに選んだ科目の集合} | {これから選べる科目の集合} ● これまでに選んだ科目の集合はこれから選べる科目の集合とは独立しているの で、前者が最適になるように更新していけば、最終的な解答も最適になる
- 5. 想定解法 ● DP (重み付き区間スケジューリング) ? DP[i][j] := i限目までにj個の科目を受講したときの最大の幸福度。 O(N * M2 )となる。N ≤ 8, M ≤ 300なのでこれで大丈夫。 ※ 曜日を要素にとって DP[i][j][k] := 曜日iのj限目までにk個の科目を受講したときの最大の幸福度。 としても良い。しかし、これは少し複雑になるので、1日にN限あるときの曜日di のai 限目 をai + di * Nのように表すと次元が1つ減り、Happyになれる。
- 6. 想定解法 (余談) ● DPを工夫したり、Segment Treeなどのデータ構造を使用するともう少し速く解くこと ができる (もともとの問題の制約はN ≤ 1000, M ≤ 1000だった)
- 7. 別解 ● ビットDP (+ DP) ? DP[i][j][k] := i曜日に、時間割で使用している時間の集合jで今までにk個の科目 を受けたときの最大の幸福度。 DP2[i][j] := i曜日までに、j個の科目を取ったときの最大の幸福度. O(2N * M2 )である。N ≤ 8, M ≤ 300なので間に合う。 ※ この解法は、想定解法よりも難しいと思います。
- 8. 結果 ● Onsite ○ First AC: edamame72 チーム(59min) ● Online ○ First AC: antaさん (12min) ● Success Rate (Accepted / Submission) ○ 45.83% (22 / 48)
- 9. ジャッジ解 arrows C++ 40行 dohatsu C++ 37行 haji C++ 45行 kawabys C++ 21行 kzyKT C++ 47行 bitDP解 moti C++ 57行 rollman C++ 36行 sate C++ 31行 uku C++ 34行