Codeforces Round #472 (rated, based on VK Cup 2018 Round 2)
-
masashinakata
- 683
- 0
- 0
- 0
-
- いいね！0
HIR180
@HIR180
Eはかなり良い問題で、高さr以下の並べ方はunimportant -> important (重さ降順) と固定していいことが示せるのでO(n^2)のdpができる
2018-03-25 02:51:55
(nは自然数)
@n_vip
F問題「0-9の和をあれするのには9まで持っとけばいい」の嘘をするとかなり計算量がいい感じになって騙された（頭が悪いだけなのでは）
2018-03-25 02:52:28
iwashi31
@iwashi31
div2 D は各時刻で最低何本の線が引かれている必要があるのかを計算した後数列の値を引いた。通るかしら pic.twitter.com/Hr5nySEbnt
2018-03-25 02:53:24
拡大
agw
@masashinakata
ここが悪いらしかったんだが(続く) public: bool operator<(const node_t& n) const { const int Ek = 2000000000; double x = static_cast<long double>(Ek - E[ j]) / (Ek - E[ i]); double y = static_cast<long double>(Ek - E[n.j]) / (Ek - E[n.i]); return x < y; };
2018-03-25 02:53:26
agw
@masashinakata
間違えてlong doubleからdoubleにキャストしていたのが問題だったようだ... orz(Custom Invocationで確認)
2018-03-25 02:54:02
HIR180
@HIR180
@uwitenpen r以下の所で使うsetを決めうつとあとは「l以上の所にいくつimportantを詰め込めるか」だけ考えればよい、という思考をしました
2018-03-25 02:54:48
有為
@uwitenpen
Dは(V/X,1/X)を、傾きWがy軸、-Wがx軸に移動するように変換したあとnon-decreasingなpairの個数を数えた。W=0のとき特別扱いしないといけない？
2018-03-25 02:55:06
satanic@研究💪
@satanic0258
A:行を重複しないsetに入れたあと各列で黒カウントして2以上ならNO B:i昇順,k伸ばせるだけ伸ばすしゃくとり,j=i+1とすればよい C:後ろから累積maxしておいた列aも用意して,aで最大値更新があったところで線のcntを増やしてcnt-m[i]-1を足してく
2018-03-25 02:55:19
agw
@masashinakata
お家のclang君では大丈夫だったので、???だった...こういうのダメなときは提出時のコンパイラをclangにしてもいいかもなあ φ(・ω・ ) ﾒﾓﾒﾓ
2018-03-25 02:56:01
btk
@btk15049
d1 A 各行bit情報に落としておくと、bi&bj!=0ならばbi==bjが成り立たなければいけないので、これをn^2で適当に判定する 実装は6行ぐらい B 問題文が読めないけどしゃくとりをしました C よくわからないけど線形のものを書きました E ソートしてナップザック的なのをすると行けるはずなんだけど通らない
2018-03-25 02:56:19