CSA Round #48 (Div. 2 only)

kuuso @kuuso1

ちょっとだけcsaやるかな．

2017-09-13 23:36:22

satanic@研究💪 @satanic0258

CSAでるぞい

2017-09-13 23:41:20

olphe @_olphe

div1は2週に一回あるのか

2017-09-13 23:48:04

とーらす🌸📦🌕✨🍀 @torus711

CS Academy 出るよっと

2017-09-13 23:51:51

有為 @uwitenpen

csaは遅れて参加する

2017-09-13 23:57:32

不養生 @satashun

csacademy出てみる

2017-09-13 23:57:58

olphe @_olphe

CSA頑張るぞい

2017-09-13 23:59:33

satanic@研究💪 @satanic0258

CSA～

2017-09-13 23:59:37

satanic@研究💪 @satanic0258

がんばるぞい！

2017-09-13 23:59:42

有為 @uwitenpen

CSAはじめます

2017-09-14 00:40:06

kmjp @kmjp_pc

あれ、E何で落ちたのと思ったら唐突にリジャッジが走って通った。

2017-09-14 00:56:03

不養生 @satashun

かなりもたついてしまった

2017-09-14 01:31:10

olphe @_olphe

えーんえーん

2017-09-14 01:58:23

olphe @_olphe

117位は流石にウケるが

2017-09-14 01:59:56

olphe @_olphe

Dどうやるの

2017-09-14 02:00:09

うし @ei1333

CSA A. うんうん B. 雰囲気でね競技プログラミングをね C. 下三桁を虚無うく全探索して、もうバグはありましぇんをします D. BITでえい、転倒数を数えるイメージをするとうしし E. なにもわからないねね、悲しいね

2017-09-14 02:00:32

とーらす🌸📦🌕✨🍀 @torus711

おつでし

2017-09-14 02:00:40

とーらす🌸📦🌕✨🍀 @torus711

やったこと　A: 総和とって足したものを比較　B: 最初が 0 だったことにしてシミュレートしてから，最小値を引くと合う

2017-09-14 02:03:27

とーらす🌸📦🌕✨🍀 @torus711

やったこと　C: 下三桁が合ってればいいので，ここは全部試す．残りの桁は，小さいものから順に上に詰める．leading zero がある場合は上の方で swap ．これだと 8 で割れる保証が無いけど，どうせ線形時間かかってるので普通にチェックする

2017-09-14 02:03:34

しさし @shisashi

ちょっと遅れたけどCSA出た。Eわからんちん。Cで2WAしたときは泣きそうになった。

2017-09-14 02:03:55

とーらす🌸📦🌕✨🍀 @torus711

やったこと　D: 左の点から見ていくと，同じ X 座標からは高々一つ，Y 座標は狭義単調増加になるように点を選んでいくことになる．最後に選んだ Y 座標をキーにする DP を考えると区間和か区間加算が出てくるので，そういう Segment Tree に乗せると速くなって間に合う

2017-09-14 02:05:27

kuuso @kuuso1

csaお疲れさまでした． E分からな過ぎてwindonws更新した．

2017-09-14 02:06:45

olphe @_olphe

@ei1333 なんで転倒数と結びつくのか教えてください…

2017-09-14 02:07:00

kmjp @kmjp_pc

Eは有向グラフのオイラーパスライブラリを持っていなかったので、Spagetti Sourceを参考に無向グラフ版を改造してた。これで最速だったのはちょっと意外。

2017-09-14 02:08:31

kuuso @kuuso1

Dはdp[now]：nowが最も右下になる集合の数：をY座標の大きい方から埋めていく．BIT使う．まさかのBIT内のmodの取り間違いで1WA．

2017-09-14 02:09:17

いま話題のタグ