-
masashinakata
- 924
- 0
- 0
- 0
-
- いいね！0
satanic@研究💪
@satanic0258
CSA50 A:xとy持って足したり引いたり．|x|+|y|が答え B:7で割ったあまりがある値になるか判定(面倒じゃない？) C:ある1点から他の3点への距離を調べて昇順ソートした時，最初2つが同じかつ最初×√2==最後が成り立つかを調べる(始点は全通り試す) (→)
2017-09-28 02:00:55
satanic@研究💪
@satanic0258
(→) D:順位でソートしてクラスを見ると，1操作で最長増加部分列に含まれる要素を取り除くことが出来る．シミュレーションは遅い(本当か？)ので，先頭からmultisetを持って「クラス[i]未満で最大のもの」があればそれをクラス[i]で置換し， (→)
2017-09-28 02:01:07
satanic@研究💪
@satanic0258
(→) 無ければ新たに追加するようにすればO(NlogN)で答えを求められる．(答えはmultisetのサイズ) E:最適な順列は，n/2より大きい要素をA,n/2より小さい要素をBとすると，(n/2)ABAB…AB(n/2+1)か，この逆のものとなる． (→)
2017-09-28 02:01:13
hamayanhamayan
@hamayanhamayan
はてなブログに投稿しました #はてなブログ Min Swaps [CSAcademy #50 E] - はまやんはまやんはまやん hamayanhamayan.hatenablog.jp/entry/2017/09/…
2017-09-28 02:01:17
satanic@研究💪
@satanic0258
(→) A同士，B同士はswapしてもコストが変わらないことに注意．このことから，まず端へn/2とn/2+1を動かし，その後Aの所にBがあるようなもの(またはその逆)をカウント，最後に2で割ると答え(逆もやり小さい方を答える)
2017-09-28 02:01:25
とーらす🌸📦🌕✨🍀
@torus711
やったこと A: 軸ごとに計算して絶対値の和 B: リアル日付使える言語でインチキ．適当な年の元旦から，閏年でなく曜日が合う年まで next_year → 一年回す C: いくつかライブラリ貼って頑張る
2017-09-28 02:02:35
とーらす🌸📦🌕✨🍀
@torus711
やったこと D: 順位順にクラスを並べた列で考えると，狭義単調増加な部分列に入ってる人は全員勝てる．なので，そういう風に分割すると考える．先頭から舐めつつ構築中の部分列の末尾だけもって，「自身未満の最大値」が末尾の部分列にくっつけていく．存在しないなら一本増える
2017-09-28 02:05:00
hogeover30
@hogeover30
Congratulations! Your rating has increased by 17 points 😄
2017-09-28 02:10:39
とーらす🌸📦🌕✨🍀
@torus711
書き忘れ．更新は末尾がこの条件を満たすものの内で最大値をとるところにやると最も損しないので，そうする．末尾のリストを昇順に持っておくと更新後も昇順のままで，増えるときは先頭に最小値が入ることになるので deque で二分探索 or push_front
2017-09-28 02:13:43