SRM631-634 Div1E

35問目まで来た

 ・SRM631 Div1E TaroJiroGrid

大きさN×Nのグリッドがあって各マスは白か黒で塗られている.ある行を選んで全てのマスを黒か白で塗る操作が出来る.同じ色のマスがN/2個より多く並んでいるような列がないようにしたい.最小で何回の操作をすればよいか?という問題.

まずボードの真ん中に黒の行と白の行を並べれば絶対に同じ色のマスがN/2個より多く並ぶことはないので答えは高々2.答えが0になるのは最初からそのような列がないとき.答えが1になるのはどこか1行を黒か白で塗るとそのような列がなくなるときなので,全探索してやればいい.

ソースコード

class TaroJiroGrid {
    public:
    bool ok(vector<string> &grid,int n) {
        for(int x=0;x<n;x++) {
            int len=1;
            for(int y=1;y<n;y++) {
                if(grid[y][x]==grid[y-1][x]) {
                    len++;
                }else {
                    if(len>n/2) return false;
                    len=1;
                }
            }
            if(len>n/2) return false;
        }
        return true;
    }
    int getNumber(vector<string> grid) {
        int n=grid.size();
        if(ok(grid,n)) return 0;
        string tmp,B=string(n,'B'),W=string(n,'W');
        for(int y=0;y<n;y++) {
            tmp=grid[y];
            grid[y]=B;
            if(ok(grid,n)) return 1;
            grid[y]=W;
            if(ok(grid,n)) return 1;
            grid[y]=tmp;
        }
        return 2;
    }
};

・SRM632 Div1E PotentialArithmeticSequence

n個の整数からなる数列Aがあり,i番目の整数を2進法で表すと末尾にa[i]個の0が並ぶことがわかっている.このときAの連続する区間であって,その区間に含まれる数が公差1の等差数列をなす可能性があるようなものはいくつ存在するか?という問題.

一応注意しておくと,ある数を2進法で表したとき末尾にx個の0が並ぶとは,その数が2^xの倍数であって2^(x+1)の倍数でないことを意味する.これを"ちょうど"2^xの倍数だと表現する.区間[l,r]に含まれる数が公差1の等差数列をなす可能性があるかの判定をかんがえよう.ちょうど2^xの倍数である数にちょうど2^yの倍数である数を足すと何がおこるか.x=yならば2^(x+1)の倍数になり,x≠yならばちょうど2^min(x,y)の倍数になる.したがって[l,r]に含まれる任意の二数i,j(i<j)について,j-iがちょうど2^kの倍数であるとき「a[l]=kかつa[r]≧a[l]+1」または「a[l]≠kかつa[r]=min(a[l],k)」が成り立たなければならない.これを調べればよい(隣り合う二数の偶奇は異なるからa[l]>0ならa[l+1]=0だな,とかかんがえてそれを拡張していくと気づける).

ソースコード

class PotentialArithmeticSequence {
    public:
    int numberOfSubsequences(vector<int> d) {
        int n=d.size();
        int ans=n;
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                bool ok=1;
                for(int k=i;k<j;k++) {
                    for(int l=k+1;l<=j;l++) {
                        int t=0;
                        int len=l-k;
                        while(len%2==0) {
                            len/=2;
                            t++;
                        }
                        if((d[k]==t && d[l]<t+1)||(d[k]!=t && d[l]!=min(d[k],t))) {
                            ok=0;
                            break;
                        }
                    }
                    if(!ok) break;
                }
                if(ok) ans++;
            }
        }
        return ans;
    }
};

・SRM633 Div1E PeriodicJumping

n個の正整数があり,i番目の数はlen[i]である.点(0,0)から点(x,0)までジャンプしていく.i回目のジャンプでは長さlen[i%n]だけ任意の方向にジャンプできる.最小何回のジャンプで辿り着けるかを求めよ(辿り着けない場合は-1と答えよ)という問題.

決められた規則でジャンプしていってある点からある点まで行く問題はあるあるだが,自由度が高すぎてさっぱりわからなかった.いくつかの線分をつなぎあわせて(0,0)から(x,0)まで結んだとき,(0,0)と(x,0)を結ぶ線分と合わせて多角形ができる.よってすでに長さxの線分が一つ与えられていて,順番に線分を追加していくとき最小何回で多角形が作れるのかを調べればいいことになる.多角形の成立条件は(最も長い線分の長さ)×2≦(全ての線分の長さの和)である(全ての線分が一直線上にあるときは多角形とは言えないがこの問題では仲間にいれられる).x≧Σlen[i]ならばxが最も長い線分なので単に条件を満たすまで線分を追加していけばいい(割り算を用いると高速に計算できる).x<Σlen[i]のとき,どの線分が最長かはわからないが,すくなくとも2周するまでには条件を満たすのでこれもシンプルに調べてやればよい.

ソースコード

class PeriodicJumping {
    public:
    int minimalTime(int x, vector<int> jumpLengths) {
        if(x==0) return 0;
        int n=jumpLengths.size();
        x=abs(x);
        LL sum=0;
        for(int j:jumpLengths) sum+=j;
        int ans=0;
        if(sum<=x) {
            ans+=(x/sum)*n;
            x%=sum;
            int i=0;
            while(x>0) {
                x-=jumpLengths[i];
                i++;
                ans++;
            }
        }else {
            int maxL=x;
            LL sumL=x;
            for(int i=0;i<2*n;i++) {
                sumL+=jumpLengths[i%n];
                maxL=max(maxL,jumpLengths[i%n]);
                ans++;
                if(sumL>=maxL*2) break;
            }
        }
        return ans;
    }
};

・SRM634 Div1E ShoppingSurveyDiv1

m個の異なるものがあり,n人の人が来てそれらのうちいくつかのものを買った(同じものを2個以上買うことはなく,何も買わなくてもよい).i番目のものを買った人がs[i]人であることがわかっている.このときk個以上のものを買った人の数としてかんがえられる最小の人数を求めよ,という問題.

k個以上のものを買った人がx人以下であることがあり得るかという判定問題をかんがえるとにぶたんが出来そう.k個以上のものを買った人をx人以下にするには,あるx人を選び,s[i]≦xであるようなものに関しては全てこれらの人が買ったことにして無視し,s[i]>xであるようなものに関しては,のこりのn-x人のうちs[i]-x人が買ったことにするのがよい.n-x人のうち誰もk個以上買ってはいけないので上手くならして分配すると,(n-x)×(k-1)個までは収められることがわかる.従ってΣmax(s[i]-x,0)≦(n-x)(k-1)ならOKと簡単に判定できる.

ソースコード

class ShoppingSurveyDiv1 {
    public:
    int minValue(int N, int K, vector<int> s) {
        int l=-1,r=N;
        while((r-l)>1) {
            int m=(l+r)/2;
            int sum=0;
            for(int e:s) sum+=max(e-m,0);
            if(sum<=(N-m)*(K-1)) r=m;
            else l=m;
        }
        return r;
    }
};