Codeforces Round #517 (Div. 1 + 2, based on Technocup 2019 Elimination Round 2)
-
masashinakata
- 1060
- 1
- 0
- 0
-
- いいね！0
31536000
@CuriousFairy315
この結果だけど 結局、本当に累積和上の二分探索で動くの確認したわ 各フレームについて計算量O(TL+NlogT)、スライド区間和なので引き算コストが重い セグ木とか使えばO((N+L)logT)で終わりそうなので検討の余地あるかも ……いや、その場合O(NlogT+L(logT)^2)か どうせTは30とかだしこれはむしろ重い twitter.com/CuriousFairy31…
2018-10-21 22:03:37
31536000
@CuriousFairy315
流石にこれは冗談だと思いたい のでTLのプログラマーに質問 次のような問題に対して、どのようなプログラムを組む？ 問題はこの下にスレッドで置いておくね コード書かなくて良いから思いつきで答えてくれて良いよ 今は多くの意見の方が欲しい
2018-10-21 13:59:08
31536000
@CuriousFairy315
引き算は常に全区間なので適切に操作すればO((N+L)logT)可能だな ……んー、でも定数倍と対して変わらないな……また後日かなぁ
2018-10-21 22:06:35
てんぷら
@tempura_cpp
木の問題でO(N)しかなさそうな問題で木DPじゃない問題がないため(これはDPというかDFSですみたいな話がしたいわけではない)
2018-10-21 22:16:39
31536000
@CuriousFairy315
@tempura_pp あれ、付かない？ LlogTの方はS[T][L]の配列全部にS[j][i]-=S[T-1][i]しなきゃだからセグ木でもlog付くと思うし NlogTは二分探索のコストなので自明に付くし それとももっと効率良い方法あった？
2018-10-21 22:23:13
31536000
@CuriousFairy315
@tempura_pp ああなるほど T回ごとに全体から引き算する処理を書けばならし計算量がO(L+NlogT)か オーバーフローもしないはずなので有りっちゃ有りだな
2018-10-21 22:33:31
てんぷら
@tempura_cpp
@CuriousFairy315 よくわかってないんですが何に関するオーバーフローですか(前から順番にTをたどってa_iを復元できるかみたいな話ですよね)
2018-10-21 22:35:30
31536000
@CuriousFairy315
@tempura_pp あ、えーと累積和部分 今回T≦10^5にしたけど実際は10^infなのでその辺の兼ね合いでね あー、ただ私より強いてんぷらさんならもしかしたら私と違う回答が見えてるのかも
2018-10-21 22:39:35
satanic@研究💪
@satanic0258
こどふぉの問題を解くのに要する時間が分かるのでもう時間内に何も解けないと分かったら即座に入眠することが出来る(は？)(おはようございます)
2018-10-21 23:03:31
satanic@研究💪
@satanic0258
こどふぉdiv1 A:(1,…,kの和)<=a+bなる最大のkについて,V:={1,…,k}の部分集合で和がaになるものSが存在する(後ろから貪欲)のでSとV-Sを出力 B:左上から(i,j)までのあるパス上の文字を全てaにする最小コストc(i,j)をDPで各マスについて求めて,c(i,j)<=kなるマスを全てaで埋める,後は左上から貪欲にとる
2018-10-21 23:13:06
アルメリア
@armeria_betrue
「Revenge of BBuBBBlesort!」とか「Normalization」とかに似てる DEGwerさんがARC-Fに置きそう
2018-10-21 23:14:35
31536000
@CuriousFairy315
@tempura_pp あー……えっとね そもそも、今作ってるのキー入力履歴から特定の順にキーを押してるか調べる(ex, ↑↑↓↓←→←→BA)プログラムなの それで、受付時間をT(T≦10^5)として持ってるけど、当然それ以上の入力データが来るのね その時、その入力に合わせて前の入力情報を消す必要があるのよ
2018-10-21 23:18:36