std::next_permutation
-
dark_yoshi_cxx
- 5927
- 0
- 2
- 0
-
- いいね！0
nico_shindannin（診断人）
@nico_shindannin
next_permutationで、わしも大事な何かを失ったのかもしれんのう…（遠い目）
2011-05-27 00:42:45
hogeover30
@hogeover30
next_permutationのかわりにprev_permutationにリバースイテレータを渡してやるとchallengerを騙すことができるだろうか
2011-05-27 00:45:17
chokudai(高橋 直大)@AtCoder社長
@chokudai
next_permutation TLかぁ 正直あんまり広めたくないものの１つ 再帰実装と実行時間が変わるか、って言ったら殆ど変らないし、組みなれてない内から頼るのはお勧めしないなぁ 黄色以上で速度がどうしても必要、とかならしゃーないけど
2011-05-27 01:03:07
chokudai(高橋 直大)@AtCoder社長
@chokudai
next_permutationとかは、確かにTopCoderの成績を上げるのには直結するけど、最初はそれくらいの複雑さのものは自力で書いて欲しいかな 速度勝負になれば確かに大きな差が出るけど、解けた・解けなかったとかの差が出るようなら、むしろ練習のために自力で書くべきである
2011-05-27 01:10:47
nico_shindannin（診断人）
@nico_shindannin
. @h_chiroさんの書き込みをみて、順列総当りを再帰で書いた場合、再帰なら枝刈りのチャンスがあるので、next_permutationが遅いなぁと思ったんだけど、別にnext_permutationも途中で数字を書き換えたてスキップとかさせたら枝刈りも可能だなと思い直す
2011-05-27 01:11:04
chokudai(高橋 直大)@AtCoder社長
@chokudai
もちろんこれは競技プログラマに限った話かな 競技プログラミングってのは、方針が見えればそれで終わりじゃない それを如何に頭の中でちゃんと組み上げて、ミスなくコードに落とせるか その速度が要求されるのに、最初っから手抜きばっかり覚えてたら、鍛えるべきところが鍛えられない
2011-05-27 01:13:46
隅須正昭
@nagoya313
@chokudai 既にいいものがあるならありがたく使わせてもらうをやった結果アルゴリズム全然自力で組めなくなってしまったんで、ここらへんのバランスがどうなんだろうなと思うことはありますね。
2011-05-27 01:53:34
tomerun
@tomerun
next_permutationはTopCoder参加しはじめの頃にSRM本番で初めて見てその場でJava実装した思い出 http://d.hatena.ne.jp/tomerun/20081202/1228231059
2011-05-27 01:17:55
nico_shindannin（診断人）
@nico_shindannin
一番の特効薬は、TopCoderで安易にnext_permutationを使うと、落ちるような問題かも。みなさん考えてみましょう。
2011-05-27 01:21:07
rti
@super_rti
【C++】next_permutationがちょうすごい件【TopCoder】 - nokunoの日記 http://htn.to/Kfsa8x
2011-05-27 01:22:27
hogeover30
@hogeover30
std::next_permutation を使うのが手抜きなら std::sort を使うのも手抜きな気がするけどコンテスト中に O(nlogn)のソートなんて書ける気がしない。
2011-05-27 01:22:51
2DP
@Respect2D
ICPCのcleaning robotなんかは, next_permutationで通らなくて, 再帰で通るものの例. たしかPKUではTLEで通らなかったはず
2011-05-27 01:25:01