pitsuの精進日記

精進の様子を垂れ流しています

今日の精進 2020/06/03

Educational Codeforces Round 57バチャ

ABCDの4完

A:l,l*2を出力

B:左端、右端の連続アルファベットだけに注目

同じなら(左の連続数+1)*(右の連続数+1)

異なるなら(左の連続数+1)+(右の連続数+1)-1

右と左どこで区切るかみたいなことを考えると数え上げしやすかった

C:式とか図をいじいじしたら正n角形は180/n *(1,2,....,n-2)の角度を作れることがわかったので全探索

n = 180のときに178度まで存在してて179度はn = 360のときにできるらしいので計算量大丈夫

D:名前出したら警察がくるDP

dp[i][4]で0は何も持ってない、1はh持ち、2はha持ち、3はhar持ちのイメージで遷移

https://codeforces.com/contest/1096

 

 

青~黄diffバチャ

1完

A:joeチャンネルで出た問題だったので解法覚えてた

式変形するとS[r] - r*K >= S[l] - l*Kを満たすペアの数を探せばよくて

set使って座圧した後にBITを使って条件満たすものを数え上げる

https://kenkoooo.com/atcoder/#/contest/show/e749c884-d16b-482a-a603-5e9df223a3b8

 

 

復習

最小値がmidを上回ってるかどうかで二分探索

highがokライン、lowがngライン

midがokならok側の領域を減らしたいのでok=mid

上回ってるなら移動できる

確認はBFSで移動していけば大丈夫

atcoder.jp