TTPC2015 J. 指さし 講評

問題

https://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_J

解説

https://bitbucket.org/ttpc2014/ttpc2015/overview

想定解法

残り人数とサイズ$K$のサイクルのありなしでDPあるいは,残り人数と最大サイクルサイズでDPのどちらかです.

前者は$O(N^2)$,後者は$O(N^{2}log(N))$で解くことができます.

提出者の解法

前者と後者,どちらも結構多かったように感じました.

感想

いい感じに正答者が多くて嬉しいです.$O(N^2logN)$解をベースに考えていたので$150$点にしましたが,$O(N^2)$解のことを考えると$100$点でも良かったですね.正答率は低いけど,部分点もあるしそのせいですかね?$O(N^3)$解法とかもキッチリ落とせたし,テストケース作成も楽で最高でした.

正直OEISに載っているとは思いませんでした(全く探さなかった訳ではないですが,見つけられなかった).まさか$2$つパラメータがあっても引っかかるとは…