ABC 009 D-漸化式

問題:D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder
参考:Abc009

まず、ビット演算をそれぞれ非負の整数に対し
XOR(^)->足し算っぽいもの AND(&)->掛け算っぽいもの
とみなすことでこれらを用いて普通の行列と同様の方法で演算を行うことができる。
ここでの足し算っぽさ、掛け算っぽさは半環の性質によって与えられる(?)。(抽象代数学について学べばこの辺りの理論に詳しくなれそう)
あとは、AND演算に対する単位元が1でなく2^n-1(nは十分に大きい整数)(二進数で全ての桁が1)であることに注意すれば通常の行列の演算が使える。
そして、漸化式を行列を用いて表して、その公比っぽい行列を累乗して、初項っぽいベクトルを掛けることで答えが求まる。
行列の累乗には繰り返し二乗法を用いる

計算量は行列積にO(K^3)m乗の計算にO(log m)かかるので
全体としてO(K^3 log m)

#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

mat mul(mat& A,mat& B){
	mat C(A.size(),vec(B[0].size()));
	for(int i=0;i<A.size();i++){
		for(int j=0;j<B[0].size();j++){
			for(int k=0;k<A[0].size();k++){
				C[i][j]^=A[i][k]&B[k][j];
			}
		}
	}
	return C;
}

mat pow(mat A,int n){
	mat B(A.size(),vec(A.size()));
	for(int i=0;i<A.size();i++){
		B[i][i]=UINT_MAX;
	}
	while(n>0){
		if(n&1)B=mul(B,A);
		A=mul(A,A);
		n>>=1;
	}
	return B;
}

int main(){
	int k,m;
	cin>>k>>m;
	mat A(k,vec(1));
	for(int i=0;i<k;i++){
		cin>>A[k-i-1][0];
	}
	mat B(k,vec(k));
	for(int i=0;i<k;i++){
		cin>>B[0][i];
	}
	for(int i=0;i+1<k;i++)B[i+1][i]=UINT_MAX;
	B=pow(B,m-1);
	A=mul(B,A);
	cout<<A[k-1][0]<<endl;
}

UVa 11297 Census

問題 : UVa Online Judge

二次元のセグメントツリーで値の更新、クエリに対して矩形内の最大値、最小値を求める。

#include<iostream>
#include<stdio.h>
using namespace std;

const int MAX_N=500;
const int INF=200000000;
struct info{
	info(){}
	info(int mi_,int ma_):mi(mi_),ma(ma_){}
	int mi;
	int ma;
};

info seg[4*MAX_N][4*MAX_N];
int n;

void init(int n_){
	n=1;
	while(n<n_)n*=2;
	for(int i=0;i<2*n-1;i++){
		for(int j=0;j<2*n-1;j++){
			seg[i][j]=info(INF,-1);
		}
	}
}

void update(int a,int b,int x){
	b+=n-1;
	a+=n-1;
	seg[a][b]=info(x,x);
	int r=b;
	while(a>0){
		r=b;
		while(r>0){	
			r=(r-1)/2;
			seg[a][r]=info(min(seg[a][2*r+1].mi,seg[a][2*r+2].mi),max(seg[a][2*r+1].ma,seg[a][2*r+2].ma));
		}

		a=(a-1)/2;
		seg[a][b]=info(min(seg[2*a+1][b].mi,seg[2*a+2][b].mi),max(seg[2*a+1][b].ma,seg[2*a+2][b].ma));
		
	}
}

info query(int a,int x1,int x2,int k,int l,int r){
	if(x1>=r || x2<=l)return info(INF,-1);
	if(x1<=l && x2>=r){
		return seg[a][k];
	}
	else{
		info ql=query(a,x1,x2,2*k+1,l,(l+r)/2);
		info qr=query(a,x1,x2,2*k+2,(r+l)/2,r);
		return info(min(ql.mi,qr.mi),max(ql.ma,qr.ma));
	}
}

info main_query(int x1,int y1,int x2,int y2,int k,int l,int r){
	if(y1>=r || y2<=l)return info(INF,-1);
	if(y1<=l && y2>=r){
		return query(k,x1,x2,0,0,n);
	}
	else{
		info ql=main_query(x1,y1,x2,y2,2*k+1,l,(l+r)/2);
		info qr=main_query(x1,y1,x2,y2,2*k+2,(r+l)/2,r);
		return info(min(ql.mi,qr.mi),max(ql.ma,qr.ma));
	}
}

int main(){
	int N;
	cin>>N;
	init(N);
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			int t;
			scanf("%d",&t);
			update(i,j,t);
		}
	}
	int Q;
	cin>>Q;
	for(int i=0;i<Q;i++){
		char q;
		scanf(" %c",&q);
		if(q=='q'){
			int x1,y1,x2,y2;
			scanf("%d%d%d%d",&y1,&x1,&y2,&x2);
			info ans=main_query(x1-1,y1-1,x2,y2,0,0,n);
			printf("%d %d\n",ans.ma,ans.mi);
		}
		else{
			int x,y,v;
			scanf("%d%d%d",&y,&x,&v);
			update(y-1,x-1,v);
		}
	}
}

バグを生やし続けて辛かった。

(今回の)二次元のセグメントツリーについて:
一次元のセグメントツリーseg[a]が値でなくセグメントツリーを持っている。
seg[a]は結果的に(子を持てば)seg[a][k].ma=max(seg[2*a+1][k].ma,seg[2*a+2][k].ma)
seg[a][k].miも同様、となっている。つまり、seg[a]はaに対応する区間(ex.a=0 -> [0,n) )でセグメントツリーを合体させた(いらないところ(最大、最小とならない)を削った)もの。

CF #354(Div2) E - The Last Fight Between Human and AI

問題 : Problem - 676E - Codeforces

概要 : n次多項式P(x)の係数を相手(AI?)と交互に決めて行って最終的にそれが(x-k)で割り切れたら人間の勝利。この問題では、その途中の段階での既に決まっている係数が与えられる。

解法 : まず、剰余の定理からP(k)=0になれば人間の勝利であることが分かる。
あとは、色々工夫して場合分けしたり、計算したりして判定する。実際P(k)の値を求めなくてはいけないのは全ての係数が決まってしまっている時だけ。

#include<iostream>
#include<string>
using namespace std;

const long long mod=1000000000000037;

long long a[100005];
long long x[100005];

int main(){
	int n,k;
	cin>>n>>k;
	int count=0;
	for(int i=0;i<=n;i++){
		string str;
		cin>>str;
		if(str=="?"){
			a[i]=mod;
			count++;
		}
		else a[i]=atoi(str.c_str());
	}

	if(k==0){
		if(a[0]==0){
			cout<<"Yes"<<endl;
		}
		else if(a[0]==mod){
			if((n-count)%2==0){
				cout<<"Yes"<<endl;
			}
			else cout<<"No"<<endl;
		}
		else cout<<"No"<<endl;
		return 0;
	}

	if(count>0){
		if(n%2)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		return 0;
	}
	long long sum=a[0];
	x[0]=1;
	for(int i=1;i<=n;i++){
		x[i]=(x[i-1]*k)%mod;
		sum=(sum+x[i]*a[i])%mod;
	}
	if(sum==0)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

反省 : k=0の時の場合分けに気付けなかった。mod=1000000007(有名な素数)では落ちるケースが用意されていた。結論modは素数でなくても十分に大きい数なら結局何でも良かった。ただ、この解法をとると適当なテストケースで落ちる可能性が少なからず残る。が、modを適当に何種類も試してどれでやっても全てP(k)=0となれば割りと正しいはず。P(k)が大きくなりすぎ得ることに対して、適当な素数での余りのP(k)%mod=0とするしか、能がなかった。

CF #354(Div2) D - Theseus and labyrinth

問題 : Problem - 676D - Codeforces

概要 :
テセウスがミノタウロスを倒しに行く、その最短経路を求める。
N*Mのフィールドが与えられて、それぞれのブロックについて上下左右それぞれに扉が付いているかどうかの情報が与えられる。そして、あるブロックとその4近傍のブロックの接している辺にどちらのブロックも扉を持っていたら、それらのブロック間は移動可能。
テセウスが一回にできることは以下の二つ。
・今いるところから移動可能な隣接するブロックに移動する。
・全てのブロックを時計回りに90度回転させる

解法 :

bfs

このフィールドが取り得る状態は4つだけなので(∵4回転すれば元に戻る)ブロック全てを90度回転させたのを一つ上のフィールドとみなして、4近傍+上に登るの5方向に対してbfsを行うことで最短経路長が求まる。

#include<iostream>
#include<string>
#include<stdio.h>
#include<string.h>
#include<queue>

using namespace std;


const int INF=100000000;
const int dx[]={0,1,0,-1};
const int dy[]={-1,0,1,0};

int id[12][4]={  //{up,right,down,left}
	{1,1,1,1},
	{0,1,0,1},
	{1,0,1,0},
	{1,0,0,0},
	{0,1,0,0},
	{0,0,0,1},
	{0,0,1,0},
	{1,1,1,0},
	{1,0,1,1},
	{0,1,1,1},
	{1,1,0,1},
	{0,0,0,0}
};
string i_str="+-|^><vLRUD*";

struct P{
	int x,y,z;
	P(int a,int b,int c):x(a),y(b),z(c){}
};

struct cell{
	int  movable[4];
	int dist;
	cell(char c){
		fill(movable,movable+4,0);
		dist=INF;
		memcpy(movable,id[i_str.find(c)],sizeof(movable));
	}
	cell(cell* c){
		dist=INF;
		for(int i=0;i<4;i++){
			movable[(i+1)%4]=c->movable[i];
		}
	}
};

cell* data [4][1002][1002];    //data[z][x][y]
int H,W;
int s_x,s_y,g_x,g_y;

bool is_movable(P from,P to,int d){
	if(data[from.z][from.x][from.y]->movable[d]==1 && data[to.z][to.x][to.y]->movable[(d+2)%4]==1){
//		cout<<"("<<from.x<<","<<from.y<<","<<from.z<<") -> ("<<to.x<<","<<to.y<<","<<to.z<<")"<<endl;
		return true;
	}
	return false;
}

void bfs(){
	queue<P> que;
	que.push(P(s_x,s_y,0));
	while(!que.empty()){
		P p=que.front();que.pop();
		for(int i=0;i<4;i++){
			int nx=p.x+dx[i],ny=p.y+dy[i];
			if(is_movable(p,P(nx,ny,p.z),i)){
				if(data[p.z][p.x][p.y]->dist+1<data[p.z][nx][ny]->dist){
					data[p.z][nx][ny]->dist=data[p.z][p.x][p.y]->dist+1;
					que.push(P(nx,ny,p.z));
				}
			}
		}
		if(data[p.z][p.x][p.y]->dist+1<data[(p.z+1)%4][p.x][p.y]->dist){
			data[(p.z+1)%4][p.x][p.y]->dist=data[p.z][p.x][p.y]->dist+1;
			que.push(P(p.x,p.y,(p.z+1)%4));
		}
	}
}

int main(){
	cin>>H>>W;
	for(int i=0;i<=1001;i++){
		for(int j=0;j<=1001;j++){
			if(i>=1 && i<=H && j>=1 && j<=W){
				char c;
				cin>>c;
				data[0][j][i]=new cell(c);
			}
			else {
				data[0][j][i]=new cell('*');
			}
		}
	}
	cin>>s_y>>s_x>>g_y>>g_x;
	data[0][s_x][s_y]->dist=0;
	for(int l=1;l<4;l++){
		for(int i=0;i<=H+1;i++){
			for(int j=0;j<=W+1;j++){
				data[l][j][i]=new cell(data[l-1][j][i]);
			}
		}
	}

	bfs();
	int ans=INF;
	for(int i=0;i<4;i++){
		ans=min(ans,data[i][g_x][g_y]->dist);
	}
	if(ans==INF)ans=-1;
	cout<<ans<<endl;
}

個人的に実装が重かった(むっちゃ時間かかった)

Lines:直線

問題 : http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day4_24.pdf

解法:
最初何もない平面を考えてそこへ一本づつ順に与えられた直線を追加していく。
直線を追加するときその直線は 平面における交点の数+1個 の領域を通る(分割する)。
そのため、それぞれの直線について追加するときの平面における交点の数を調べていくことで答えが求まる。

#include<iostream>
#include<set>
#include<complex>
#include<vector>

#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)

using namespace std;
namespace std{
    template<class T> bool operator<(const complex<T> &a, const complex<T> &b){
        return a.real() == b.real() ? a.imag() < b.imag() : a.real() < b.real();
    }
};
typedef complex<double>P;

struct line{
	line(){};
	line(P a1,P a2){
		p1=a1;
		p2=a2;
	}
	P p1,p2;
};
double dot(P a, P b) {
  return (a.real() * b.real() + a.imag() * b.imag());
}
double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}
int is_intersected_l(P a1, P a2, P b1, P b2) {
  return !EQ( cross(a1-a2, b1-b2), 0.0 );
}
P intersection_l(P a1, P a2, P b1, P b2) {
  P a = a2 - a1; P b = b2 - b1;
  return a1 + a * cross(b, b1-a1) / cross(b, a);
}
int is_point_on_line(P a, P b, P c) {
  return EQ( cross(b-a, c-a), 0.0 );
}
int is_eq_line(line l1,line l2){
	return is_point_on_line(l1.p1,l1.p2,l2.p1) && is_point_on_line(l1.p1,l1.p2,l2.p2);
}
vector<line> table;

int che(line l){
	set<P>rem;
	vector<line>::iterator itr=table.begin();
	for(;itr!=table.end();itr++){
		line tmp=*itr;
		if(is_intersected_l(l.p1,l.p2,tmp.p1,tmp.p2)){
			rem.insert(intersection_l(l.p1,l.p2,tmp.p1,tmp.p2));
		}
		else if(is_eq_line(l,tmp))return 0;
	}
	table.push_back(l);
	return rem.size()+1;
}
int main(){
	int n;
	cin>>n;
	int ans=1;
	for(int i=0;i<n;i++){
		P p1,p2;
		cin>>p1.real()>>p1.imag();
		cin>>p2.real()>>p2.imag();
		ans+=che(line(p1,p2));
	}
	cout<<ans<<endl;
}

サンプル (領域の個数をSしておく)
0本目 S=1

1本目 S=2

二本目 S=4

三本目 S=7

四本目 S=11

あとは重なっている直線や交点に注意すれば大丈夫。

Google Chrome 更新 | 表示されない | Ubuntu

GoogleChromeを更新したら無題のタブが開かれるだけでwebページが表示されなくなった。
再起動したら正常に動いた。

2014/12/29

AOJ 0526 - Boat Travel

問題 : Boat Travel | Aizu Online Judge

JOI 2007 問題6

解法 :
ダイクストラ法でクエリごとに最短距離を計算する。

#include<iostream>

#define INF 5000000

using namespace std;
const int V=120;
int map[V][V]={INF};
int dis[V];
bool used[V];

int dijkstra(int s,int e){
	fill(dis,dis+V,INF);
	fill(used,used+V,false);
	dis[s]=0;
	while(true){
		int v=-1;
		for(int u=0;u<V;u++){
			if(!used[u] && (v==-1 || dis[u]<dis[v]))v=u;
		}
		if(v==-1)break;
		used[v]=true;
		for(int u=0;u<V;u++){
			dis[u]=min(dis[v]+map[v][u],dis[u]);
		}
	}
	if(dis[e]!=INF)return dis[e];
	else return -1;
}

int main(){
	int N,K;
	while(cin>>N>>K && N && K){
		fill((int*)map,(int*)map+V*V,INF);
		for(int loop=0;loop<K;loop++){
			int check;
			cin>>check;
			if(check==0){
				int s,e;
				cin>>s>>e;
				cout<<dijkstra(s,e)<<endl;
			}
			else {
				int c,d,e;
				cin>>c>>d>>e;
				map[c][d]=map[d][c]=min(map[c][d],e);
			}
		}
	}
}

ダイクストラ法の導入として良い問題でした。
おすすめです。