CSA #83 (Div. 2 only)

nmnmnmnmnmnmnm @enuemuenuemuenu

A:数え上げ B:全探索(いくつの要素まででMの個数を満たすか？) C:セグメント木と2分探索 D:BIT E:読んだだけ

agw @masashinakata

今日のC問、多分こどふぉとかで何回もやってて自分的には典型だと思うんだけど、脳に染み込まないのはどうしたらいいんだろう...?

hogeover40 @hogeover30

1555 → 1593　Highest更新

nmnmnmnmnmnmnm @enuemuenuemuenu

100位台前半だけど400人くらいしか出てないから良い結果とはいけないかもしれません。寝る。

agw @masashinakata

ぱっと見でこれは難しい! と感じてしまってD問題に行ってしまった

Hideyuki Tanaka @tanakh

やったー(´･_･`) pic.twitter.com/nxpWKvkDHQ

拡大

Hideyuki Tanaka @tanakh

今回レートが121上がったらしいから頑張って赤にしていきたい(´･_･`)

やざてん @Yazaten

CSA A: 計算でできそうだけど思いつかず、|S|^36通り全部生成する全探索 B: 1~Mの和から、ai<=Mであるようなaiの和を引いたものをansとする。あとは引いた数だけM~1以上の数を適当にansに足してあげる。

やざてん @Yazaten

C: 地点Aから初めて地点Bで停止する移動があったとき、地点A~B間のどの地点から始めても地点Bより手前で停止するので、調べる必要のある区間はオーバーラップしない。よって前からしゃくとり風(?)にO(N)で全部試せる。

satanic@研究💪 @satanic0258

Bなんでわざわざにぶたんしたんだろうと今になって思っている

やざてん @Yazaten

D: 長方形の縦の長さYを決めてあげると自然に横幅Xも決まる(X=floor(A/Y))。今見ている長方形に含まれる頂点達をsetに入れたり消したりすることで管理しながら、Yを1~1e6まで変化させれば最大値が求まる。

やざてん @Yazaten

V字回復(？） pic.twitter.com/r1ruWuGTQS

拡大

hogeover40 @hogeover30

CSAのレーティンググラフ pic.twitter.com/4Zepz9TJ1E

拡大

hogeover40 @hogeover30

おわかりいただけただろうか pic.twitter.com/g8D1kBC6CO

拡大

やざてん @Yazaten

C++に詳しくないのでどなたか教えていただきたいんですが、setのrbegin()でもらったiteratorでset.erase()できないのって何故かわかりませんか？ ideone.com/kL69iv

Hideyuki Tanaka @tanakh

setのeraseに渡すiteratorはreverse_iteratorだとダメなんじゃないのかな…知らないけど…値で消せば消えるのでは s.erase(*s.rbegin())

てんぷら @tempura_cpp

1796->1778 ウケる、一生青コーダー

(nは自然数) @n_vip

なんでリバースイテレータのeraseが無いんだろう。できるでしょ。戻り値がリバースイテレータっぽくなるかもだけど

やざてん @Yazaten

@tanakh rbegin()で得られるiteratorって普通のiteratorとは違うんですね、知りませんでした。 確かに値で消せば消せました、ありがとうございます。

てんぷら @tempura_cpp

Cでハマったのがなぁ()

Hideyuki Tanaka @tanakh

C++の標準ライブラリで、普通に考えればできそうだけどやってないのって、C++の深遠なる闇にのみ込まれて消滅したものである可能性が巨レ存だしあんまり深く考えたくないすね…(´･_･`)

(nは自然数) @n_vip

途中までdeque使っててやっぱ(multi)setだなってなること多いし最大元の削除簡単に書きたいよなあ

Hideyuki Tanaka @tanakh

@Yazaten そうですねえ。解決したみたいで良かったです。他のコンテナとかでも違う型だったりすることが多いので注意が要りますね。

(nは自然数) @n_vip

@Yazaten インクリメントしたときにイテレータと違う方に行くのは知ってますか

NATSUGIRRRRI @natsugir

se.erase(it.base()) では