JOIss2013 - gdgdiary

参加記です.
JOIssは8/26~30に準山奥で開催されました.

怖い本ばかりに見えて怯えながらコンピュータ・ジオメトリを選択しました.
(指圧マットさんとhogloidさんと同じ班, チューターは藤原さんでした)
講義寝まくってすみませんでした..

セミナーも楽しかったですが普段なかなか会えない人達と交流出来たのが何より良かったです.
それから変な用語が生まれる感じが面白かったです.
最終日にはみんな疲れてきて, snukeさんとDEGwerさんが添い寝したりしていました.
添い寝する人多すぎると思いました.
発表会の間Twitterで実況しまくって規制垢をたくさん作っているチューターとかがいてやばかっｙった(tozanさんプロ)
最終日kagamiz先生と遊んで帰ろうとしたら新幹線の終電がかなり危ない感じになって走って乗るとrefuteさんとcubicさんがいて驚いた.

参加権がまだある人は積極的に行くといいと思います.
内輪感が強くて初めは大変かもしれませんが慣れると快適です!
夏休みの宿題の進捗ダメです！
agypo3したい...

関係ないですがソースを載せておきます.
PKU 3274 Gold Balanced Lineup
N個の数列が与えられて, ある区間に含まれる数の各bitについて立っている個数が等しいような区間をバランスの良い区間と定義した時, 最長のバランスの良い区間の長さを出力せよ.
(N <= 10^5, ai <= 2^30)

少し考えると, 上から順番に見ていって, 各bit間の差が等しいようになる場所が2つあればその間がバランスの良い区間になることがわかるので, 適当に計算する(差を変なハッシュにしてやるとNlogNになる)

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <climits>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define fi first
#define se second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,1,-1};

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int n, k, ans;
int a[100010];
map<ll, int> zan;
int z[40];

int main(){
    scanf("%d %d", &n, &k);
    zan[0] = 0;

    rep(i, n){
	scanf("%d", &a[i]);
	int x = a[i];
	rep(j, k){
	    z[j] += (x & 1);
	    x /= 2;
	}
	int mi = 2;
	rep(j, k) mi = min(mi, z[j]);
	ll cur = 0;
	rep(j, k){
	    cur *= ll(n + 1);
	    z[j] -= mi;
	    cur += z[j];
	}
	if(zan.count(cur)) ans = max(ans, i + 1 - zan[cur]);
	else zan[cur] = i + 1;
    }
    printf("%d\n", ans);
    return 0;
}

PKU 3613 Cow Relays
辺の数が100以下のグラフが与えられる.
点sからtにちょうど辺をN本経由して行く時の最短距離を求めよ(N<=10^6)

各点の次数が2以上という条件から表れる点が高々100個であることがわかる.
行列累乗みたいな感じのことをすると通る. O(V^3*logN)

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <climits>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define fi first
#define se second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,1,-1};

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int n, m, st, en;
pair<P, int> eg[110];
vector<int> xs;
int id[1010];
ll d[110][110];
ll x[110][110];
ll ret[110][110];

int main(){
    scanf("%d %d %d %d", &n, &m, &st, &en);
    rep(i, m){
	scanf("%d %d %d", &eg[i].se, &eg[i].fi.fi, &eg[i].fi.se);
	xs.pb(eg[i].fi.fi); xs.pb(eg[i].fi.se);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    rep(i, xs.size()) id[xs[i]] = i;
    rep(i, xs.size()){
	rep(j, xs.size()) d[i][j] = x[i][j] = ret[i][j] = INT_MAX;
	x[i][i] = 0;
    }
    
    rep(i, m){
	eg[i].fi.fi = id[eg[i].fi.fi];
	eg[i].fi.se = id[eg[i].fi.se];
	d[eg[i].fi.fi][eg[i].fi.se] = d[eg[i].fi.se][eg[i].fi.fi] = eg[i].se;
    }
    
    while(n > 0){
	if(n & 1){
	    rep(i, xs.size()) fill(ret[i], ret[i] + xs.size(), INT_MAX);
	    rep(i, xs.size()) rep(j, xs.size()) rep(k, xs.size()) ret[i][k] = min(ret[i][k], x[i][j] + d[j][k]);
	    rep(i, xs.size()) rep(j, xs.size()) x[i][j] = ret[i][j];
	}
	rep(i, xs.size()) fill(ret[i], ret[i] + xs.size(), INT_MAX);
	rep(i, xs.size()) rep(j, xs.size()) rep(k, xs.size()) ret[i][k] = min(ret[i][k], d[i][j] + d[j][k]);
	rep(i, xs.size()) rep(j, xs.size()) d[i][j] = ret[i][j];
	n /= 2;
    }
    printf("%lld\n", x[id[st]][id[en]]);
    return 0;
}