Hatena::Grouptopcoder

IH19980412の日記

2013-04-14

Codeforces Round #179 (Div. 1)

00:42

コンテスト30分前に15歳になってました。

初陣をレートupで飾ろうとやる気を出す。

A:

・Segtreeや″だ″ーー

・!!!imos法!!!

・クエリの種類でimos->使われる個数にクエリごとの足す数を掛ける

・で再度imos法。

・書く->投げる->通る

これ明らかに10^5*10^5でオーバーフロー奴〜〜wwwいるよね...

いない(絶望)のでBへ

#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 num[100005];
long long query[100005][3];
long long imos[100005]={};
long long imoss[100005]={};
long long cou[100005]={};
long long sum[100005]={};
int main(){
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&num[i]);
	}
	for(int i=1;i<=m;i++){
		long long int a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		query[i][0]=a;
		query[i][1]=b;
		query[i][2]=c;
	}
	for(int i=0;i<k;i++){
		int g,j;
		scanf("%d %d",&g,&j);
		imos[g]++;
		imos[j+1]--;
	}
	for(int i=1;i<=m;i++){
		cou[i]=cou[i-1]+imos[i];
	}
	for(int i=1;i<=m;i++){
		query[i][2]*=cou[i];
	}
	for(int i=1;i<=m;i++){
		imoss[query[i][0]]+=query[i][2];
		imoss[query[i][1]+1]-=query[i][2];
	}
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+imoss[i];
	}
	for(int i=1;i<=n;i++){
		printf("%lld%c",sum[i]+num[i],i==n?'\n':' ');
	}
}

B:

・グラフこわい

Cへ

C:

・わからん

・状態でほげほげするのかな

Dへ

D:

・ad-hocのにおい

・英語読めない(しろめ)

Bへ

B:

・消すのは大変なので足していきたい

・消すノードを逆にして考えればいいのでは

・すると新しいノードを加えたときに変化する値は

 ・新ノード->旧ノード

 ・旧ノード->新ノード

 ・旧ノード->新ノード->旧ノードでもとの最短距離より短くなるとき

なので

・一個目は辺の向きを逆にしたグラフでdijkstra O(N^2)

・二個目はそのままdijkstra O(N^2)

・三個目はN^2通り試す

となり、O(N^3)でできる

・n<=500だけどまあ通るでしょ

・実装力不足による大量のバグ(絶望)

・書く->投げる->通る

#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;
typedef long long l;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000000000
l cost[505][505];
l rev_cost[505][505];
l c[505][505];
l rev_c[505][505];
l a[505][505];
l d[505];
l rev_d[505];
bool used[505]={};
bool rev_used[505]={};
vector<int>node;
int n; 
int V;
void dijkstra(int s){
	fill(d,d+n,INF);
	memset(used,0,sizeof(used));
	d[node[s]]=0;
	while(1){
		int v=-1;
		for(int u=0;u<V;u++){
			if(!used[node[u]] && (v==-1 || d[node[u]]<d[node[v]])){
				v=u;
			}
		}
		if(v==-1){
			break;
		}
		used[node[v]]=true;
		for(int i=0;i<V;i++){
			d[node[i]]=min(d[node[i]],d[node[v]]+cost[node[v]][node[i]]);
		}
	}
}
void rev_dijkstra(int s){
	fill(rev_d,rev_d+n,INF);
	memset(rev_used,0,sizeof(rev_used));
	rev_d[node[s]]=0;
	while(1){
		int v=-1;
		for(int u=0;u<V;u++){
			if(!rev_used[node[u]] && (v==-1 || rev_d[node[u]]<rev_d[node[v]])){
				v=u;
			}
		}
		if(v==-1){
			break;
		}
		rev_used[node[v]]=true;
		for(int i=0;i<V;i++){
			rev_d[node[i]]=min(rev_d[node[i]],rev_d[node[v]]+rev_cost[node[v]][node[i]]);
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cost[i][j]=INF;
			rev_cost[i][j]=INF;
			a[i][j]=INF;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			scanf("%lld",&c[i][j]);
			if(i==j) c[i][j]=INF;
			rev_c[j][i]=c[i][j];
		}
	}
	vector<long long>ans;
	for(int i=0;i<n;i++){
		int ru; scanf("%d",&ru); ru--;
		node.pb(ru);
	}
	reverse(node.begin(),node.end());
	ans.pb(0LL);
	l behind=0;
	V=1;
	for(int i=1;i<node.size();i++){
		for(int j=0;j<i;j++){
			cost[node[j]][node[i]]=c[node[j]][node[i]];
			cost[node[i]][node[j]]=c[node[i]][node[j]];
			rev_cost[node[j]][node[i]]=rev_c[node[j]][node[i]];
			rev_cost[node[i]][node[j]]=rev_c[node[i]][node[j]];
		}
		V++;
		dijkstra(i);
		rev_dijkstra(i);
		for(int j=0;j<i;j++){
			for(int k=0;k<i;k++){
				if(j!=k){
					if(a[node[j]][node[k]]!=INF && a[node[j]][node[k]]>rev_d[node[j]]+d[node[k]]){
						behind-=(a[node[j]][node[k]]-(rev_d[node[j]]+d[node[k]]));
						a[node[j]][node[k]]=rev_d[node[j]]+d[node[k]];
					}
					if(a[node[j]][node[k]]==INF){
						a[node[j]][node[k]]=rev_d[node[j]]+d[node[k]];
					}
				}
			}
		}
		for(int j=0;j<i;j++){
			a[node[j]][node[i]]=rev_d[node[j]];
			behind+=a[node[j]][node[i]];
		}
		for(int j=0;j<i;j++){
			a[node[i]][node[j]]=d[node[j]];
			behind+=a[node[i]][node[j]];
		}
		ans.pb(behind);
	}
	reverse(ans.begin(),ans.end());
	for(int i=0;i<n;i++){
		printf("%lld%c",ans[i],i==n-1?'\n':' ');
	}
}

長過ぎる...

あとは適当に問題を考えて終了間際に10^5*10^5をintでやっている人がいたのでおいしくいただきました。

終了!!

systest 通る

oo--- +1/-0

Rating 1764->1806(+42)

1800の壁を超えました!!

紫安定を目標に頑張ります。

2013-04-09

SRM 575

23:56

翌日塾でしたが参加しました。

Easy:

・N<=10^18なので明らかに約数をしらべればいい

・とりあえず奇数はBrusと仮定した。偶数(2)の個数とうまく対応させたい...

・最初変なことをするもsampleとおって提出。

Medium:

・数学ゲーのにおい

・しかしわからない(絶望)

・放棄

Easy(再)

・12で考えるとミスに気づく

・あっ、負けの手は(2をのぞき)奇数だ 偶数->奇数, 奇数->偶数という手がとれるか

->とれる(偶数のほうは奇数にする方法があり(2の冪乗はのぞく)、奇数からは偶数しか作れないから)

・奇数の側が突然2の冪乗を生やすのは不可->2の冪乗以外の偶数は勝ち、奇数は負け。

・2の冪乗について

・もし/2して負けの手になるなら勝ち

・そうでないと相手に2の冪乗でない偶数を渡すことになる->負けが生える

・よって2で割れる回数の偶奇に対応しそう

書く。投げる

#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 
class TheNumberGameDivOne{ 
public: 
string find(long long n){ 
if(n==1){ 
  return "Brus"; 
}  
  int res=0; 
  while(n%2==0){ 
    res++; 
    n/=2; 
  } 
  if(n!=1){ 
    if(res){ 
      return "John"; 
    }else{ 
      return "Brus"; 
    } 
  }else{ 
    if(res%2==0){ 
      return "John"; 
    }else{ 
      return "Brus"; 
    } 
  } 
} 
};

終わり〜〜〜

Challenge phase

焦って合ってるものを撃墜しようとしてしまった

Systest 通る

o-- +0/-1 50.0pts(大絶望)

Rating 1383->1381(-2)

50.0ptsの割に落ちなくて良かった。

はやく黄色になりたい

2013-04-06

このブログの趣旨です

23:18

HIR180,IH19980412というユーザー名でCodeforcesTopCoderに参加しています。

コンテストの参加記を書いていきたいと思います。よろしくお願いします。

(Codeforces rating: 1764,TopCoder rating; 1383)