読者です 読者をやめる 読者になる 読者になる

天下一2014 QualA

全然駄目でした(A,Cの2完)
A:ついこないだTo_string関数を自分で書いた(ostringstreamを使う)ので覚えていた、多言語だとより簡単?

B:問題文読解が激ムズ、ここまで悪意のある問題文は普通書けない.明らかにこのセットの中で一番むずい.かぶりん死ね(かぶりんは悪くない、問題作成者がゴミ)

C:"文字列集合Sを同時に同じ文字列に当てはめられるか"は、"どのx,y∈Sをとっても同じ文字列に当てはめられる"と同値なので,dp[bit]="bitを何個でいけるか"に対し、dpが1になるやつを先に埋めておいて、後はbitのsubset列挙の魔法を使う.O(3^n).DEGwerが枝刈り前探索とか言ってて??だった

D:角度に直して巡回スケジューリングっぽい一個決めて貪欲をやるだけ…と思っていたのだが思わぬ落とし穴があった.
蟻本のダブリングのとこにある巡回スケジューリングでは、見る回数を2周させてループを考えないようにする方法が取られている(例えば区間のmaxを99として、(0,10)は(0,10)と(100,110)の二つが登録される.また,(9,1) (つまりループしている) では (9,101),(109,201) の二つ)
蟻本の問題とやることが違うのは、蟻本のは取りたいだけ取るのだが、こっちは全部埋めなきゃいけないということ.アルゴリズム的には全然変わらないのだが…
今(0,1),(98,5)とかがあるとすると、登録される区間は(0,1),(100,101),(98,105),(198,205).貪欲の性質上secondでソートするのだが、この際105から見ていくと(0,1)系統を補足できない
蟻本だとこういう系ではどうせ(0,1)とかは選べないから大丈夫なんだけど、こっちでは全区間に対応しなきゃいけないのでスルーしたら駄目.
3周させたらAC.
あと、イベントを保管する配列を作ってもいい(このコード書いてACとった後に元のコードとdifをとってバグを取った)

E:おもしろい.そんなにむずくないかと思ったけど悩んだ.まず,このピースを動かすとそれによって直接的にこのピースが動く(つまり直に底面で接している)みたいなグラフを持って、強連結成分分解して、DAGになったところでdfsでサイズを足せばいいと思ったのだが、一回別れてからまた合流する場合に重複して足されてしまうのでまずい.
dp[i][j]="強連結成分iを動かすとj列目は?行目から動く"を持つとdfsが出来る