SRM510 Div2 Medium - TheLuckyGameDivTwo
問題
全ての桁が4か7の数字をLuckyNumberと呼ぶ
区間[a,b]からまずJohn君が長さalの区間Sを取り出し、次にBrus君がSから長さblの区間Tを取る
Tに含まれるLuckyNumberの個数をゲームのスコアとする
John君はスコアを最大化、Brus君は最小化しようとするときスコアは何点になるか
解法
John君がある区間を選んだとき、そこからBrus君は長さblの区間でLuckyNumberが一番少ない区間を選ぶ
ということはJohn君はどこを選んでもLuckyNumberがなるべく多いような区間を取るべき
つまり最小値の最大値を求めればいい
John君の区間Sを全探索し、それぞれについてBrus君の区間Tを全て試してそれらの最小値を求める
それらの最小値の最大値が答えになる
実装
累積和をとって、ある区間に含まれるLuckyNumberの個数をO(1)で求められるようにしておく
(累積和かしゃくとり法のどっちかは使わないとb-a=4444, al=2222, bl=1111なんかが怪しい)
class TheLuckyGameDivTwo { public: int find(int a, int b, int al, int bl) { int k[5050] = {}; reps(i,1,5050) { int t = i, ok = 1; while (t) { if (t%10!=4 && t%10!=7) ok = 0; t /= 10; } k[i] = k[i-1] + ok; } int res = 0; rep(i,b-a-al+2) { int mn = 114514, l = a+i, r = l+al-1; rep(j,r-l-bl+2) { int ll = l+j, rr = ll+bl-1; chmin(mn, k[rr]-k[ll-1]); } chmax(res, mn); } return res; } };