はてなサマーインターンシップ2015に行ってきました

題目の通り，株式会社はてなのサマーインターンシップ2015に行ってきました．

hatenacorp.jp

インターンシップの流れについては，他のインターンシップ生が詳細を書いてくれているので， 僕は参加したアドテクコースについて書こうと思います．

アドテクコースとは？

今回のサマーインターンシップで初めて実施されるコース. 募集要項によると，

企業ブランドを毀損するサイトへの広告掲載を阻止する、アドベリフィケーションサービス「BrandSafe はてな」をはじめとした、はてなのアドテクノロジー関連事業の開発に取り組むコースです。広告主とインターネットユーザーをより良いかたちで引き合わせることを支援する事業領域にて、その改善に取り組んでいただきます。

• あると望ましいスキル

大規模データ処理、検索、自然言語処理、レコメンデーション、統計といった、アドテクノロジーに関連する領域のスキル

とありますが，僕自身今現在M1で，修士から自然言語処理や統計に興味を持ったレベルなので，今後申し込む方はそこまで気負うことはないかもしれません．

ただし，先に述べておくと，アドテクコースの性質上恐らく対象分野のサーベイや仮説の妥当性検証に比重が大きく偏ると思われるので，望ましいスキルに関わる最近の動向は追っておいたほうがいいと思います．（自戒の念を込めて）

取り組んだ課題

今回僕と，id:dagunikoくんとで取り組んだのは，はてなブックマークの特徴キーワード抽出精度の改善でした．

ブックマーク数の右にあるのが，エントリーページ本文中から抽出された特徴キーワードです．

苦労したこと

今回特に苦心したのが，評価をどうしたらいいのか，ということでした． このようなタスクは一意に正解が定まることが無いので，抽出された結果に対して特徴的かどうかを評価することが多いようです． ですが，今回時間も限られているということで，複数人で正解データを作成し，それに対するprecisionとrecallで評価していきました.
作成した正解データに対して過学習するのが怖いので，アルゴリズムをどのようにするかはとても悩みました・・．

個人的に新鮮で且つ頭を悩ませた要素が，実際に稼働しているサービスであるためオンラインで行える範囲の処理，という制約でした．
はてなブックマークは膨大な数のユーザーが日々利用するサービスであるため，これまで見たこともないような質と量のデータが存在します． これらを統計的に処理しようとすれば勿論オンラインでは処理出来ない時間がかかるので，いかにしてオフラインでやっておくかをひたすら悩みました．
これまで自分が行ってきた解析処理などは愚直にブン回してもたかだか数分自分が待つ程度のものだったので，多くのユーザーが画面の向こうにいる，ということを強く意識するきっかけとなりました．

感想

メンターさんに教えてもらった中で強く覚えているのは，「今何ができていなくて，それをどのように改善すればよいのか」を常に意識するということだった．
一見すると当たり前のことのように思えるのだけれど，一度自分の考えた方法にのめり込むとそれが何の解決をしてて実際にどれくらい解決出来そうかというのを 忘れがちになっていることがよくあって，そこでいつも足踏みをしていた気がする．
もっと精度改善できたとおもうし, まだまだ試してみたいことはあってかなり悔しい結果にはなったけど, とても多くのことを学んだと思う．

最後に，はてな社の皆さん，特にメンターをしていただいたid:skozawaさん，id:takuya-aさんには本当にお世話になりました.

余力があって且つ書いてもよさそうであれば，また今度実際に何をしたのかについてもうちょっと詳しく書こうと思う．

以下，軽く思い出を振り返っておきます.

• 初日の事故

インターン生に「kuromoji.js を開発した方が社員にいらっしゃるらしいですね！！」って言われたのが今日のハイライト。

— id:takuya-a (@takuya_a) 2015, 8月 10

初日から大事故を起こした感

— e-mon (@eemon18) 2015, 8月 10

• 猫穴

ネコ穴、よさしかなかったし絶対また行きたい。 pic.twitter.com/2eqRdlnHKe

— id:takuya-a (@takuya_a) 2015, 8月 31

スペースネコ穴、写真を見ても宅飲みにしか見えない pic.twitter.com/7VAbVYQIUn

— e-mon (@eemon18) 2015, 8月 31

• はてな社にあった心惹かれた便利マシーン情報

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の累乗-1になるので，k回自乗してmodをとればよい．しかし，それだと，になるのでC++でもTLEのようだ．ある合成数Cを考える．というのは，素因数のp乗の積で表せるので，素数のp乗だけ求めておけばあとは合成数の素因数を求めるだけで計算出来る．10⁶以下の素数は80,000くらいなので，篩の計算量O(NloglogN)になるはず．

反省

これはもう本当にひどくて，ダブリングで実装したpow_mod関数でなんとかなるとおもってとりあえず通してしまった．実際にやってることはk回自乗とまったく一緒になるので(だから)普通に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;
    }
};

CodeForces Round #303 Div2 E - Paths and Trees

問題 : http://codeforces.com/contest/545/problem/E

内容:

頂点 : , 辺 : から成る多重辺の無い無向グラフG(V,E)が与えられる．このとき，あるノードからの最短パスのみで構成される， コストの総和が最小の木を求めよ．

解法:

からの最短距離をとりあえず求めて，あるノードとその一つ前のノードとの距離が小さいエッジを集めていく方法で解いた． エッジそれぞれについてそのエッジを用いた場合の距離が最短距離であり且つ一つ前の頂点とのコストが小さいものをとっていく．

具体的には， dist[u] == dist[v] + w and w < dist[u] - dist[prev[u]] となるようなエッジを採用していく． 全体でとなりくらいの計算になるので，PyPyでは間に合わないみたい．

雑感:

C++に書き直して通りはしたけど，ソースは汚い上に筋が悪そう． 今回，コストが最大であることを忘れてintのまま計算を行っており相当WAを出してしまった．C++のソースの見通しが悪すぎるのでTLEになったPythonのコードも貼っておく．読みやすいコードが書けるようになりたい．

TLEになったPythonコード :

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from heapq import heappush, heappop
def dijkstra(adjList,s):
    num = len(adjList)
    dist = [10**10 for i in range(num)]
    prev = [-1 for i in range(num)]
    queue = []

    heappush(queue,(0,s))
    dist[s] = 0
    prev[s] = (0,-1)
    while queue != []:
        v_cost, v = heappop(queue)
        if dist[v] < v_cost:
            continue
        for u_cost, u, edge_no in adjList[v]:
            if u != v and u_cost + dist[v] < dist[u]:
                prev[u] = (v,edge_no)
                dist[u] = u_cost + dist[v]
                heappush(queue, (dist[u], u))
    return dist,prev

n,m = map(int,input().split())
adjList = [[] for i in range(n)]
edges = []
for i in range(m):
    u,v,w = map(int,input().split())
    u-=1
    v-=1
    adjList[u].append((w,v,i))
    adjList[v].append((w,u,i))
    edges.append((u,v,w))

s = int(input())-1
dist,prev = dijkstra(adjList,s)
idx = 0
for u,v,w in edges:
    if dist[u] == dist[v] + w and w < dist[u] - dist[prev[u][0]]:
        prev[u] = (v,idx)
    elif dist[v] == dist[u] + w and w < dist[v] - dist[prev[v][0]]:
        prev[v] = (u,idx)
    idx += 1

ans = 0
ans_edges = []
for node,idx in prev:
    if idx >= 0:
        ans += edges[idx][2]
        ans_edges.append(idx+1)
print(ans)
print(' '.join(map(str,sorted(ans_edges))))

通ったc++のコード:

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define INF 1e15

struct edge{
    int to;
    ll cost;

    bool operator>(const edge &e)const{
        return cost > e.cost;
    }

    bool operator<(const edge &e)const{
        return cost < e.cost;
    }
};

void dijkstra(vector<vector<pair<edge,int>> > &g, vector<ll> &dist, vector<pii> &prev, int s){
    priority_queue<edge, vector<edge>, greater<edge> > pq;

    fill(dist.begin(),dist.end(),INF);
    dist[s] = 0;
    prev[s] = (pii){0,-1};

    pq.push((edge){s,0});

    while(!pq.empty()){
        auto v = pq.top(); pq.pop();
        if(dist[v.to] < v.cost) continue;

        for(pair<edge,int> u:g[v.to]){
            edge next_v = u.first;
            if(next_v.to != v.to and next_v.cost + dist[v.to] < dist[next_v.to]){
                prev[next_v.to] = pii{v.to,u.second};
                dist[next_v.to] = next_v.cost + dist[v.to];
                pq.push((edge){next_v.to,dist[next_v.to]});
            }
        }
    }
}

int main(){
    int n,m;
    cin >> n >> m ;
    vector<vector<pair<edge,int>>> G(n);
    typedef tuple<int,int,int> tiii;
    vector<tiii> edges;
    FOR(i,0,m){
        int u,v,w;
        cin >> u >> v >> w ;
        u--;v--;
        G[u].push_back((pair<edge,int>{(edge){v,w},i}));
        G[v].push_back((pair<edge,int>((edge){u,w},i)));
        edges.push_back((tiii){u,v,w});
    }

    int s;
    cin >> s ;

    vector<ll> dist(n);
    vector<pii> prev(n);
    dijkstra(G,dist,prev,s-1);

    FOR(i,0,m){
        int u,v,w;
        tie(u,v,w) = edges[i];
        if(dist[v] == (dist[u] + w) && w < (dist[v] - dist[prev[v].first]))
            prev[v] = pii{u,i};
        if(dist[u] == (dist[v] + w) && w < (dist[u] - dist[prev[u].first]))
            prev[u] = pii{v,i};
    }

    ll ans = 0;
    vector<int> ans_edge;
    for(auto p : prev){
        int node,idx;
        tie(node,idx) = p;
        if(idx >= 0){
            int u,v,w;
            tie(u,v,w) = edges[idx];
            ans += w;
            ans_edge.push_back(idx+1);
        }
    }

    cout << ans << endl;
    sort(ans_edge.begin(),ans_edge.end());
    for(auto i:ans_edge)
        cout << i << " ";
    cout << endl;

    return 0;
}

CodeForces Round #304 Div2 E - Soldier and Traveling

問題 : http://codeforces.com/contest/546/problem/E

内容

nの町があり，それぞれの町はm個の辺で接続されている． 現在の町に存在するの兵士を同じ道を二度通らずに他の町に移動する,もしくは他の町から移動してくることでにしたい． 多重辺はないが，連結であるとは限らない．可能である場合はからへ何人移動したかを行列にして出力すること．

解法

各頂点への流入路を初期配置，流出路を最終配置として，新たにsourceとsinkを設けることでフロー問題に帰着させ解くということであった． 具体的には，まず頂点を移動前N個，移動後N個，source,sinkの2N+2個確保し，sourceから各頂点へ各A分のcapを設け，頂点から対応のある頂点へ容量を無限大としたエッジを張り，各頂点からsinkへ各B分のcapを設ける，という方法で解ける．

雑感

人数が足りているところと，不足しているところの対応を考える問題かなぁとぐちゃぐちゃコードを書いて結局解けなかった． yukicoderでも同様にして解く問題（あちらは明白に二部グラフだったけど）があったので．典型問題なのだろうか． 良い機会なので最大流問題に今後チャレンジ出来るようにライブラリの整備を行った． 最大流問題は，今回のようにうまいこと頂点の容量を辺の容量に変換,sourceとsinkを追加して二部グラフのフローとして解くような問題とかが良くでるようなので，他のパターンも含めて色々解いておきたい．

まだPythonしかできていないので，C++版も用意すること．(加えて，Dicnic法を追加すること)

class Ford_Fulkerson:
    class Edge:
        def __init__(self, to, cap, rev):
            self.to = to
            self.cap = cap
            self.rev = rev
        
        def __repr__(self):
            return "(to: {0} cap: {1} rev: {2})".format(self.to, self.cap, self. rev)

    def __init__(self,V):
        self.V = V
        self.size = [0 for i in range(V)]
        self.G = [[] for i in range(V)]

    def add_edge(self, _from, to, cap):
        self.size[_from]
        self.G[_from].append(self.Edge(to, cap, self.size[to]))
        self.G[to].append(self.Edge(_from, 0, self.size[_from]))
        self.size[_from] += 1
        self.size[to] += 1

    def dfs(self, v, t, f):
        if v == t: return f
        self.used[v] = True
        for i in range(len(self.G[v])):
            edge = self.G[v][i]
            if self.used[edge.to] is False and edge.cap > 0:
                d = self.dfs(edge.to, t, f if f < edge.cap else edge.cap)
                if d > 0:
                    self.G[v][i].cap -= d
                    self.G[edge.to][edge.rev].cap += d
                    return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.used = [False for _ in range(self.V)]
            f = self.dfs(s, t, float('inf'))
            if f == 0:
                return flow
            flow += f

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ff = ford_fulkerson(N*2+2)
S = 1
T = N + 1

for i in range(M):
    p,q = map(int, input().split())
    ff.add_edge(p,T+q-1,10**9)
    ff.add_edge(q,T+p-1,10**9)

for i in range(N):
    ff.add_edge(i+1,T+i,10**9)
    ff.add_edge(0,S+i,A[i])
    ff.add_edge(T+i,2*N+1,B[i])

ans = [[0  for i in range(N)] for j in range(N)]
ff.max_flow(0,2*N+1)

for i in range(1,N+1):
    for v in ff.G[i]:
        if v.to != 0:
            ans[i-1][v.to-T] = ff.G[v.to][v.rev].cap

if sum(A) != sum(B):
    print('NO')
    quit()
if [sum([ans[i][j] for i in range(N)]) for j in range(N)] == B:
    print('YES')
    for a in ans:
        print(' '.join(map(str,a)))
else:
    print('NO')

CodeForces Round #302 Div2 C - Writing Code

問題 : http://codeforces.com/contest/544/problem/C

内容

プログラマーがn人居る．一人行書くことによって，全員でm行書きたい． プログラマーiは１行書くたびに のバグを生み出すので，それを最大b個におさえつつ，m行書くことの出来るパターン数を答える問題．

解法

制約が多くて最初どうしたらいいか面食らったけど，よく考えると個数制限付きの複数ナップサック問題だった． DP[バグの個数][書いた行数]で，前からループを回していけばバグがb個までに書けるコードの行数を列挙することが出来る．最終的には，各バグの個数に対してm行書いた位置，DP[0-b][m]の個数を足し合わせることで答えが出る．

500³になるので，PyPyでもしかしたら・・・とおもって提出してみたけど無理だったのでC++で書きなおした．整数の範囲に制限があるのでちゃんとmodをとってあげないと答えが合わず少しハマったのと， 個までのループでいけるかとおもったけど，は0を含むのでb個まで回さないといけないとこにはまった．範囲をちゃんと確認できるようにしたい．

Python版：

#!/usr/bin/env python
# -*- coding: utf-8 -*-

n,m,b,mod = map(int,input().split())
A = list(map(int,input().split()))

dp = [[False for i in range(501)] for j in range(501)]
dp[0][0] = 1

for p in range(n):
    for bug in range(b+1):
        for write in range(m):
            if dp[bug][write] is not False:
                if bug + A[p] <= b:
                    dp[bug + A[p]][write+1] += dp[bug][write]

ans = 0
for bug in range(b+1):
    ans += dp[bug][m]
print(ans)
print(ans%mod)

C++で通った版:

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define INF 1e9

int main(){
    int n,m,b,mod;
    cin >> n >> m >> b >> mod ;
    vector<int> A(n,0);
    FOR(i,0,n){
        cin >> A[i] ;
    }

    vector<vector<int> > dp(501,vector<int>(501,0));
    dp[0][0] = 1;

    FOR(p,0,n){
        FOR(bug,0,b+1){
            FOR(write,0,m){
                if(bug + A[p] <= b && dp[bug][write] > 0){
                    dp[bug+A[p]][write+1] = (dp[bug+A[p]][write+1] + dp[bug][write]) % mod;
                }
            }
        }
    }

    int ans = 0;
    FOR(i,0,b+1)
        ans = (ans + dp[i][m])%mod;
    cout << (ans%mod) << endl;

    return 0;
}

ABC014(C,D)

ARC039の復習で，適当な根付き木にして距離を出す必要があったのでライブラリのチェックのために解いた． Dの閉路だけ通すつもりだったけど，どうせなら，とC問題も解いた．

C : AtColor

与えられた区間の最も重なる点を求める問題．

いもす法．気をつけなきゃいけないのは，与えられているのが閉区間なので一個ずれる． 10⁶ かかるのでPythonで通るのか少し不安だったけど，制限時間3秒だったのでセーフ．

#!/usr/bin/env python
# -*- coding: utf-8 -*-

n = int(input())
info = [0 for i in range(10**6 + 2)]
for _ in range(n):
    a,b =  map(int,input().split())
    info[a] += 1
    info[b+1] -= 1

for i in range(10**6 + 1):
    info[i + 1] += info[i]

print(max(info))

D:閉路

木が与えられていて，ある辺を加えたときに生じる閉路の長さを答える問題．

DFSにて深さ，親を記憶していきDFS木を構成する．よく解説に適当な根付き木にする，とあるけどたぶんこの適当な頂点からDFSで木を構成することを適当な根付き木にする，という意味だと思っている．

問題としては，与えられた辺をつなぐ頂点間の距離を元の木から求める事ができれば，追加分の辺を足してあげるだけで解ける．ただし，頂点が , クエリが あるので，愚直に距離を求めると到底間に合わないので， を用いて計算する．

ある頂点aとbのLCAを求める方法は，一番簡単な方法だと同じ高さにして1つずつ親をたどっていく方法だけど，この方法だとO(N)となり，Query分やってしまうとTLE．なので， でLCAを求める事ができるダブリングを実装した．

初期化で行っているのはダブリングの前処理で，あるノードから たどった位置の親を記録している．ダブリングてのは，よくわかってないけど，LCAのようにある点からは共通しているような配列集合を2の累乗ごとに辿れるようにしておいて，配列同士の共通点までの二分探索をしやすくするためのものだと思っている．詳しくは以下．

参考 : [木に対する一般的なテク達] (http://t.co/yxsOVMIwRs)

Pythonで書きたかったので以下のようなクラスを作成した．

class RootedTree:
    # G : adjcency list : 0 - indexed
    # N : the number of vertex
    def __init__(self,N,G):
        self.N = N
        self.G = G

        # for lca
        self.log_N = 20

        self.parents = [[ -1 for i in range(self.log_N)] for j in range(N)]
        self.depth = [-1] * self.N
        self.tree_initialize(0)

        for i in range(self.log_N-1):
            for j in range(N):
                if self.parents[j][i] == -1:
                    self.parents[j][i+1] = -1
                else:
                    self.parents[j][i+1] = self.parents[self.parents[j][i]][i]

    def tree_initialize(self, u):
        q = []
        q.append((u,-1,0))
        while q != []:
            u,parent,d = q.pop()

            self.depth[u] = d
            self.parents[u][0] = parent
            for v in self.G[u]:
                if v != parent:
                    q.append((v, u, d+1))

    def lca(self, u, v):
        if(self.depth[v] < self.depth[u]):
            u,v = v,u

        for i in range(self.log_N-1)[::-1]:
            if(((self.depth[v] - self.depth[u])>>i)&1):
                v = self.parents[v][i]

        if u==v:
            return u

        for i in range(self.log_N-1)[::-1]:
            if self.parents[u][i] != self.parents[v][i]:
                u = self.parents[u][i]
                v = self.parents[v][i]

        return self.parents[u][0]
    
    def dist(self, u, v):
        l = self.lca(u,v)
        return (self.depth[u] - self.depth[l]) + (self.depth[v] - self.depth[l])

と，以上のように書いたはいいけど，結局 だとを超えてしまうのでPythonではTLEだった．なので，C++で書きなおしてAC.

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define INF 1e9

struct rootedtree{
    int V;
    vector<vector<int> > T;
    vector<vector<int> > parents;
    vector<int> depth;
    int log_N = 20;

    rootedtree(int N, vector<vector<int> > &Tree){
        V = N;
        T = Tree;

        depth = vector<int>(V,0);
        parents = vector<vector<int> >(V, vector<int>(log_N-1,0));
        dfs(0,-1,0);

        FOR(i,0,log_N-1){
            FOR(j,0,V){
                if(parents[j][i] == -1)
                    parents[j][i+1] = -1;
                else
                    parents[j][i+1] = parents[parents[j][i]][i];
            }
        }
    }

    void dfs(int u,int parent,int d){
        depth[u] = d;
        parents[u][0] = parent;
        for(int v : T[u]){
            if(v != parent)
                dfs(v, u, d + 1);
        }
    }

    int lca(int u, int v){
        if(depth[v] < depth[u])
            swap(u,v);
         
        for(int i=log_N-1;i>=0;i--){
            if(((depth[v] - depth[u])>>i)&1)
                v = parents[v][i];
         }

        if(u==v) return u;

        for(int i=log_N-1;i>=0;i--){
            if(parents[u][i] != parents[v][i]){
                u = parents[u][i];
                v = parents[v][i];
            }
        }
        
        return parents[u][0];
    }

    int dist(int u, int v){
        int l = lca(u,v);
        return (depth[u] - depth[l]) + (depth[v] - depth[l]);
    }
};

int main(){
    int N;
    int Q;
    cin >> N ;
    vector<vector<int> > T(N);
    FOR(i,0,N-1){
        int x,y;
        cin >> x >> y ;
        x--;y--;
        T[x].push_back(y);
        T[y].push_back(x);
    }

    rootedtree rt(N,T);

    cin >> Q ;
    FOR(i,0,Q){
        int a,b;
        cin >> a >> b ;
        a--;b--;
        cout << rt.dist(a,b) + 1 << endl;
    }

    return 0;
}

HaskellでSchemeを書く#4

追記：見直すこと!!

ここらで一度、ソースを整理することにした。 ついでにためてた宿題も片付けることに。

まずは、構文解析の章。

1.parseNumberの書き換え

• 1.do記法

parseNumber :: Parser LispVal
parseNumber = do
  x <- many1 digit
  return $ (Number . read) x

*2.>>=による明示的シーケンシング

parseNumber :: Parser LispVal
parseNumber = many1 digit >>=  return . Number . read

2は解答を見てしまった。>>= (return (Number . read))とかいていて、なんで通らないんだ・・と思ってたけども、合成しないといけなかったのか。未だ不慣れ・・・

*Main> :t (return (Number . read))
(return (Number . read)) :: Monad m => m (String -> LispVal)
*Main> :t return . Number .read
return . Number .read :: Monad m => String -> m LispVal

2.parseStringの終端判定修正

3.escape文字の実装

これは問題の理解に手間取った・・。\\\"とか、\\nのようなものを実装すればいいんだな。
なのでとりあえず一度\\でパースして続く文字を取り出してあげれば、\"が単体で出てきたときに終端文字として正しく認識される、ということかな。
parseStringの中でパースするにあたり、Parser Charで返さなきゃ行けなくて、エスケープ文字を抽出したあと一文字で返す方法がわからず(文字列として連結して渡そうとしてた)、結局かなり筋が悪い感じになった

parseString :: Parser LispVal
parseString = do char '"'
                 x <- many (parseEscape <|> noneOf "\"")
                 char '"'
                 return $ String x

parseEscape :: Parser Char
parseEscape = do char '\\'
                 x <- oneOf "\\nrts"
                 return $ case x of
                  'n' -> '\n'
                  'r' -> '\r'
                  't' -> '\t'
                  _   -> x

*Main> parseTest parseString "\"abc\\\"abc\\\\1\\n3\""
"abc"abc\1
3"

直したい・・・。

4.'#'prefixの実装

The radix prefixes are #b (binary), #o (octal), #d (decimal), and #x (hexadecimal). With no radix prefix, a number is assumed to be expressed in decimal.

parseNumberよりは、parseAtomを直すのが良いように思える・・・。どうせなので、prefixParserを作る。#prefixを別で処理することにしたので、symbolに吸い込まれないように修正。

symbol :: Parser Char
symbol = oneOf "!$%&|*+-/:<=>?@^_~"

parseAtom :: Parser LispVal
parseAtom = do first <- letter <|> symbol
               rest <- many (letter <|> digit <|> symbol)
               let atom = first:rest
               return $ case atom of
                          _    -> Atom atom

parsePrefix :: Parser LispVal
parsePrefix = do char '#'
                 prefix <- letter <|> symbol
                 expression <- many(letter <|> digit)
                 return $ case prefix of
                  'x' -> Number $ fst $ (readHex expression) !! 0
                  'd' -> (Number . read) expression
                  'o' -> Number $ fst $ (readOct expression) !! 0
                  --'b' -> readBin
                  't' -> Bool True
                  'f' -> Bool False

parseAtomの意味がなくなってしまったな・・・。本当は、firstで処理を分けたかったけど、その場合だと、 一度文字列を処理してparsePrefixでparseするという関数をもう１つ作らなければならなかったのでそちらのほうが筋悪と考えた。readBinはNumericモジュールになかったのでまた考える。

*Main Numeric> parseTest parsePrefix "#d1234"
1234
*Main Numeric> parseTest parsePrefix "#x1234"
4660

5.Characterリテラルの実装

Characters are objects that represent printed characters such as letters and digits. Characters are written using the notation #\\ or #\\. For example:

• #\a ; lower case letter
• #\A ; upper case letter
• #\( ; left parenthesis
• #\ ; the space character
• #\space ; the preferred way to write a space
• #\newline ; the newline character

#\から始まる表現みたい。何もLispValに加えるほどのものでも無い気がするけど、どうなんだろう。 後続の文字が１文字ならそのまま返して、space or newlineなら変換して返す感じかなぁ。 一文字だったら、文字列に一致したら、っていう条件分岐の書き方がわからない・・、のでカンニング・・・

value <- try (string "newline" <|> string "space") 
          <|> do { x <- anyChar; notFollowedBy alphaNum ; return [x] }

alphaNum は letterとdigitをあわせたパーサで、notFollowedByは、何かと組み合わせて、指定されたパーサでパースできるものが続いてる場合はError、そうじゃなければ通す、みたいな関数らしい。(参考Parsec　notFollowedBy - tnomuraのブログ) doのこういうくくり方全然思いつけないなぁ・・。写経することにする。ついでにShowValも変更。

6.Floatコンストラクタの追加

これは、これまでのに比べると簡単。

parseFloat :: Parser LispVal
parseFloat = do
  head <- many1 digit
  char '.'
  tail <- many1 digit
  return $ Float $ fst $ (readFloat $ head ++ "." ++ tail) !! 0

parseExprにはtryを入れて、parseNumberの前に追加

*Main Numeric Text.ParserCombinators.Parsec> parseTest parseExpr "(12.3 123)"
(12.3 123)

7.数値表現の追加

Mathematically, numbers may be arranged into a tower of subtypes in which each level is a subset of the level above it:

number

• complex
• real
• rational
• integer

realとintegerは実装済なので、rationalとcomplexの実装。まずは、rational、有理数・・。

4/6  => 2/3
3/12 => 1/4
10/5 => 2    ; 整数に変換される

こんな感じになるらしい。なんと、HaskellにはRational型があった。凄い。10 % 11のように表示されるということだけど、少数に直したりすると正確な値とはずれるらしい。(参考:すごい乱暴な方法でHaskellの少数を正確数にする-Qiita)
念頭におきつつ、多分今回は関係ないので、とりあえず例にあるような形の数字を、Rational型にする。

parseRational :: Parser LispVal
parseRational = do
  denom <- many1 digit
  char '/'
  num <- many1 digit
  return $ Rational $ read(denom) % read(num)

そのまんまな感じ。

複素数も、Data.Complexなるモジュールにあったので、そのまま流用。
Schemeでの複素数の例

5-3i => 5.0-3.0i
1.2+2.4i => 1.2+2.4i
1/2+1/4i => 0.5+0.25i

parseComplex :: Parser LispVal
parseComplex = do
  re <- many1 digit
  mark <- char '+' <|> char '-'
  im <- many1 digit
  char 'i'
  return $ Complex $case mark of
    '+' -> read(re) :+ read(im)
    '-' -> read(re) :+ (- read(im))

勢いに任せてこんな感じで実装し、答え合わせをすると、実数で表示されてるのを完全に忘れてた。確かにSchemeでも実数表示になってる・・。書き直し・・。

parseComplex :: Parser LispVal
parseComplex = do
  re <- (try parseFloat <|> do { x <- many1 digit;return $ Float $ fst $ head $ readFloat(x)})
  mark <- char '+' <|> char '-'
  im <- (try parseFloat <|> do { x <- many1 digit;return $ Float $ fst $ head $ readFloat(x)})
  char 'i'
  return $ Complex $case mark of
    '+' -> toDouble(re) :+ toDouble(im)
    '-' -> toDouble(re) :+ ( - toDouble(im))

結局toDoubleを実装してこのように。do記法でやってみたけど、これは見た目があれだなぁ・・

かなり急いでやってしまったのでまた見直す事。 現在の進捗：github