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

AOJ 文字列

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

AOJ 二分法

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

AOJ

センター試験まで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");
    }
}

2015-01-03

SRM 644 div 1

SRM

あけましておめでとうございます
するめは新年早々、unratedだった

easy
はじめにソートする
尺取りみたいに見て、osize[i]-osize[j]>Kとなった瞬間に(j-i-1)C(M-1)を答えに加算する(osize[i]を最小のお好み焼きとして必ず選ぶときのありえる組合せの数)
組合せの計算はライブラリにしてあったのでコピペするだけだった

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define IDX(v,a) distance(a.begin(),lower_bound(a.begin(),a.end(),v))
typedef long long ll;
const ll MOD = 1000000007;
typedef pair<int,int> P;
ll mod_pow(ll a, ll n){
	ll ret = 1;
	ll t = a;
	while(n){
		if(n&1)
			ret = ret * t % MOD;
		t = t * t % MOD;
		n >>= 1;
	}
	return ret;
}

ll mod_comb(ll N, ll K){
	ll nPk = 1 , kfact = 1;
	for(ll i = N; i > N - K; i--)
		nPk = nPk * (i % MOD) % MOD;

	kfact = 1;
	for(ll i = 2; i <= K; i++)
		kfact = kfact * i % MOD;

	kfact = mod_pow(kfact, MOD - 2);
	return ((nPk * kfact) % MOD);
}
class OkonomiyakiParty{
public:
    int count(vector <int> osize, int M, int K){
        int N = osize.size();
        ll ans = 0;
        sort(osize.begin(), osize.end());
        int j = 0;
        for(int i = 0; i < N; i++){
            for(j = i+M-1; j < N; j++){
                if(osize[j] - osize[i] > K) break;
            }
            if(j-i>=M){
                ll t = mod_comb(j-i-1,M-1);
                printf("%d %d c=%lld\n", i,j,t);
                ans += t;
                ans %= MOD;
            }
        }
        return (int)ans;
    }
};

2014-12-12

SRM 641 div1

SRM TopCoder 幾何

easy
頂点を4つの象限で分類して（軸は適当に含める）考えると、原点を内部に含む三角形は次の二つのうちいずれかを満たすことに気づく。
(1)頂点が向かい合う二つの象限（または軸の上）にある
(2)頂点が三つの象限（または軸の上）にある

(1)について、ある象限の一つの頂点に注目して向かい合う象限の点に線分を引いたとき、y切片が正であるものの個数をu、負であるものの個数をvとすると、注目した頂点を含みかつ他の2頂点が向かい合う象限にある三角形の個数はuv個である。
これを各象限の各頂点について計算すると(1)を満たす三角形の個数が求まり、この計算量はO(n^2)

(2)について、向かい合う２つの象限の頂点の組による線分のy切片が正か負かで、残り一つの頂点がどの象限に属するかが決まる。またその象限の頂点ならどの頂点でも原点を含む三角形となるから、その象限に含まれる点の個数が「向かい合う２つの象限の頂点の組」に対する作りうる三角形の個数となる。
計算量はO(n^2)

(1)(2)をそれぞれ計算して和をとればよくて全体の計算量もO(n^2)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define IDX(v,a) distance(a.begin(),lower_bound(a.begin(),a.end(),v))
typedef long long ll;
typedef pair<int,int> P;

class TrianglesContainOrigin{
public:
	long long count(vector <int> x, vector <int> y){
        int n = x.size();
        long long ans = 0;
        vector<int> num[4];
        for(int i = 0; i < n; i++){
            if(x[i] >= 0 && y[i] > 0)
                num[0].push_back(i);
            if(x[i] > 0 && y[i] <= 0)
                num[1].push_back(i);
            if(x[i] <= 0 && y[i] < 0)
                num[2].push_back(i);
            if(x[i] < 0 && y[i] >= 0)
                num[3].push_back(i);
        }
        for(int k = 0; k < 4; k++){
            int l = (k+2)%4;
            for(int i = 0; i < num[k].size(); i++){
                int s = num[k][i];
                long long xs = x[s], ys = y[s];
                long long u=0, v=0;
                for(int j = 0; j < num[l].size(); j++){
                    int t = num[l][j];
                    long long xt = x[t], yt = y[t];
                    if((xs*yt-xt*ys) * (xs-xt) > 0){
                        u++;
                    }else{
                        v++;
                    }
                }
                ans += u*v;
            }
        }
        for(int i = 0; i < num[0].size(); i++){
            int s = num[0][i];
            long long xs = x[s], ys = y[s];
            for(int j = 0; j < num[2].size(); j++){
                int t = num[2][j];
                long long xt = x[t], yt = y[t];
                if((xs*yt-xt*ys) * (xs-xt) < 0){
                    ans += num[3].size();
                }else{
                    ans += num[1].size();
                }
            }
        }
        for(int i = 0; i < num[1].size(); i++){
            int s = num[1][i];
            long long xs = x[s], ys = y[s];
            for(int j = 0; j < num[3].size(); j++){
                int t = num[3][j];
                long long xt = x[t], yt = y[t];
                if((xs*yt-xt*ys) * (xs-xt) > 0){
                    ans += num[2].size();
                }else{
                    ans += num[0].size();
                }
            }
        }
        return ans;
	}
};