Hatena::Grouptopcoder

IH19980412の日記

 | 

2013-05-06

SRM578 & CF#182 Div1

14:18

まとめます

SRM 578

Easy:

・問題文を理解するのに時間を食う

・要は距離D以下の鳥をつなげてUFするだけ

・あとはDPする

・鳥がいないマスを消していなかったのでさらに時間を食う(絶望)

submit

#include <cstdio> 
#include <cstring> 
#include <cstdlib> 
#include <cmath> 
#include <string> 
#include <algorithm> 
#include <vector> 
#include <queue> 
#include <stack> 
#include <functional> 
#include <iostream> 
#include <map> 
#include <set> 
using namespace std; 
typedef pair<int,int> P; 
typedef pair<int,P> P1; 
typedef pair<P,P> P2; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 2000000000 
#define mod 1000000007 
int par[4005]; 
int ran[4005]; 
void init(){ 
  for(int i=0;i<4005;i++){ 
    par[i]=i; 
    ran[i]=0; 
  } 
} 
int find(int x){ 
  if(par[x] == x){ 
    return x; 
  }else{ 
    return par[x]=find(par[x]); 
  } 
} 
void unite(int x,int y){ 
  x=find(x); 
  y=find(y); 
  if(x == y) return ; 
  if(ran[x]<=ran[y]){ 
    par[x]=par[y]; 
  }else{ 
    par[y]=par[x]; 
    if(ran[x] == ran[y]) ran[x]++; 
  } 
} 
bool same(int x,int y){ 
  return find(x)==find(y); 
} 
bool used[4005]={}; 
long long dp[2505][2]={}; 
class GooseInZooDivOne{ 
public: 
int count(vector <string> field, int dist){ 
vector<int>ko; 
ko.pb(0); 
int eo=0; 
  vector<string>vec=field; 
  init(); 
  int base=vec[0].size(); 
  for(int i=0;i<vec.size();i++) 
  { 
    for(int j=0;j<vec[0].size();j++) 
    { 
      if(vec[i][j]=='v') 
      {eo++; 
          for(int ii=0;ii<vec.size();ii++) 
          { 
            for(int jj=0;jj<vec[0].size();jj++) 
            { 
              if(vec[ii][jj]=='v' && !(i==ii && j==jj) && abs(i-ii)+abs(j-jj)<=dist) 
              { 
                unite(i*base+j,ii*base+jj); 
              } 
            } 
          } 
        } 
      else 
      { 
        used[i*base+j]=true; 
      } 
      } 
    } 
    int ep=0; 
  for(int i=0;i<vec.size()*base;i++) 
  { 
    if(used[i]) continue; 
    used[i]=true; 
    int cnt=1; 
    for(int j=i+1;j<vec.size()*base;j++) 
    {   
      if(same(i,j) && !used[j]) 
      { 
        used[j]=true; 
        cnt++; 
      } 
    } 
    ko.pb(cnt); 
    ep+=cnt; 
  } 
  cout << ep << " " << eo << endl; 
  for(int i=0;i<ko.size();i++) 
  { 
    printf("%d %d\n",i,ko[i]); 
  } 
  dp[0][0]=1; 
  for(int i=1;i<ko.size();i++) 
  { 
    if(ko[i]%2==0) 
    { 
      dp[i][0]=dp[i-1][0]+dp[i-1][0]; 
      dp[i][1]=dp[i-1][1]+dp[i-1][1]; 
    }else 
    { 
      dp[i][0]=dp[i-1][0]+dp[i-1][1]; 
      dp[i][1]=dp[i-1][1]+dp[i-1][0]; 
    }     
    dp[i][0]%=mod; 
    dp[i][1]%=mod; 
  } 
  return (int)dp[ko.size()-1][0]-1; 
  } 
};

Medium:

・おっ解けそう

・解けぬ

終了

Challenge メモ化してなくてこれ終わらないよねと思ったら終わってくれて萎えた

Systest 通る

o-- +0/-1

Rating 1436->1484(+48)

黄色が見えてきたなあ。次回become yellow したい

CF182#Div1

0:30->1:05(+0:35)

A:

・小さいN個をひっくり返して合計が減ったらおわり♪

・2WA

・これ負になるの0か1だけですむやん

・submit

//CF301
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int main(){
	int n;
	scanf("%d",&n);
	vector<int>num;
	vector<int>abss;
	for(int i=0;i<2*n-1;i++)
	{
		int e;
		scanf("%d",&e);
		num.pb(e);
		abss.pb(abs(e));
	}
	sort(num.begin(),num.end());
	sort(abss.begin(),abss.end());
	int minus=0;
	for(int i=0;i<num.size();i++)
	{
		if(num[i]<0)
		{
			minus++;
		}
	}
	int ret=0;
	if(minus%2==1 && n%2==0)
	{
		ret=-1*abss[0];
		for(int i=1;i<abss.size();i++)
		{
			ret+=abss[i];
		}
	}
	else{
		ret=0;
		for(int i=0;i<abss.size();i++)
		{
			ret+=abss[i];
		}
	}
	printf("%d\n",ret);
}

B:

・どう見ても辺(u,v)のコストを(abs(u.x-v.x)+abs(u.y-v.y))*D-a[v]にして最短経路する問題に見える

・submit

//CF301
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
long long d[105][105];
long long gen[105]={};
int V;
long long D;
void warshall_floyd(){
	for(int k=1;k<=V;k++){
		for(int i=1;i<=V;i++){
			for(int j=1;j<=V;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
}

int main(){
	cin >> V >> D;
	for(int i=2;i<V;i++)
	{
		cin >> gen[i];
	}
	P cor[105];
	for(int i=1;i<=V;i++)
	{
		int f,s;
		cin >> f >> s;
		cor[i].first=f;
		cor[i].second=s;
	}
	for(int i=1;i<=V;i++)
	{
		for(int j=1;j<=V;j++)
		{
			if(i==j) continue;
			int dis=abs(cor[i].first-cor[j].first);
			dis+=abs(cor[i].second-cor[j].second);
			long long cost=1LL*dis*D;
			cost-=gen[j];
			d[i][j]=cost;
		}
	}
	warshall_floyd();
	printf("%lld\n",d[1][V]);
}

D:

p[w]%p[q]==0 & w>=qと勘違いしていたので無理

(w<qでも問題ない)</ppp>

Systest 通る

oo--- +0/-0

Rating 2058->2058(Unrated)

(after contest)

D:

・よく知られていることだが、(1/1+1/2+...+1/N)≒log Nである

・つまり組(a,b)を{p[a],p[b]の片方が片方を割り切る}と定義すると

そのような組はNlog N個できる、そしてaの値で(a,b)をソートしておく。

・aの値の順に並べ、節点がカバーしている範囲内にaが存在するすべての組のbの値をソートしてもつsegtreeをくむ

・left,rightが与えられたときに,[left,right]に完全に含まれる節点で

 b以下の数がいくつあるかを調べる。これはにぶたんたんで出来る。

・segtreeの構成にO(N log^2 N),クエリ一つにO(log N log (N log N))≒O(log^2 N)かかるので

 時間計算量O(N log^2 N+M log^2 N),空間計算量O(N log^2 N)でできる。

・枝刈りして自明な操作をなくしてinlineつけてhogeしたら1984/2000 msで通った

・明らかにTLE解法...

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
vector<int>seg[(1<<19)];
int lim;
int inv[200005],n,q,s,le,ri;

inline void update()
{
	for(int i=((1<<18)+n)/2+1;i>=1;i--)
	{
		if(i==2 || i==6 || seg[i*2+1].size()+seg[i*2+2].size()==0) continue;
		seg[i].resize(seg[i*2+1].size()+seg[i*2+2].size());
		merge(seg[i*2+1].begin(),seg[i*2+1].end(),seg[i*2+2].begin(),seg[i*2+2].end(),seg[i].begin());
	}
}

inline int calc(int a,int b,int k,int l,int r)
{
	if(r<a || b<l) return 0;
	if(a<=l && r<=b)
	{
		int ret=upper_bound(seg[k].begin(),seg[k].end(),lim)-seg[k].begin();
		return ret;
	}
	return calc(a,b,k*2+1,l,l+(r-l+1)/2-1)+calc(a,b,k*2+2,l+(r-l+1)/2,r);
}

int main()
{
	scanf("%d %d",&n,&q);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&s);
		inv[s]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=2;i*j<=n;j++)
		{
			seg[min(inv[i],inv[i*j])+(1<<18)-1].pb(max(inv[i],inv[i*j]));
		}
	}
	for(int i=0;i<n;i++)
	{
		sort(seg[i+(1<<18)-1].begin(),seg[i+(1<<18)-1].end());
	}
	update();
	while(q--)
	{
		scanf("%d %d",&le,&ri);
		lim=ri-1;
		printf("%d\n",calc(le-1,ri-1,0,0,(1<<18)-1)+ri-le+1);
	}
	return 0;
}

もっとデータ構造に慣れたい。

 |