e-mon

備忘録

Topcoder SRM #660 Div2

結果から言えば惨敗だった.通ったとおもっていたeasy,med,hardすべてが落ちていた.反省を込めて詳細を書く.

Easy : Cyclemin

問題 : http://community.topcoder.com/stat?c=problem_statement&pm=13814

問題概要

文字列sと,数字kが与えられる.sの文字を右へシフト,押し出された文字を左へ持ってくるローテーションを任意の回数行う,k文字を任意の文字に置き換えるという操作を行い辞書順最小の文字列を作成する問題.

解法

ローテーションしてk文字'a'に入れ替えるだけ.

反省

読解力が死んでいた問題.ローテーション = 入れ替えだと思っていて,中央を中心とした入れ替えで考えていた名残がソースコードに混入しておりシステムテストで落ちた.

class Cyclemin:
    def bestmod(self, s, k):
        ans = s
        length = len(s)
        for i in range(length):
            _s = list(s[-i-1:] + s[0:-i-1])
            count = k
            for i in range(length):
                if count == 0:
                    break
                if _s[i] != 'a':
                    _s[i] = 'a'
                    count -= 1
            ans = min(ans,''.join(_s))
        
        return ans

Med : PrivateD2party

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13804

問題概要

PiさんはPjさんが嫌いであるという情報が与えられる.Pjさんがパーティに先に参加を表明していた場合Piさんは参加を拒否するので,Piさん -> Pjさんの順番で誘わなければならない.n人の参加者情報が与えられ,最適な順番でパーティに招待したときの最大数.

解法

木を考えて,基本的には葉から誘っていけば全員参加可能.嫌いである関係を矢印であらわすと,Pi → Pj,Pj → Piのような場合はどちらかしか誘うことが出来ない.つまり,ループがある場合はループに属する人間の内一人だけ参加出来ないことになるので,ループの数をカウントし全体の人数から引けばよい.

反省

提出時は,どこが葉かわからないので,dfsで訪問済みを管理するための配列と,招待済みかを管理するための配列を用意して,次に訪問するのが訪問済み且つ招待済みであれば未招待,訪問済みにする,という方法をとりループに対応,というつもりで書いて出した.だけどこの方法だと,複数の葉を持つ節のときにループと判断されるという物凄く初歩的なミスをしてしまっていたのでシステムテストで落ちた.

class PrivateD2party:
    def getsz(self, a):
        visited = [-1 for i in range(len(a))]

        def dfs(v, ID):
            if visited[v] == ID and v != a[v]:
                return True
            if visited[v] != -1:
                return False
            visited[v] = ID
            return dfs(a[v],ID)

        ans = 0
        for i in range(len(a)):
            if visited[i] == -1 :
                ans += 1 if dfs(i,i) is True else 0
        return len(a) - ans

Hard : Powerit

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13802

問題概要

 p = 2^{k}-1, 1 \le N \le 10^{6}, 1 \le k \le 400, 2 \le m \le 10^{9}のとき, \sum_{n=1}^{N} {n^{p}\mod m} を求める問題.

解法

pが2の累乗-1になるので,k回自乗してmodをとればよい.しかし,それだと,4*10^{8}になるのでC++でもTLEのようだ.ある合成数Cを考える. C^{p}というのは,素因数のp乗の積で表せるので,素数のp乗だけ求めておけばあとは合成数の素因数を求めるだけで計算出来る.106以下の素数は80,000くらいなので,篩の計算量O(NloglogN)になるはず.

反省

これはもう本当にひどくて,ダブリングで実装したpow_mod関数でなんとかなるとおもってとりあえず通してしまった.実際にやってることはk回自乗とまったく一緒になるので( 2^{k}-1だから)普通にTLEな上,pの値の計算も間違っているという酷い有様だった.ちゃんと問題を読んでしっかり考えるようにしたい.

下記のコードでは,先に篩で素数判定した後テーブルの素数部分だけ埋めてから,素数のループで合成数テーブルを計算するようにしている.二度,三度手間っぽいソースなので見直したい.

vector<bool> sieve_of_erastosthenes(int N){
    vector<bool> isPrime(N,true);
    isPrime[0] = isPrime[1] = false;

    for(int i = 2;i*i<N;i++){
        if(!isPrime[i]) continue;

        for(int j = i*i;j<N;j+=i)
            isPrime[j] = false;
    }
    return isPrime;
}

ll pow_mod(ll x, int count, int mod){
    ll ret = 1;
    for(int i = 0;i < count;i++){
        ret = (ret*x)%mod;
        x = (x*x)%mod;
      }
    return ret;
}

class Powerit {
    public:
    int calc(int n, int k, int m) {
        auto table = sieve_of_erastosthenes(1e6+1);
        vector<ll> dp(1e6+1,1);
        FOR(i,1,1e6+1){
            if(table[i])
                dp[i] = pow_mod(i,k,m);
        }

        ll ans = 0;
        FOR(i,1,n+1){
            if(table[i] && i <= sqrt(n)){
                for(int j = i*i;j<=n;j+=i){
                    dp[j] = (dp[i]*dp[j/i])%m;
                }
            }
            ans = (ans + dp[i])%m;
        }

        return ans;
    }
};