Pokemon Advent Calendar 2014 11日目

この記事はPokemon Advent Calendar 2014 - Adventarの11日目の記事として書かれたものです。

最近はポケモンから遠ざかっていましたが、主催者のkagamizさんが辛そうだったので書くことになりました。ご確認ください。

エンジョイ勢なので育成論とかは置いておいて(まあ多少はやってたんですがそういうのはガチ勢の方にお願いすることにして)思い出を軽く語ろうと思います。当初はn文字(n<=10)の記事になる予定でしたが先に釘をさされてしまいました(╹◡╹)

直近のポケモンのソフトと言えばオメガルビー/アルファサファイアです(自分は今年受験生なのもあって(まあ主な理由は金欠なのですが)買えていません)

このソフトは2002年11月21日に発売されたゲームボーイアドバンス版のルビー/サファイアのリメイクです。

え....

2002年??????????

現在18歳なので.......(察し)

実は自分が初めてやったポケモン、更には初めてやったゲームがサファイアでした。 なのでこのリメイクはかなり気になっていました。
初めに選んだ御三家はミズゴロウだったかな。可愛さ重視。

因みにそれ以前のゲームボーイ系とかは触ったことがないです。

こういうポケモンを集めたり育てたりといったゲームが自分に合っていたらしくハマって、馬鹿みたいに長時間やっていたら親に怒られてエアコンの上に隠されたりした記憶があります。当時は努力値とかそういったパラメータの存在は全く知らず純粋に好きなポケモンを育てたりして楽しんでしました。小学校とかでもやっている人が多くて盛り上がった記憶。速く殿堂入りする遊びとかもあった気がする。

それ以後のポケモンはX,Yまでは結構プレーして来ましたが(コロシアムとかダンジョン系とかレンジャーとかも)、1番プレーしたのは多分ダイヤモンドとかかな？(忘れた)　まあその辺に極大値がありそう。ボックスがたくさん同じポケモンで埋まったりしてました。個人的にコロシアムとか結構楽しかったような。

中高に入ってからは結構他のゲームに流れてしまいました...がたまにポケセンとかに行くと相変わらずぬいぐるみに惹かれてしまいます。

文章力が足りないのでぬいぐるみ情報をお送りします。

最後に...

ポケモンで悶々

一般に受験生は辛いぞい。

AOJ2439 Hakone

箱根駅伝。問題概要は略。
解法が面白かったのでメモ

dp[i][j] : 現在i位まで見てj個unmatchedな場合の数
として、
i番目が-ならそのまま,
Dならi番目をそれまでの空いているところに入れるのでj通り,
またi番目にそれまでのを入れる.... dp[i+1][j-1] += dp[i][j] * j * j
スルー.... dp[i+1][j] += dp[i][j] * j

Uなら
i番目にそれまでのを入れる... dp[i+1][j] += dp[i][j] * j
スルー... dp[i+1][j+1] += dp[i][j]

として更新するとO(n^2)で解ける

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n)  for(int i = 0; i < (int)n; ++i)

const int MOD = 1000000007;

int n;
int dp[210][210];

inline void md(int &x, int y){ x += y; if(x >= MOD) x -= MOD; }

int main(){
    dp[0][0] = 1;
    scanf("%d", &n);
    rep(i, n){
	char c[3]; scanf("%s", c);
	if(c[0] == '-') for(int j = 0; j <= i + 1; ++j) dp[i+1][j] = dp[i][j];
	else if(c[0] == 'D'){
	    for(int j = 1; j <= i + 1; ++j){
		md(dp[i+1][j-1], (ll)dp[i][j] * j * j % MOD);
		md(dp[i+1][j], (ll)dp[i][j] * j % MOD);
	    }
	}else{
	    for(int j = 0; j <= i; ++j){
		md(dp[i+1][j], (ll)dp[i][j] * j % MOD);
		md(dp[i+1][j+1], dp[i][j]);
	    }
	}
    }
    printf("%d\n", dp[n][0]);
    return 0;
}

Codeforces #157 Div1 E Little Elephant and Tree

Problem - E - Codeforces

segment treeを使って頑張ると解ける(dfsしながらやると上手く行く系)

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

struct segtree{
    int *lazy, *mi, *cnt;
    int sz;

    segtree(int n){
	for(sz = 1; sz < n; sz *= 2); 
	lazy = new int[sz * 2 - 1];
	mi = new int[sz * 2 - 1];
	cnt = new int[sz * 2 - 1];
    }

    void init(){ init(0, 0, sz); }
    void add(int a, int b, int x){ add(a, b, x, 0, 0, sz); }
    pii query(int a, int b){ return query(a, b, 0, 0, sz); }

    void init(int k, int l, int r){
	lazy[k] = mi[k] = 0;
	cnt[k] = r - l;
	if(k < sz - 1){
	    init(k * 2 + 1, l, (l + r) / 2);
	    init(k * 2 + 2, (l + r) / 2, r);
	}
    }

    inline void spread(int k){
	if(lazy[k] == 0) return ;
	mi[k] += lazy[k];
	if(k < sz - 1){
	    lazy[k * 2 + 1] += lazy[k];
	    lazy[k * 2 + 2] += lazy[k];
	}
	lazy[k] = 0;
    }

    inline void upd(int k){
	cnt[k] = 0;
	mi[k] = min(mi[k * 2 + 1], mi[k * 2 + 2]);
	if(mi[k * 2 + 1] == mi[k]) cnt[k] += cnt[k * 2 + 1];
	if(mi[k * 2 + 2] == mi[k]) cnt[k] += cnt[k * 2 + 2];
    }

    void add(int a, int b, int x, int k, int l, int r){
	spread(k);
	if(r <= a || b <= l) return ;
	if(a <= l && r <= b){ lazy[k] += x; spread(k); return ; }
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
	upd(k);
    }

    pii query(int a, int b, int k, int l, int r){
	spread(k);
	if(r <= a || b <= l) return mp(0, INT_MAX);
	if(a <= l && r <= b) return mp(cnt[k], mi[k]);
	pii lc = query(a, b, k * 2 + 1, l, (l + r) / 2);
	pii rc = query(a, b, k * 2 + 2, (l + r) / 2, r);

	pii ret = mp(0, INT_MAX);
	if(lc.se <= rc.se) ret = lc;
	if(rc.se <= lc.se){
	    ret.se = rc.se;
	    ret.fi += rc.fi;
	}
	return ret;
    }
};

int n, m;
segtree *t;
vector<int> g[100010];
vector<int> op[100010];
int in[100010], out[100010];
int ans[100010];
int now;

inline void tour(int v, int p){
    in[v] = now++;
    for(int &to : g[v]) if(to != p) tour(to, v);
    out[v] = now;
}

void calc(int v, int p){
    bool f = false;

    for(int &x : op[v]){
	t->add(in[x], out[x], 1);
	if(!f){
	    f = true;
	    t->add(in[v], out[v], 1);
	}
    }

    pii ret = t->query(0, n);
    if(ret.se > 0) ans[v] = n;
    else ans[v] = n - ret.fi;
    if(ans[v]) --ans[v];

    for(int &to : g[v]) if(to != p) calc(to, v);

    for(int &x : op[v])
	t->add(in[x], out[x], -1);

    if(f) t->add(in[v], out[v], -1);
}

int main(){
    scanf("%d %d", &n, &m);

    rep(i, n - 1){
	int a, b;
	scanf("%d %d", &a, &b); --a; --b;
	g[a].pb(b);
	g[b].pb(a);
    }

    rep(i, m){
	int a, b;
	scanf("%d %d", &a, &b); --a; --b;
	op[a].pb(b); op[b].pb(a);
    }

    tour(0, -1);
    t = new segtree(n);
    t->init();
    calc(0, -1);
    rep(i, n) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');

    return 0;
}

gcc4.9 インストール(OS X Yosemite)

珍しくパソコン系かつ問題系でない話題。(メモ)

#include<bits/stdc++.h> は前準備禁止なIOIとかICPCで特に役に立つ気がする（あとはテンプレート使わないで毎回0から書いてる人）

— hogloid (@hogloid) 2014, 11月 12

を見てbits/stdc++.hの存在に気付く

• > 試す
• > コンパイルエラー
• > ファッ
• > そういえばOS Xのgccは中身がclangだったな〜と思い出し、gccをインストールすることにする。

昔なにかをした時homebrewやらmac portやらを入れていたので楽勝だと思ったら意外と手こずった

まずhomebrewを用いてgccをインストールを試みたが、意味不明なエラー(検索しても出てこなかった)のせいで時間を溶かしてしまった

某potetisenseiからmac portでやってみたらと言われやると、1回目は失敗したが2回目は特にエラーも出ずスムーズにインストール出来ました。

(参考にしたページ :
mac port で gcc4.8を入れたった - Bye Bye Moore

テンプレートが短くなって嬉しみ

Codeforces #189 Div1. C Kalila and Dimna in the Logging Industry

Convex-Hull Trickを蟻本の形のまま使える問題があったのでメモ。

b[n-1] = 0に気付けると、
dp[0] = 0,
dp[i] = min[j=0, i - 1] (dp[j] + b[j] * a[i]) (i >= 1)
とすればO(N^2)で計算出来ることがわかる。
y = b[j] * x + dp[j]のa[i]での値であって、b[j] : 単調減少, a[i] : 単調増加より蟻本のまま適用できる。

直線の上下判定に超苦戦(long longをあふれるのに気付かなかった。)

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

typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

int n;
ll a[100010], b[100010];
ll dp[100010];
int deq[100010];
int s, t;

ll f(int j, int pos){
    return b[j] * a[pos] + dp[j]; 
}

bool ng(int t1, int t2, int t3){
    double a1 = b[t1], b1 = dp[t1];
    double a2 = b[t2], b2 = dp[t2];
    double a3 = b[t3], b3 = dp[t3];
    return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2);
}

int main(){
    scanf("%d", &n);
    rep(i, n) scanf("%I64d", &a[i]);
    rep(i, n) scanf("%I64d", &b[i]);

    for(int i = 1; i < n; ++i){
	while(s + 1 < t && ng(deq[t - 2], deq[t - 1], i - 1)) --t;
	deq[t++] = i - 1;

	while(s + 1 < t && f(deq[s], i) >= f(deq[s + 1], i)) ++s;
	dp[i] = f(deq[s], i);
    }
    printf("%I64d\n", dp[n-1]);

    return 0;
}

夏模試

夏休みに受けた模試3つが全部返ってきた(呟く気にはあまりならないのでここに載せることにした)

受けた順に
東大オープン(河合)

英語の採点辛すぎるし数学はそこそこ大変だったのでこんなもん(理科悪すぎ)

東大実戦(駿台)

英語(簡単) 数学(高1模試) 国語(puke)(handshake) (理科悪すぎ)

京大実戦(駿台)

英語(和訳の採点厳しい) 数学(簡単) 国語(寝るべきではなかった) (理科悪すぎ)

理科と社会をやらねばなあという感じでした

USACO 2014 January Contest, Gold

今月と見せかけて先月のGoldを解きました。

Problem 1. Cow Curling
N点から3点選んでできる三角形の領域の和集合が凸包になっていることがわかるので、凸包を作る。
N <= 50000なためN^2ができずつらぽよするが、凸包の点を始点から見た角度でsortすると二分探索で含まれそうな三角形がわかり、外積を使って三角形の内外判定をすると判定できる。
これはテストケースがもっと強いと落ちるかもナアと思う

O(N log N)

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

typedef long long ll;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

int n;
int sa, sb;

struct PO{
    ll x, y;
    PO(){}
    PO(ll x, ll y) : x(x), y(y){}
    ll cross(PO p){ return x * p.y - y * p.x; }
    PO operator - (PO p){ return PO(x - p.x, y - p.y); }
    bool operator < (const PO& p) const{ return x == p.x ? y < p.y : x < p.x; }
};

PO a[50010], b[50010];

vector<PO> conhull(PO* p){
    sort(p, p + n);
    int now = 0; 
    vector<PO> vec(n * 2);
    rep(i, n){
	while(now > 1 && (vec[now - 1] - vec[now - 2]).cross(p[i] - vec[now - 1]) <= 0) --now;
	vec[now++] = p[i];
    }
    for(int i = n - 2, la = now; i >= 0; --i){
	while(now > la && (vec[now - 1] - vec[now - 2]).cross(p[i] - vec[now - 1]) <= 0) --now;
	vec[now++] = p[i];
    }
    vec.resize(now - 1);
    return vec;
}

bool in(PO g, PO gg, PO ggg, PO ob){
    if((gg - g).cross(ob - g) < 0) return false;
    if((ggg - gg).cross(ob - gg) < 0) return false;
    if((g - ggg).cross(ob - ggg) < 0) return false;
    return true;
}

int main(){
    freopen("curling.in", "r", stdin);
    freopen("curling.out", "w", stdout);   
    scanf("%d", &n);
    rep(i, n) scanf("%lld %lld", &a[i].x, &a[i].y);
    rep(i, n) scanf("%lld %lld", &b[i].x, &b[i].y);
    vector<PO> aa = conhull(a);
    vector<PO> bb = conhull(b);

#ifdef DEBUG
    puts("\naa");
    rep(i, aa.size()) printf("%lld %lld\n", aa[i].x, aa[i].y);
    puts("\nbb");
    rep(i, bb.size()) printf("%lld %lld\n", bb[i].x, bb[i].y);    
#endif

    PO st = aa[0];
    vector<double> v;
    rep(i, aa.size()) if(i) v.pb(atan2(aa[i].y - st.y, aa[i].x - st.x));
    //rep(i, v.size()) cout << 180 * v[i] / PI << endl;

    rep(i, n){
	double r = atan2(b[i].y - st.y, b[i].x - st.x);
	if(r < v[0] || r > v.back()) continue;
	if(v.size() == 1){
	    sa += (b[i] < aa[1]);
	    continue;
	}
	vector<double>::iterator it;
	it = lower_bound(v.begin(), v.end(), r);
	bool f = false;
	if(it != v.begin()){
	    int t = it - v.begin() + 1;
	    f |= in(st, aa[t-1], aa[t], b[i]);
	}
	if(it + 1 != v.end()){
	    int t = it - v.begin() + 1;	    
	    f |= in(st, aa[t], aa[t+1], b[i]);
	}
	sa += f;
    }
    //debug(sa);

    v.clear();
    st = bb[0];
    rep(i, bb.size()) if(i) v.pb(atan2(bb[i].y - st.y, bb[i].x - st.x));
    //rep(i, v.size()) cout << 180 * v[i] / PI << endl;

    rep(i, n){
	double r = atan2(a[i].y - st.y, a[i].x - st.x);
	if(r < v[0] || r > v.back()) continue;
	if(v.size() == 1){
	    sb += (a[i] < bb[1]);
	    continue;
	}
	vector<double>::iterator it;
	it = lower_bound(v.begin(), v.end(), r);
	bool f = false;

	if(it != v.begin()){
	    int t = it - v.begin() + 1;
	    f |= in(st, bb[t-1], bb[t], a[i]);
	}
	if(it + 1 != v.end()){
	    int t = it - v.begin() + 1;	    
	    f |= in(st, bb[t], bb[t+1], a[i]);
	}
	sb += f;
    }
    //debug(sb);
    printf("%d %d\n", sa, sb);
    return 0;
}

Problem 2. Building a Ski Course
明らかに二分探索できるので、判定を考えると、逆から辿っていくと簡単に調べることができる。
こういうのは計算量がわからない

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

int n, m;
int lb = 1, ub;
char gri[110][110];
int gr[110][110];
bool done[110][110];
bool pr[110][110];

bool ok(int x){
    memset(done, 0, sizeof(done));
    memset(pr, 0, sizeof(pr));

    while(true){
	bool f = false;
	for(int i = 0; i <= n - x; ++i){
	    for(int j = 0; j <= m - x; ++j){
		if(pr[i][j]) continue;
		bool s[2]; 
		s[0] = s[1] = false;
		rep(k, x) rep(l, x) if(!done[i+k][j+l]){
		    s[gr[i+k][j+l]] = true;
		    if(s[0] && s[1]) break;
		}
		if(!(s[0] || s[1])) continue;
		if(s[0] && s[1]) continue;
		rep(k, x) rep(l, x) done[i+k][j+l] = true;
		f = true;
		pr[i][j] = true;
	    }
	}
	if(!f) break;
    }

    rep(i, n) rep(j, m) if(!done[i][j]) return false;
    return true;
}

int main(){
    freopen("skicourse.in", "r", stdin);
    freopen("skicourse.out", "w", stdout);
    scanf("%d %d", &n, &m);
    ub = min(n, m) + 1;
    rep(i, n){
	scanf("%s", gri[i]);
	rep(j, m) gr[i][j] = (gri[i][j] == 'R');
    }
    
    while(ub - lb > 1){
	int mid = (ub + lb) / 2;
	if(ok(mid)) lb = mid;
	else ub = mid;
    }

    printf("%d\n", lb);
    return 0;
}

Problem 3. Ski Course Rating
結構面白かった。辺のコストをelevationの差の絶対値としたグリッドグラフを考える。
コストが小さい順に頂点を併合していき、集合のサイズが一定値以上に初めてなった時のコストを頑張ってunionfindに覚えさせる。つらぽよ。
O(NM*hoge)っぽい

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

typedef pair<int, int> P;
typedef long long ll;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

int n, m, t;

struct unionfind{
    vector<int> par, rank, sz, ra;
    unionfind(){}

    void init(int n_){
	par.resize(n_);
	rank.resize(n_);
	sz.resize(n_);
	ra.resize(n_);
	rep(i, n_){
	    par[i] = i;
	    rank[i] = 0;
	    sz[i] = 1;
	    ra[i] = -1;
	}
    }
    
    inline int find(int x){
	if(par[x] != x) find(par[x]);
	if(ra[x] == -1) ra[x] = ra[par[x]] == -1 ? ra[par[par[x]]] : ra[par[x]];
	return par[x] = par[par[x]];
    }

    void unite(int x, int y){
	x = find(x); y = find(y);
	if(x == y) return ;

	if(rank[x] < rank[y]){
	    par[x] = y;
	    sz[y] += sz[x];
	}else{
	    par[y] = x;
	    sz[x] += sz[y];
	    rank[x] += (rank[x] == rank[y]);    
	}
    }

    inline bool same(int x, int y){ return find(x) == find(y); }
    inline int get_rate(int x){ return ra[x]; }
    inline int get_sz(int x){ return sz[find(x)]; }
}uf;

pair<int, P > e[500010];
int val[510][510];
int st[250010];
int now;
ll ret;

int main(){
    freopen("skilevel.in", "r", stdin);
    freopen("skilevel.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &t);
    rep(i, n) rep(j, m)	scanf("%d", &val[i][j]);
    rep(i, n * m) scanf("%d", &st[i]);
    rep(i, n){
	rep(j, m){
	    if(j < m - 1) e[now++] = mp(abs(val[i][j] - val[i][j+1]), mp(i * m + j, i * m + j + 1));
	    if(i < n - 1) e[now++] = mp(abs(val[i][j] - val[i+1][j]), mp(i * m + j, (i + 1) * m + j));
	}
    }
    sort(e, e + now);
    uf.init(n * m);

    rep(i, now){
	int cost = e[i].fi;
	int a = e[i].se.fi, b = e[i].se.se;
	if(uf.same(a, b)) continue;
	a = uf.find(a); b = uf.find(b);
	int as = uf.get_sz(a), bs = uf.get_sz(b);
	if(as + bs >= t){
	    if(as < t) uf.ra[a] = cost;
	    if(bs < t) uf.ra[b] = cost;
	}
	uf.unite(a, b);
    }
    rep(i, n * m) if(st[i]){
	uf.find(i);
	ret += uf.get_rate(i);
    }
    printf("%lld\n", ret);
    return 0;
}