Hatena::ブログ(Diary)

sndrのブログ

2015-04-26

SA-ISを実装した

https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf を読んで実装した。
まだverifyしていないので正しいか知らない。
[追記4/28]
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620 でverifyしました
[さらに追記]
verifyは通ったけど実は微妙にバグっているかもしれないことが判明した

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

// SAIS(s,n)
// s is a string; n is the length of s (except null character)
// return SA of s
const bool typeS = true;
const bool typeL = false;
vector<int> SAIS(char *s, int n){
    n++;
    //count[i] := the number of characters whose Ascii code are i
    int count[256];
    memset(count, 0, sizeof(int)*256);
    for(int i=0;i<n;i++){ count[s[i]]++; }
    //Step 1
    //determine type and LMS
    vector<int> LMS;
    bool *t = new bool[n];
    t[n-1] = typeS;
    for(int i = n-2; i >= 0; i--){
        if(s[i] > s[i+1]){
            t[i] = typeL;
            if(t[i+1] == typeS)
                LMS.push_back(i+1);
        }else if(s[i] < s[i+1]){
            t[i] = typeS;
        }else{
            t[i] = t[i+1];
        }
    }
    //construct buckets
    vector<unsigned char> bucket;
    char char2bucketIdx[256];
    for(int c=0;c<256;c++){
        if(count[c] > 0){
            bucket.push_back(c);
            char2bucketIdx[c] = bucket.size()-1;
        }
    }
    //put LMS into bucket
    vector<int> SA(n);
    fill(SA.begin(), SA.end(), -1);
    int *index = new int[bucket.size()];
    index[0] = 1;
    for(int b = 1; b < bucket.size(); b++){ index[b]=index[b-1]+count[bucket[b]]; }
    for(int l = LMS.size()-1; l >= 0; l--){
        int i = LMS[l];
        int idx = char2bucketIdx[ s[i] ];
        SA[index[idx]-1] = i;
        index[idx]--;
    }
    //Step2
    //scan from left to right and determine SA of typeL-substrings
    index[0] = 0;
    for(int b = 1; b < bucket.size(); b++){ index[b]=index[b-1]+count[bucket[b-1]]; }
    for(int i = 0; i < n; i++){
        int j = SA[i];
        if(j <= 0) continue;
        if(t[j-1] == typeL){
            int k = char2bucketIdx[s[j-1]];
            SA[index[k]] = j-1;
            index[k]++;

        }
    }
    //Step3
    //scan from left to right and determine SA of typeS-substring
    index[0] = 1;
    for(int b = 1; b < bucket.size(); b++){ index[b]=index[b-1]+count[bucket[b]]; }
    for(int i = n-1; i>=0; i--){
        int j = SA[i];
        if(j <= 0) continue;
        if(t[j-1] == typeS){
            int k = char2bucketIdx[s[j-1]];
            SA[index[k]-1] = j-1;
            index[k]--;
        }
    }

    return SA;
}

int main(){
    char s[] = "mmiissiissiippii";
    vector<int> SA = SAIS(s,16);
    for(int i = 0; i < SA.size(); i++){
        printf("%d ", SA[i]);
    }
    puts("");
}

2015-03-10

2015-01-12

AOJ 1152 Organize Your Train part II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1142&lang=jp
D言語らしいコードが書けた
mutableじゃないとreverseできない(当たり前)とかimmutableだと~が使えない(なんでだろう?)で引っかかった
例えば,下の解答の一部で

char[] v = str[0..i].dup;
char[] u = str[i..$].dup;
ans[v~u] = true;

とするとコンパイラに怒られる.

以下解答

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
void main(){
    for(int m = to!int(chomp(readln())); m>0; m--){
        bool[string] ans;
        string str = chomp(readln());
        for(int i = 0; i <= str.length; i++){
            char[] v = str[0..i].dup;
            char[] u = str[i..$].dup;
            string w = v.idup;
            string x = u.idup;
            string y = v.reverse.idup;
            string z = u.reverse.idup;
            ans[w~x] = true;
            ans[x~w] = true;
            ans[y~z] = true;
            ans[z~y] = true;
            ans[w~z] = true;
            ans[y~x] = true;
            ans[z~w] = true;
            ans[x~y] = true;
        }
        writeln(ans.length);
    }
}

[追記]
連想配列の添字はimmutableでないといけないことを教えていただきました

2015-01-11

AOJ 2317 Class Representative Witch

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317
二分探索。場合分けを冷静にしてオーバーフローに気をつける

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.typecons;
int abs(int a){
    if(a<0) return -a;
    return a;
}
//valを超えない最大のvec[i]を求めiを返す
int search(int[] vec, int val){
    int l = 0, h = to!int(vec.length);
    while(true){
        if(l+1 == h) break;
        int m = (l+h)/2;
        if(vec[m]<=val){
            l = m;
        }else{
            h = m;
        }
    }
    return l;
}
void main(){
    int[] input = array(map!(to!int)(split(readln())));
    int N=input[0],M=input[1];
    int[] p = new int[M+2];
    Tuple!(int,int)[] xs;
    foreach(i; 0..N){
        input = array(map!(to!int)(split(readln())));
        xs ~= tuple(input[0],input[1]);
    }
    p[0] = 0; p[M+1] = 1234567890;
    foreach(i; 1..M+1){
        p[i] = to!int(chomp(readln()));
    }
    sort(p);
    int[] q = new int[M+2];
    int[] r = new int[M+2];
    q[0] = 0;
    r[0] = p[0];
    for(int i = 1; i < M+2; i++){
        if(i%2==0){
            q[i] = q[i-1] + p[i]-p[i-1];
            r[i] = r[i-1];
        }else{
            r[i] = r[i-1] + p[i]-p[i-1];
            q[i] = q[i-1];
        }
    }
    //writeln(p);
    //writeln(q);
    //writeln(r);
    ulong ans = 0;
    foreach(i; 0..N){
        int s = xs[i][0];
        int t = xs[i][1];
        int si = search(p,s);
        int ti = search(p,t);
        int w = abs(s-t);
        if(s < t){
            if(si%2 == 0){
                if(ti%2 == 0){
                    w -= q[ti] - q[si];
                }else{
                    w -= q[ti] - q[si] + t - p[ti];
                }
            }else{
                if(ti%2 == 1){
                    w -= r[ti] - r[si];
                }else{
                    w -= r[ti] - r[si] + t - p[ti];
                }
            }
        }else{
            if(si%2 == 0){
                if(ti%2 == 0){
                    w -= q[si] - q[ti];
                }else{
                    w -= q[si] - q[ti] - t + p[ti];
                }
            }else{
                if(ti%2 == 1){
                    w -= r[si] - r[ti];
                }else{
                    w -= r[si] - r[ti] - t + p[ti];
                }
            }
        }
        //writeln("s=",s," t=",t," si=",si," ti=",ti," w=",w);
        ans += w;
    }
    writeln(ans);
}

2015-01-10

AOJ 2600 Koto Distance

センター試験まで1週間です。
気分転換に解いた
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2600
解法
imos法を使ってカバーできているかどうか調べる。
コーナーケースがあって、マスの辺はカバーできているけど中身がカバーできていないというケースがある。
そのためグリッドの幅、高さを2倍して内部も表すことができるようにする。

import std.stdio;
import std.string;
import std.algorithm;
import std.conv;
import std.range;

void main(){
    int N,W,H;
    int[] input = array(map!(to!int)(split(readln())));
    N = input[0];
    W = input[1];
    H = input[2];
    int[] Hb = new int[2*H+2];
    int[] Wb = new int[2*W+2];
    foreach(i; 0..N){
        int x, y, w;
        int[] xyw = array(map!(to!int)(split(readln())));
        x = 2*xyw[0];
        y = 2*xyw[1];
        w = 2*xyw[2];
        Hb[max(y-w,0)] += 1;
        Hb[min(y+w+1,2*H+1)] -= 1;
        Wb[max(x-w,0)] += 1;
        Wb[min(x+w+1,2*W+1)] -= 1;
    }
    bool f = true, g = true;;
    if(Wb[0] == 0) f = false;
    foreach(x; 1..(2*W+1)){
        Wb[x] = Wb[x-1] + Wb[x];
        if(Wb[x] == 0){
            f = false;
        }
    }
    if(Hb[0] == 0) g = false;
    foreach(y; 1..(2*H+1)){
        Hb[y] = Hb[y-1] + Hb[y];
        if(Hb[y] == 0){
            g = false;
        }
    }
    if(f || g){
        writeln("Yes");
    }else{
        writeln("No");
    }
}