AtCoder Petrozavodsk Contest 001 - D Forest
嘘解法かもしれないので程々に．
2つのコーナーケースを記事に載せたのでぜひ．
問題文
https://beta.atcoder.jp/contests/apc001/tasks/apc001_d
公式想定解法
- 考察すると次が分かる
- 各連結成分のうち，必ず使わなければならない頂点は 1 個
- 全て合わせて2(N-M-1)頂点使う．
- ので，これを実装すれば良い．実装量はとても軽い．
yukicoder No.629 グラフの中に眠る門松列
2018/02/24 表現を修正
writerしました
問題
- https://yukicoder.me/problems/no/629
- ざっくり説明：グラフと頂点に割り当てる数字が与えられる．門松パスは存在するか？
本記事の目的
- グラフに含まれる，門松パスの個数を O(M) で求める．
- cielさんの提出コード https://yukicoder.me/submissions/228617 を参考にしました．
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の導入がほぼ不可能であるため．
