Kの重複を許す区間スケジューリング問題
2018/02/22 更新 文章を修正
区間スケジューリング問題
http://www.prefield.com/algorithm/misc/interval_scheduling.html から引用．
区間スケジューリングは次の問題である．仕事が n 個与えられる．各仕事 j には開始時刻 s[j] と終了時刻 f[j] が設定されている．仕事は開始時刻から終了時刻まで続けて行わなければならず，同時に複数の仕事を行うことはできない．最も多くの仕事を行う方法を求めよ．
Kの重複を許す区間スケジューリング問題
区間スケジューリング問題では，『同時に複数の仕事を行うことはできない』としていた． これを『K個までは同時に複数の仕事が出来る』と置き換えてみる．
すなわち，上の区間スケジューリング問題はK=1の重複を許す区間スケジューリング問題である．
問題集
- CodeSprint で K=2 が出題されている(リンクを探せず)．
- yukicoder No.580 旅館の予約計画 - yukicoder
- 入力が面倒だが，
scanfや正規表現で読み取って，day*1440+hour*60+minでおｋ - 問題の制約上
O(NM)で accept 出来る．
- 入力が面倒だが，
Kuin で 競技プログラミング(yukicoder No.4 おもりと天秤) の問題を解く
2019/02/15 追記：
コードが動かなくなっていたので，書き直しました．
#316677 No.4 おもりと天秤 - yukicoder
math@knapsackを使ったバージョンも載せます．
#316679 No.4 おもりと天秤 - yukicoder
Kuinとは？
「Kuin」は、簡単で高速な実用プログラミング言語です。
- オブジェクト指向言語．
- 2D,3D描画を標準でサポート．
- 2017/9/17に完成版としてリリース．
割と前から存在している言語で，競プロ界隈にもKuinの話題が流れている*1ようです．
しかし，Googleで検索した*2ところ，競技プログラミングの問題を実際に解いた記事はありませんでした*3．
yukicoder No.4 おもりと天秤
※解き方の解説はしません．
https://yukicoder.me/problems/no/4
問題概要：daveを授業に集中させろ．
*1:本人も言及https://twitter.com/kuina_ch/status/913934988927578112
*2:2017/10/05に「競技プログラミング Kuin」で検索
*3:ほとんどのジャッジ環境がLinuxであり，2017/10/05現在Windows環境でのみ動作するKuinの導入がほぼ不可能であるため．
yukicoder No.550 夏休みの思い出（１）
yukicoder No.545 ママの大事な二人の子供
問題はこちら． - No.545 ママの大事な二人の子供 - yukicoder
コンテスト中に半分全列挙のアルゴリズムを調べ，書きなぐってAccept通したので，その考え方を書きます．
問題文
個のアイテムがある．
番目のアイテムをA君に渡すとA君は
ポイント喜ぶ．
ポイント喜ぶ．
- 適切に分配することで，2人の喜び度合いの合計の差をなるべく小さく抑えたい．
制約．
オーダー)．
- 喜怒哀楽が激しく，ポイントによる動的計画法が使えない．(
オーダー)
