SRM599,646-649 Div1E

ついにSRM Div1E埋め50問!問題はタメになる気がするんだけど,なんかある回のRoomに入れなかったりどうしても不便な所が多いので一旦別のコンテストをやろうかな.

 ・SRM599 Div1E BigFatInteger

はじめX=1である.このXに対し以下の操作ができる.

・ある素数pを選び,Xにかける

・Xの約数dを選び,Xにかける

このとき最小何回の操作でXをA^Bに出来るか?という問題.

Aを素因数分解すると,A^Bを素因数分解したときに現れる素因数と,各素因数の指数がわかる.まず現れる全ての素因数を1つ目の操作でXにかける.次に,2番目の操作を用いて指数を二倍にしていけるのを利用すると,各素因数について最小何回操作すれば目的の指数に出来るかがわかる.で,各素因数に対する操作は同時に行えるので,そのうち最大のものと最初の操作の回数を足したものが答え.

ソースコード

typedef long long LL;
typedef pair<int,LL> P;
class BigFatInteger {
    public:
    int minOperations(int A, int B) {
        vector<P> v;
        for (int i = 2; i <= A; i++) {
            if (A%i != 0) continue;
            int cnt = 0;
            while (A%i == 0) {
                A /= i;
                cnt++;
            }
            v.emplace_back(i, cnt*B);
        }
        int ans = v.size();
        int M = 0;
        for (int i = 0; i < v.size(); i++) {
            int j = 0;
            LL k = 1;
            LL tmp = v[i].second;
            while (tmp > 1) {
                tmp /= 2;
                j++;
                k *= 2;
            }
            if (v[i].second != k) j++;
            M = max(M, j);
        }
        ans += M;
        return ans;
    }
};

・SRM646 Div1E TheConsecutiveIntegersDivOne

長さnの数列がある(全ての要素は相異なる).このうち一つの要素を選んでインクリメントまたはデクリメントする操作ができる.この数列にk個の連続する整数(a,a+1,...,a+k-1)が含まれるようにするには,最小何回操作すればよいか?という問題.

まず数列を昇順にソートしておく.操作回数が最小になるのは,ソート後の数列で並んでいるk個の整数が連続するようにするとき.さらにかんがえると,並んでいるk個の整数のうちどれか一つはそのままにしておくとしてよいことがわかる.すると,その数を基準にして,各数に対してどれだけ操作しなければいけないかが求まるので終わり.

ソースコード

class TheConsecutiveIntegersDivOne {
    public:
    int find(vector<int> numbers, int k) {
        int n=numbers.size();
        sort(numbers.begin(),numbers.end());
        int ans=1<<30;
        for(int i=0;i+k<=n;i++) {
            for(int j=0;j<k;j++) {
                int sum=0;
                for(int l=0;l<k;l++) {
                    sum+=abs(numbers[i+j]+(l-j)-numbers[i+l]);
                }
                ans=min(ans,sum);
            }
        }
        return ans;
    }
};

・SRM647 Div1E BuildingTowersEasy

1列に並んだn個のビルを建設したい.ただし左端のビルの高さは0で,隣り合うビルの高さの差は高々1でないといけない.また,いくつかのビルについては,その高さの上限が定まっている.このとき,ビルの高さの最大値を求めよ.という問題.

AtCoderか何かで見たなあという気持ち.あるビルの高さの上限が与えられると,隣り合うビルの高さの差が高々1ということから,他の全てのビルについても上限が定まる.全てのビルについて高さの上限がわかったら,その上限を満たす中でなるべく大きくしたいので(次のビルの高さ)=max(今のビルの高さ+1,次のビルの高さの上限)というように更新していけばあり得る最大の高さがわかる.

ソースコード

class BuildingTowersEasy {
    public:
    int maxHeight(int N, vector<int> x, vector<int> t) {
        int now=0;
        int ans=0;
        for(int i=1;i<N;i++) {
            int nxt=now+1;
            for(int j=0;j<x.size();j++) {
                nxt=min(nxt,t[j]+abs(x[j]-(i+1)));
            }
            now=nxt;
            ans=max(ans,now);
        }
        return ans;
    }
};

・SRM648 Div1E AB

各文字がAまたはBであるような長さnの文字列Sであって,i<jかつS[i]=='A'かつS[j]=='B'を満たすようなペア(i,j)の個数がちょうどKであるようなものは存在するか.存在するなら具体例を,存在しないなら""を答えよ.という問題.

何故かPractice Roomに入ろうとすると固まるのでやる気を失くしたが,アルゴリズムはわかった.まずn文字のうち半分をA,もう半分をBにしてAA...ABB...Bのように並べたときが最もペアの数が多くなることがわかるので,A,Bの文字数は半分ずつにする.次に,BB...BAA...Aと並べたときはペアの数が0で,左からk個目のAのうしろにBを1個うつすとペアをk個増やせることがわかる.これより,Aの個数をaとしたときK/A個のBをAA...Aのうしろに移し,左からK%A番目のAのうしろにBを1個移すとペア数をKに出来ることがわかる.

・SRM649 Div1E Decipherability

長さK以上の文字列sが与えられる.sのうちどのK文字を消した文字列が与えられたとしても,消された文字がsの何番目の文字かが一意に定まるかどうか判定せよ.という問題.

ある文字xがあってs="(文字列)x(文字列)x(文字列)"というようになっているとき,(真ん中の文字列の長さ)+1≦Kなら真ん中の文字列とどちらかのxを消すことで同じ文字列が出来てしまい,どの文字を消したか一意に定まらないことがわかる.よって,全ての同じ文字のペアについてその文字間の距離を求めることで判定が可能.

ソースコード

class Decipherability {
    public:
    string check(string s, int K) {
        int n=s.size();
        if(n==K) return "Certain";
        int mv=1<<30;
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                if(s[i]!=s[j]) continue;
                mv=min(mv,j-i);
            }
        }
        if(mv<=K) return "Uncertain";
        return "Certain";
    }
};