ABCD の 4 完。D は DFS じゃ TLE やろなと思ったら普通に通ったからじゃあ E は Seg 木か～と思ったら全然通らなかった。計算量とか分からん・・・俺は雰囲気でコードを書いている・・・ #abc441
1
0
1
0
Hashtag
#abc441
Advertisement · 728 × 90
#ABC441 3問解けました
3
0
0
0
#ABC441
5完でした
A: P≤X<P+100∧Q≤Y<Q+100
B: 各言語について単語の全ての文字がその言語で使用される文字に含まれるかを確認
C: 最も不利な状況を想定して貪欲法を用いる
D: 探索範囲が少ないので愚直にDFSを行う
E: 接頭辞を伸長させつつ現時点の接頭辞から取り除くことができるより短い接頭辞の個数を数える。(Aの出現数)-(Bの出現数)の各値の個数をFenwickTreeで管理することで差分の範囲を絞り込んでカウントできる。
F: 値段の合計の上限に対する価値の合計の最大値についてのDPを左右から行い、商品iを含む場合と含まない場合の価値の合計の最大値を比較
4
0
0
0
#ABC441 メモ
ABCDEF(1) 6完 1ペナ 80:34
お前はまだ遅延セグ木を知らない。
A:p <= x < p+100 か？
B:一文字ずつ照らし合わせてみる。
C:デカい順に飲む。大きい順に(n-k)個がハズレと仮定してシミュレート。ハズレを飲み切ってから加算。
D:高々4^10パターンしかないのでやってみる。
E:(Aの個数)ー(Bの個数)を記録。これまでに(Aの個数)ー(Bの個数)未満だった回数だけ加算。
F:まずはDP。その後復元。上にしか上がれないならC,左にしか行けないならA。どっちもならB。
G:どうせ、すごい遅延セグ木なんだろ。
2
0
1
0
#ABC441
ぞい！！！
2
0
0
0