SRM510 Div2Medium TheLuckyGameDivTwo

問題URL：TheLuckyGameDivTwo
Markdownが使いたくなったのでしばらく記事の見た目がぶれます。はてな記法とどっちがいいか、ｺﾚｶﾞﾜｶﾗﾅｲ

考察

範囲が1~4747と狭いので全探索できそう。
Johnはスコアが大きくなるように、Brusはスコアが小さくなるように、それぞれ範囲をとるというのがわかりにくい。こういう戦略最適化問題の場合、おおむね先手はエスパーなので、まずBrusの行動から考える。BrusはJohnの決めた範囲のうちスコアが小さくなるように、更に範囲を定める。つまり、Johnの各選択に対してスコアは一意に確定することがわかる。こうなると後は単純で、Johnはこの内スコアが最も大きくなる選択をすればいい。数学でやる1文字固定に近い。

実装

どうせラッキーナンバーは少ないので、2進数を列挙する感覚で全部書き出した。春に受講した、ひたすらカルノー図を書く授業を思い出してちょっと鬱になった。
Brusが全範囲の最小値を必死に探す中、Johnはそのうちの最大値を高みの見物で選ぶ。そんな主従関係が目に浮かぶと書きやすいですね。

#include <bits/stdc++.h>
using namespace std;
const int INF=1145141919;

class TheLuckyGameDivTwo {
public:
    int find( int a, int b, int jLen, int bLen ){
        int lucky[]={4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747};
        int num[5000]={}; for(auto i:lucky) num[i]=1;
        for(int i=1;i<5000;i++) num[i]+=num[i-1];
        jLen--; bLen--;

        int ans=0;
        for(int i=a;i+jLen<=b;i++){
            int bSum=INF;
            for(int j=i;j+bLen<=i+jLen;j++){
                bSum=min(bSum,num[j+bLen]-num[j-1]);
            }
            ans=max(ans,bSum);
        }
        return ans;
    }
};