分数の話

HackerRank 数学 C++

Equations

整数Nが与えられる。
(1/x) + (1/y) = 1/N!
を満たす正数(x, y)の組の数(mod 1000007)を求めよ。


1000000!なので数え上げ系は無理。
変形すると
(x + y)*N! = xy
なのでこの式と組み合わせを上手く使って解くのかと思ったけどどうも上手くいかない。
相加・相乗平均とかも使ったけど駄目っぽい。


研究室の人に相談してみたところ、見事に解いてくれました。

(1/x) + (1/y) = (1/m)
を考える。
x, y > mを満たすので、x = m + a, y = m + bと置ける(a, b >= 1)。
これを代入して変形するとm^2 = abが得られる。

よって、(N!)^2を素因数分解してa, bに当てはめる方法の数を数えればOK。
ある素因数f[i]がc個あるとき、a, bに割り当てる方法はc+1通りある。
全ての素因数について、(素因数の数+1)を掛けていけば答えが出る。

ただ、結構制限時間が厳しいので高速化しないといけない。普通にやったらTLEしたので、素因数の数え上げの部分で「今見ている数字(変数e)が素数なら即終了」の処理を加えたら通った。

#include <iostream>
#include <cstdio>
//#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
//#include <limits>
#include <sstream>
//#include <functional>
using namespace std;

#define len(array)  (sizeof (array) / sizeof *(array))
#define rep(i, s, e) for(int i = s;i < e;i++)
#define rrep(i, e, s) for(int i = e;s <= i;i--)
#define vrange(v) v.begin(), v.end()
#define vrrange(v) v.rbegin(), v.rend()
#define vsort(v) sort(vrange(v))
#define vrsort(v) sort(vrrange(v))
#define arange(a) a, a + len(a)
#define asort(a) sort(arange(a))
#define arsort(a, t) sort(arange(a), greater<t>())
#define afill(a, v) fill(arange(a), v)
#define afill2(a, v, t) fill((t *)a, (t *)(a + len(a)), v)
#define fmax(a, b) (a < b? b : a)
#define fmin(a, b) (a > b? b : a)
#define fabs(a) (a < 0? -a : a)
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int INF = (int)1e9;
const int MOD = 1000007;
const double EPS = 1e-10;
//const int dx[] = {1, -1, 0, 0, 1, -1, -1, 1};
//const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
//const int weight[] = {0,1,10,100,1000,10000,100000,1000000,10000000};
//priority_queue<int, vector<int>, greater<int>> q;
typedef struct _Node {
  _Node(int arg1 = 0, int arg2 = 0 , int arg3 = 0) {
	i = arg1;
	j = arg2;
	k = arg3;
  }
  int i,j,k;
  bool operator <(const struct _Node &e) const{
    return i == e.i? j < e.j : i < e.i;
  }
  bool operator >(const struct _Node &e) const{
    return i == e.i? j > e.j : i > e.i;
  }
}node;

void doIt(){
  const int MAX_N = 1000002;
  bool bPrimes[MAX_N];
  vector<int> primes;
  int cnt[MAX_N];
  afill(bPrimes, true);
  afill(cnt, 0);
  bPrimes[0] = bPrimes[1] = false;
  primes.push_back(2);
  for(int i = 3; i < MAX_N; i += 2){
	if(bPrimes[i]){
	  primes.push_back(i);
	  for(int j = 3*i; j < MAX_N; j += 2*i) bPrimes[j] = false;
	}
  }
  //cout << primes.size() << endl;
  int n;
  ll ans = 1;
  cin >> n;
  rep(i, 2, n+1){
	int e = i;
	rep(j, 0, primes.size()){
	  while(e % primes[j] == 0){
		cnt[primes[j]]+=2;
		e /= primes[j];
	  }
	  if(bPrimes[e]){
		cnt[e] += 2;
	   	break;
	  }
	  // if(primes[j] > sqrt(e)) break;
	  if(primes[j] > e) break;
	}
  }
  rep(j, 0, primes.size()){
	ans = (ans * (cnt[primes[j]] + 1)) % MOD;
  }
  cout << ans << endl;
}

int main() {
  doIt();
  return 0;
}


確か一橋大学の入試問題で

(1/x) + (1/y) + (1/z) = 1/5
を満たすx, y, zの組を求めよ。

みたいな問題があったけど、あれみたいに考えればよかったみたい。

切断点や橋を求めるTarjanのアルゴリズム

アルゴリズム CodeChef ZOJ C++

グラフ理論において、切断点(cut vertex, articulation point)とは無くす事でグラフの連結成分の数が増える頂点のことをいい、橋(bridge)とは無くす事でグラフの連結成分の数が増える辺のことをいいます。
グラフの頂点集合に対してDFSを行うと森（木の集まり）を構築出来ます。この森を上手く使う事で切断点や森を効率よく見つけることが出来るアルゴリズムがTarjanのアルゴリズムです。
なお、以下ではグラフの頂点数を|V|、辺の数を|E|で表します。

切断点を求めるアルゴリズム

単純に考えると1つ1つの頂点を消してグラフが連結であるかを調べれば良いので、O(|V|*(|V|+|E|))で出来ます。

しかし、Tarjan's Algorithm for articulation pointsを使うとO(|V|+|E|)で切断点を列挙できます。簡単にいうと、それぞれの頂点にDFSで番号をつけていき、各頂点の子（部分木）がその頂点の番号より前の番号につながっていないならば切断点であるということができます。
根だけは特別な処理が必要で、子が2つ以上あれば切断点です。注意すべきなのは、根の子が2つ以上というのは根からの辺が2本以上伸びているという意味ではなく、部分木を2つ以上持っているという意味です。

Kingdom Unityをこのアルゴリズムで解いてみました（本番ではTLEだった）。


ソースコード
Kingdom Unity Editorial

橋を求めるアルゴリズム

単純に考えると、切断点と同様に各辺を消してグラフが連結であるかを調べれば良いので、O(|E|*(|V|+|E|))で出来ます。

切断点と似たような理屈で、Tarjan's Algorithm for finding bridgesを使うとO(|V|+|E|)で橋を列挙できます。それぞれの頂点にDFSで番号をつけていき、ある頂点の子（部分木）がその頂点の番号より後の番号にしかつながっていないならばその2点をつなぐ辺は橋であるということができます。

前々から解きたいと思っていたAttack the NEET Princessをこのアルゴリズムで解いてみました。
ただ、この問題は単純に橋を列挙するだけでは駄目で、ゴールまでとのルートとのintersectionを取ります（C++のset_intersectionが便利）。また、入力条件の「There may be more than one roads between two villages.」に注意が必要。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
//#include <set>
#include <queue>
//#include <limits>
//#include <sstream>
//#include <functional>
using namespace std;

#define len(array)  (sizeof (array) / sizeof *(array))
#define rep(i, s, e) for(int i = s;i < e;i++)
#define rrep(i, e, s) for(int i = e;s <= i;i--)
#define mfill(a, v) fill(a, a + len(a), v)
#define mfill2(a, v, t) fill((t *)a, (t *)(a + len(a)), v)
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v, t) sort(v.begin(), v.end(), greater<t>())
#define asort(a) sort(a, a + len(a))
#define rasort(a, t) sort(a, a + len(a), greater<t>())
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-10;
const int INF = 10000000;
const int dx[] = {1, -1, 0, 0, 1, -1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};

const int MAX_N = 10002, MAX_M = 100001, WHITE = 0, GRAY = 1, BLACK = 2;
int color[MAX_N], low[MAX_N], pred[MAX_N], d[MAX_N], ttime = 0, reach[MAX_N];
bool used[MAX_M];
vector<int> edge[MAX_N];
vector<int> route, bridge;
map<int, int> tab;

int hash(int a, int b) {
  if (a <= b) return a * 10000 + b;
  else return b * 10000 + a;
}

void dfs(int v){
  color[v] = GRAY;
  low[v] = d[v] = ++ttime;
  rep(i, 0, edge[v].size()){
	int w = edge[v][i];
	if(color[w] == WHITE){
	  pred[w] = v;
	  dfs(w);
	  if(low[w] > d[v]){
		int t = tab[hash(v,w)];
		if(t != -1 && used[t] == false){
		  bridge.push_back(t);
		  used[t] = true;
		}
	  }
	  low[v] = min(low[v], low[w]);
	}
	else if(w != pred[v]) low[v] = min(low[v], d[w]);
  }
  color[v] = BLACK;
}

void bfs(int n){
  queue<int> q;
  int p = n - 1;
  mfill(pred, -1);
  q.push(0);
  while(!q.empty()){
	int v = q.front();
	q.pop();
	if(v == n - 1) break;
	rep(i, 0, edge[v].size()){
	  int w = edge[v][i];
	  if(pred[w] == -1){
		pred[w] = v;
		reach[w] = tab[hash(v, w)];
		q.push(w);
	  }
	}
  }
  while(!q.empty()) q.pop();
  while(p != 0){
	if(tab[hash(p, pred[p])] != -1) route.push_back(reach[p]);
	p = pred[p];
  }
}


void init(){
  ttime = 0;
  mfill(color, WHITE);
  mfill(low, INF);
  mfill(pred, -1);
  mfill(d, -1);
  mfill(used, false);
  mfill(reach, -1);
  rep(i, 0, len(edge)) edge[i].clear();
  bridge.clear();
  route.clear();
  tab.clear();
}

void doIt(){
  int n, m, a, b, h;
  vector<int>::iterator it;
  while(~scanf("%d%d", &n, &m)){
	init();
	rep(j, 0, m){
	  scanf("%d%d", &a, &b);
	  edge[a].push_back(b);
	  edge[b].push_back(a);
	  h = hash(a,b);
	  if (tab.count(h) == 0) tab[h] = j;
	  else tab[h] = -1;
	}
	dfs(0);
	bfs(n);
	vsort(bridge);
	vsort(route);
	bridge.erase(set_intersection(bridge.begin(), bridge.end(), route.begin(), route.end(), bridge.begin()), bridge.end());
	printf("%d\n", (int)bridge.size());
	if(1 <= bridge.size()){
	  vsort(bridge);
	  it = bridge.begin();
	  while(it != bridge.end())
		{
		  if(it != bridge.begin()) printf(" %d", *it);
		  else printf("%d", *it);
		  ++it;
		}
	}
	printf("\n");
  }
}

int main() {
  doIt();
  return 0;
}

この問題地雷が多くて、TLE, MLE, PEなどいろいろさまざまなエラーを喰らいました^^（MLE、PEとか初めて喰らった）
Attack the NEET Princess Editorial (中国語)


Tarjanのアルゴリズムを理解しやすいページ
Lecture 6: Depth-First Search (pdf)
Algorithm Design and Complexity

（多分これらと違う）橋を見つけるTarjanのアルゴリズム（僕は理解していません）
Wikipedia

コピー先に連番が扱えるようにcpの拡張を作ってみた

Ruby

今までプログラミングコンテストに望む際に、template.cppをA.cpp, B.cpp, ... , E.cppにコピーする必要があり、これが非常に面倒でした。
先日zmvコマンドの記事(http://mollifier.hatenablog.com/entry/20101227/p1)を読んで、もしかして簡単に連番のcpが出来るのかなと思い、探してみるもなかなか見つかりませんでした。
bashやzshは「{1..5}」を「1,2,3,4,5」に展開してくれる機能があるので、これで行けるかと思いましたが、どうもcpには上手く使えないもよう。「touch A{1..5}.txt」とかは動くのに・・・。


見つからないのなら作っちゃおうということで作ってみました。
https://github.com/mkiken/Small_Programs/tree/master/ccp

始めは何を思ったかPerlで作っていましたが、RubyやPythonの構文糖衣に慣れている僕にはPerlの構文は辛かったので、Rubyで書き直し。
Perlでの実装時に一番悩んでいたのが連番の作り方。"a9"の次を"b0"にすべきかどうか？またどう実装するか？
RubyのStringクラスにはsuccというメソッドがあり、

"a9".succ   # => "b0"

となります。こんな便利なメソッドがあるとはさすがRuby・・・。

適当な試作品ですが、

ccp templates/template.cpp temp/[A..E].cpp

のように使えるので、便利。

二部マッチング

アルゴリズム Java FHC


前から最大流問題を解いてみたいなーを思っており、蟻本を購入したのをきっかけに、この前参加したFacebook Hacker Cup 2013 Round 1の2問目「Security」が二部マッチングの問題だったので解いてみました。

Security

{a, b, c, d, e, f}からなるキー k がある。kはmのセクションから成っている。

関数 f : kを引数にし、いくつかの文字を?にする
関数 g : kを引数にし、kをセクションで分けて順番を変える。

m, k1 = f(k), k2 = f(g(k)) が与えられるので、考えられるkの中で辞書順最小のものを求めよ。


本番は手も足も出ませんでしたが、解説(https://www.facebook.com/notes/facebook-hacker-cup/2013-round-1-solutions/606859202663318)によるとk1の各セクションとk2の各セクションをノードにして、二部マッチングを行えばいいそうです。

二部マッチングは最大流問題に帰着でき、さらにその構造からさらに簡単に書けます。
アルゴリズムとしては、マッチングできるものを適当にマッチングしていき、やってるうちに無理が出てきたら前のマッチングをやり直してみるという感じのようです。O(|E||V|)。

蟻本を写経して作成。

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;

public class R1_2013_B {
	static Vector<Integer>[] edge;
	static int[] match;
	static boolean[] used;
	static int v, m;
	static char[][] k1s, k2s;

	public static void main(String[] args) {
		doIt();
	}

	static void doIt() {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			m = sc.nextInt();
			String k1 = sc.next();
			String k2 = sc.next();
			int sec = k1.length() / m;
			k1s = new char[m][sec];
			k2s = new char[m][sec];
			for (int j = 0; j < m; j++) {
				k1s[j] = k1.substring(sec * j, sec * j + sec).toCharArray();
				k2s[j] = k2.substring(sec * j, sec * j + sec).toCharArray();
			}
			v = 2 * m;
			edge = (Vector<Integer>[]) new Vector[v];
			for (int j = 0; j < v; j++) edge[j] = new Vector<Integer>();
			match = new int[2 * m];
			used = new boolean[2 * m];
			
			if(m != bipartite_matching()){
				System.out.println("Case #" + (i + 1) + ": IMPOSSIBLE");
			}
			else{
				String ans = "";
				for (int j = 0; j < m; j++) {
					String s = "";
					for (int k = 0; k < sec; k++) {
						if(k1s[j][k] == '?'){
							for(char c = 'a'; c <= 'f';c++){
								k1s[j][k] = c;
								if(m == bipartite_matching()){s += c;break;}
							}
						}
						else s += k1s[j][k];
					}
					ans += s;
				}
				System.out.println("Case #" + (i + 1) + ": "  + ans);
			}
		}
	}
	static int bipartite_matching(){
		for (int j = 0; j < v; j++) edge[j].clear();
		for (int j = 0; j < m; j++) {
			for (int j2 = 0; j2 < m; j2++) {
				if(cmp(k1s[j], k2s[j2])){
					edge[j].add(m + j2);
					edge[m + j2].add(j);
				}
			}
		}
		
		Arrays.fill(match, -1);
		int res = 0;
		for (int j = 0; j < v; j++) {
			if(match[j] == -1){
				Arrays.fill(used, false);
				if(dfs(j)) res++;
			}
		}
		return res;
	}
	static boolean cmp(char[] a, char[] b){
		for (int i = 0; i < a.length; i++) {
			if(a[i] != '?' && b[i] != '?' && a[i] != b[i]) return false;
		}
		return true;
	}
	static boolean dfs(int v0){
		used[v0] = true;
		for (int i = 0; i < edge[v0].size(); i++) {
			int u = edge[v0].get(i);
			int w = match[u];
			if(w == -1 || used[w] == false && dfs(w)){
				match[v0] = u;
				match[u] = v0;
				return true;
			}
		}
		return false;
	}
}


知らなかったのがfor文を下のようにcharで回せること。出来るんだろうなーとは思ってましたが、初めて実装しました。

for(char c = 'a'; c <= 'f';c++) ;

あとJavaにおけるVectorの配列の作り方。こちら(http://tyche.pu-toyama.ac.jp/~ko-ji/now-java/VectorArray.html)を見たところ、いまいち綺麗な解決策がないようです。
仕方ないので、以下のように一番簡単に実装。でも、コンパイル時に警告が出ます。

Vector<Integer>[] edge = (Vector<Integer>[]) new Vector[v];

うーん、なんかすっきりしない。

そのうち最大流問題、最小流問題もやってみます。

March Challenge 2013, TCO 2013, Codeforces #172

Contest CodeChef Scala Java TopCoder Codeforces

いくつかコンテストに出たので記録しておきます。


March Challenge 2013

http://www.codechef.com/MARCH13

CodeChefのLong Contest。

Tourist Translations

やるだけ。
Scalaでやってみました。
やっぱり関数型言語のmap関数は便利です。
ちなみにInt型をChar型にするにはtoChar関数を使う。

http://www.codechef.com/viewsolution/1879236

Approximately

103993/33102の値を求める問題。
小数点以下100万桁まで求めるので、実際に筆算をシミュレートする。もしかしてJavaのBigDecimalクラスでいけるか？？とやってみたけどさすがに無理でした。

http://www.codechef.com/viewsolution/1878746

Fire Escape Routes

人数Nと友人関係が与えられたとき、友人関係のある人間をグループにする。また、グループで一人リーダーを決めるとき、グループ数とリーダーの決め方が何通りあるかを求める問題。

やるだけ・・・だけど実装が微妙に難しい。
グループ化はUnion-Find木(http://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)とか使うといいって聞いたことがあるけど、実装できないので配列で作成。
それぞれの人について友人関係を持っておき、それらを同じグループにする。さらに友人の友人も再帰的に同じグループにしていく。

http://www.codechef.com/viewsolution/1883111


解けたのは前回と同じ3問でした。Random decreasing functionはEditorialが出たら解いてみたい。

Long Contest Rating 1784 -> 2113


TCO13 Round 1C

http://community.topcoder.com/stat?c=round_overview&rd=15585

TopCoder Open Round 1Cに参加。登録が早い人から2000人出れて、600位以内の人が次のラウンドに進めます。コンテストの形式はSRMと同じで、Twitterで聞いた話だと、難易度はDiv2以上Div1らしいです。

僕はRoom56。Div1もDiv2もごちゃまぜになってて、レッドコーダーとかいてビビってました。

The Array

隣の要素が最大dだけ離れている長さnの配列と始めの要素と終わりの要素が与えられる。考えられる中で配列内の最大の要素を求める。


Easyなのにむずい・・・とか思いつつ考察。各要素は配列の始めからも終わりからも到達出来る大きさであるはずなので、それらのminをとる。

http://community.topcoder.com/stat?c=problem_solution&rm=316581&rd=15585&pm=12455&cr=23103815

TheOlympiadInInformatics

N個の部屋がある。それぞれの部屋には何人かの人がおり、部屋内の人の合計点が与えられる。整数kが与えられたとき、最低何点あれば自分より大きいスコアを持つ人をk人以下に抑えられるか。


残り30分くらいで解法を思いつく。二分探索で最低点を求めれば良い。実装は難しいかもしれないけど、発想はEasyより簡単？？

http://community.topcoder.com/stat?c=problem_solution&rd=15585&rm=316581&cr=23103815&pm=12456


2問解けて終了時の順位は424.73Ptで850位くらい。Challenging Phase終了後に750位くらいになり、まー600位以内は無理かーと思っていましたが、System Test後に476位まで上がりました。実力以上のものが出たおかげでRound1突破。下がり続けていたレーティングも久々にアップ。

Rating 1024 -> 1121


Codeforces #172 Div2

http://codeforces.com/contest/281

A. Word Capitalization

本当にやるだけ。3分くらい。

http://codeforces.com/contest/281/submission/3275044

B. Nearest Fraction

整数n, x, yが与えられる。以下の問題を解く。

min

(x / y) - (a / b)

subject to
a, b (1 ≤ b ≤ n; 0 ≤ a)


Bなのに難しい問題（終了後に解けていたのが300人ちょっとだった。CodeforcesのBはたまに鬼畜になる気がする・・・）。
n <= 100000なので全部を調べるのは無理そう。でもO(1)で出すのも無理そう。
bを固定したとき、|(x / y) - (a / b)|を最小にするaはx*b / yの近くにあるはず。bを1からnまで動かしてa = x*b / y (+- 1)を調べて、|(x / y) - (a / b)|を最小にするa, bを求める。実装にすごい苦労した。

http://codeforces.com/contest/281/submission/3280960


Cは三角関数の計算をし、とりあえず実装してみたけどサンプル合わず。

落ちるかなと思ったBが落ちず、スコア1210でなんと223位という今までの最高順位でした。しかもRoom内2位。もう10点でRoom内1位だった。惜しい！

Rating 1474 -> 1611

今までの最高レーティング1500を大きく更新。色が緑から青くなりました。緑落ちしないように頑張りたい。

最強のシェル zsh

環境設定

今までシェルはbash一筋だったのですが、最強のシェルと聞いてzshを使ってみました。

Macには標準でもzshが入っていましたが、せっかくなので最新版をインストール。
インストールはHomebrewで

brew install zsh

で一発で出来ます。
デフォルトシェルの変え方はこちら（http://tukaikta.blog135.fc2.com/blog-entry-195.html）とか参照。


zshは.zshrcをいじることでカスタマイズできます。oh-my-zsh(https://github.com/robbyrussell/oh-my-zsh)が簡単で使いやすいらしいです。ただ僕はあまり好みではなかったので自作。下記の参考サイトを見て良さそうな機能をかき集めて作りました。

一番悩んだのがインクリメンタル補完機能。是非欲しい機能だけど、標準搭載のincremental-complete-wordやauto-fu.zsh(https://github.com/hchbaw/auto-fu.zsh)はちょっとイメージと違う。うーんどうしようと思っていたらしっくり来るのを発見！y.fujiiさんの「Incremental completion on zsh」です。すごい！！

http://mimosa-pudica.net/zsh-incremental.html


ちょっと使ってみた感じでは、zshの強力な補完機能はかなりいい感じです。また、過去に訪れたディレクトリに移動出来る「cd -」もかなり便利。
また、zshの勉強の過程で知ったのですが、シェルのコマンドラインってemacsのキーバインド使えたんですね・・・（参照 : http://qiita.com/items/08792b7188b5c11e0f21）。
zshどころかbashでも「Ctrl-w」（単語削除）とか「Ctrl-u」（行削除）、「Ctrl-a」（行頭移動）が出来たなんて・・・。今まで人生を無駄にしていた・・・。

最後に僕の今の.zshrcを書いておきます。コピーするとすぐ使えるので良ければどうぞー。

#read Aliases
source ~/.aliases

#from http://news.mynavi.jp/column/zsh/index.html
case ${UID} in
	0) #for super user
		RPROMPT='(%~)'
		PROMPT=$'%B%m%b:%?:%# '
		;;
	*)
		RPROMPT='(%~)'
		PROMPT=$'%m: %n %D{%T} %{%F{cyan}%}%#%{%f%} '
esac

#SPROMPT="%r is correct? [n,y,a,e]:] "


# auto change directory
setopt auto_cd

# auto directory pushd that you can get dirs list by cd -[tab]
setopt auto_pushd

# command correct edition before each completion attempt
setopt correct

# compacked complete list display
setopt list_packed

# no remove postfix slash of command line
setopt noautoremoveslash

# no beep sound when complete list displayed
#
#setopt nolistbeep

## Keybind configuration
# emacs like keybind (e.x. Ctrl-a goes to head of a line and Ctrl-e goes
#   to end of it)
bindkey -e

# historical backward/forward search with linehead string binded to ^P/^N
autoload history-search-end
zle -N history-beginning-search-backward-end history-search-end
zle -N history-beginning-search-forward-end history-search-end
bindkey "^P" history-beginning-search-backward-end
bindkey "^N" history-beginning-search-forward-end

## Command history configuration
#
HISTFILE=~/.zsh_history
HISTSIZE=10000
SAVEHIST=10000
setopt hist_ignore_dups     # ignore duplication command history list
setopt share_history        # share command history data

## Completion configuration
#http://qiita.com/items/f2971728c845c75e9967
autoload -U compinit && compinit
compinit

#autoload predict-on
#predict-on

setopt complete_aliases # aliased ls needs if file/dir completions work



#from http://qiita.com/items/ed2d36698a5cc314557d
zstyle ':completion:*:default' menu select=2
zstyle ':completion:*' verbose yes
zstyle ':completion:*' completer _expand _complete _match _prefix _approximate _list _history
zstyle ':completion:*:messages' format '%F{YELLOW}%d'$DEFAULT
zstyle ':completion:*:warnings' format '%F{RED}No matches for:''%F{YELLOW} %d'$DEFAULT
zstyle ':completion:*:descriptions' format '%F{YELLOW}completing %B%d%b'$DEFAULT
zstyle ':completion:*:options' description 'yes'
zstyle ':completion:*:descriptions' format '%F{yellow}Completing %B%d%b%f'$DEFAULT

# マッチ種別を別々に表示
zstyle ':completion:*' group-name ''

# セパレータを設定する
zstyle ':completion:*' list-separator '-->'
zstyle ':completion:*:manuals' separate-sections true

# 名前で色を付けるようにする
autoload colors
colors

# LS_COLORSを設定しておく
export LS_COLORS='di=34:ln=35:so=32:pi=33:ex=31:bd=46;34:cd=43;34:su=41;30:sg=46;30:tw=42;30:ow=43;30'

# ファイル補完候補に色を付ける
zstyle ':completion:*' list-colors ${(s.:.)LS_COLORS}

# 補完に関するオプション
# http://voidy21.hatenablog.jp/entry/20090902/1251918174
setopt auto_param_slash      # ディレクトリ名の補完で末尾の / を自動的に付加し、次の補完に備える
setopt mark_dirs             # ファイル名の展開でディレクトリにマッチした場合 末尾に / を付加
setopt list_types            # 補完候補一覧でファイルの種別を識別マーク表示 (訳注:ls -F の記号)
setopt auto_menu             # 補完キー連打で順に補完候補を自動で補完
setopt auto_param_keys       # カッコの対応などを自動的に補完
setopt interactive_comments  # コマンドラインでも # 以降をコメントと見なす
setopt magic_equal_subst     # コマンドラインの引数で --prefix=/usr などの = 以降でも補完できる

setopt complete_in_word      # 語の途中でもカーソル位置で補完
setopt always_last_prompt    # カーソル位置は保持したままファイル名一覧を順次その場で表示

setopt print_eight_bit  #日本語ファイル名等8ビットを通す
setopt extended_glob  # 拡張グロブで補完(~とか^とか。例えばless *.txt~memo.txt ならmemo.txt 以外の *.txt にマッチ)
setopt globdots # 明確なドットの指定なしで.から始まるファイルをマッチ

bindkey "^I" menu-complete   # 展開する前に補完候補を出させる(Ctrl-iで補完するようにする)

# 範囲指定できるようにする
# 例 : mkdir {1-3} で フォルダ1, 2, 3を作れる
setopt brace_ccl

# manの補完をセクション番号別に表示させる
zstyle ':completion:*:manuals' separate-sections true

# 変数の添字を補完する
zstyle ':completion:*:*:-subscript-:*' tag-order indexes parameters


#cdは親ディレクトリからカレントディレクトリを選択しないので表示させないようにする (例: cd ../<TAB>):
zstyle ':completion:*:cd:*' ignore-parents parent pwd

# オブジェクトファイルとか中間ファイルとかはfileとして補完させない
zstyle ':completion:*:*files' ignored-patterns '*?.o' '*?~' '*\#'


# http://qiita.com/items/55651f44f91123f1881c
# url: $1, delimiter: $2, prefix: $3, words: $4..
function web_search {
  local url=$1       && shift
  local delimiter=$1 && shift
  local prefix=$1    && shift
  local query

  while [ -n "$1" ]; do
    if [ -n "$query" ]; then
      query="${query}${delimiter}${prefix}$1"
    else
      query="${prefix}$1"
    fi
    shift
  done

  open "${url}${query}"
}

function google () {
  web_search "https://www.google.co.jp/search?&q=" "+" "" $*
}

#http://qiita.com/items/156464de9caf64338b17
#bindkey "^[u" undo
#bindkey "^[r" redo

#incremental-complete
#autoload incremental-complete-word
#zle -N incremental-complete-word
#bindkey '\C-xI' incremental-complete-word



# Incremental completion for zsh
# by y.fujii <y-fujii at mimosa-pudica.net>, public domain

#autoload -U compinit
zle -N self-insert self-insert-incr
zle -N vi-cmd-mode-incr
zle -N vi-backward-delete-char-incr
zle -N backward-delete-char-incr
zle -N expand-or-complete-prefix-incr
#compinit

bindkey -M viins '^[' vi-cmd-mode-incr
bindkey -M viins '^h' vi-backward-delete-char-incr
bindkey -M viins '^?' vi-backward-delete-char-incr
bindkey -M viins '^i' expand-or-complete-prefix-incr
bindkey -M emacs '^h' backward-delete-char-incr
bindkey -M emacs '^?' backward-delete-char-incr
bindkey -M emacs '^i' expand-or-complete-prefix-incr

setopt automenu

now_predict=0

function limit-completion
{
	if ((compstate[nmatches] <= 1)); then
		zle -M ""
	elif ((compstate[list_lines] > 6)); then
		compstate[list]=""
		zle -M "too many matches."
	fi
}

function correct-prediction
{
	if ((now_predict == 1)); then
		if [[ "$BUFFER" != "$buffer_prd" ]] || ((CURSOR != cursor_org)); then
			now_predict=0
		fi
	fi
}

function remove-prediction
{
	if ((now_predict == 1)); then
		BUFFER="$buffer_org"
		now_predict=0
	fi
}

function show-prediction
{
	# assert(now_predict == 0)
	if
		((PENDING == 0)) &&
		((CURSOR > 1)) &&
		[[ "$PREBUFFER" == "" ]] &&
		[[ "$BUFFER[CURSOR]" != " " ]]
	then
		cursor_org="$CURSOR"
		buffer_org="$BUFFER"
		comppostfuncs=(limit-completion)
		zle complete-word
		cursor_prd="$CURSOR"
		buffer_prd="$BUFFER"
		if [[ "$buffer_org[1,cursor_org]" == "$buffer_prd[1,cursor_org]" ]]; then
			CURSOR="$cursor_org"
			if [[ "$buffer_org" != "$buffer_prd" ]] || ((cursor_org != cursor_prd)); then
				now_predict=1
			fi
		else
			BUFFER="$buffer_org"
			CURSOR="$cursor_org"
		fi
		echo -n "\e[32m"
	else
		zle -M ""
	fi
}

function preexec
{
	echo -n "\e[39m"
}

function vi-cmd-mode-incr
{
	correct-prediction
	remove-prediction
	zle vi-cmd-mode
}

function self-insert-incr
{
	correct-prediction
	remove-prediction
	if zle .self-insert; then
		show-prediction
	fi
}

function vi-backward-delete-char-incr
{
	correct-prediction
	remove-prediction
	if zle vi-backward-delete-char; then
		show-prediction
	fi
}

function backward-delete-char-incr
{
	correct-prediction
	remove-prediction
	if zle backward-delete-char; then
		show-prediction
	fi
}

function expand-or-complete-prefix-incr
{
	correct-prediction
	if ((now_predict == 1)); then
		CURSOR="$cursor_prd"
		now_predict=0
		comppostfuncs=(limit-completion)
		zle list-choices
	else
		remove-prediction
		zle expand-or-complete-prefix
	fi
}

参考 :
漢のzsh http://news.mynavi.jp/column/zsh/index.html
zsh Advent Calendar 2012 http://qiita.com/advent-calendar/2012/zsh
http://qiita.com/items/ed2d36698a5cc314557d
http://d.hatena.ne.jp/Naruhodius/20110520/1305872622
http://d.hatena.ne.jp/seiunsky/20110519/1305764493

BITを使ってみた

データ構造 CodeChef C++

前に出たCodeChefのコンテストで解けなかった問題を解いてみました。

Magic Board
http://www.codechef.com/problems/MBOARD

N*NのフィールドとQ個のクエリが与えられる。
クエリは
RowSet i x: i行目をx(=0 or 1)にする。
ColSet i x: i列目をx(=0 or 1)にする。
RowQuery i: i行目の0の数を答える。
ColQuery i: i列目の0の数を答える。

N, Q <= 500000なのでシミュレーションは無理。
i行目の0の数を知るには、
・最後のRowSet i xのxが0か1か
・最後のRowSet i xのあとにColSet j (xの逆) が何個発生したか分かれば良い。

全く分かりませんでしたが、BITを使ってタイムスタンプを覚えておけば出来るらしいです。

MBOARD Editorial
http://discuss.codechef.com/questions/6379/mboard-editorial


BITってなんだ？？ということで調べてみました。
BITというのはBinary Indexed Treeの略で、Fenwick Treeともいうそうです。例えば長さnのIntの配列が与えられた時にi〜j番目の総和などをO(logn)時間で計算できます。

調べてみると、構造的にはセグメント木のようなイメージですが、実装がものすごく簡単。
なんと、C++でadd、queryが以下の短さで書けます。驚きの短さ！

//配列のindex番目にvalを足す操作
void add(int *ary, int index, int val){
	int t = index;
	if(t == 0) return;
	while(t <= q + 1){
		ary[t] += val;
		t += t&(-t);
	}
}
//配列の先頭からindex番目までの総和を取る操作
int query(int*ary, int index){
	int ret = 0;
	int t = index;
	while(0 < t){
		ret += ary[t];
		t -= t&(-t);
	}
	return ret;
}

詳しくは調べてみてください。t & (-t)でtの最後のビットが取れるのがポイント。あとBITでは0-indexではなくて1-indexの方が簡単な気がします。

参考 : http://spinda2.blog48.fc2.com/blog-entry-427.html


BITを使ってMagic Boardを解いたコードはこちら(http://www.codechef.com/viewsolution/1844022)。
フィールドが始め0になっていますが、これは仮想的に1個目のクエリとし、i回目のクエリをi + 1回目とすると分かりやすいと思います。