2014-02-11

■ SRM練習会とJMO本選とJOI本選4 00:12

SRM練習会

SRM458。

Easy:

蟻本が蟻本である所以を知っていれば解けます。

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//これは、頭が悪く競プロが世界で一番できないHIR180が
//IOI2014日本代表になるまでのN日間の記録である。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
class BouncingBalls
{
	public:
	double expectedBounces(vector <int> x, int T)
	{
		int n=x.size();
		int div=(1<int ret=0;
		for(int i=0;iint rt[15];
			for(int j=0;j>j)&1));
			}
			for(int i=0;ifor(int j=i+1;jint pos=x[i];
					int pos2=x[j];
					int posn=x[i]+T*(rt[i]?1:-1);
					int posn2=x[j]+T*(rt[j]?1:-1);
					if((posreturn (double)ret/(double)div;
	}
};

Med:

dp[i]=(価値i-1以下のコインを使うことですべての商品の残り金額をiの倍数にする時の最小値)

とすると、

dp[i*j]=min(dp[i*j],dp[i]+(すべての商品に対しi*jの倍数にするために使わなければならない価値iのコイン数の合計))となる。

これは、i以外のiの約数からiをつくるよりiをそのまま用いた方がいいことより明らか。

(要するに10を3つ集めて30をつくるより30のコインで払うのがいい、というような当たり前のこと)

前処理をしないと計算量が100000* log 100000 * 50になりmaxで1.4sくらいかかります。

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//これは、頭が悪く競プロが世界で一番できないHIR180が
//IOI2014日本代表になるまでのN日間の記録である。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
int dp[100005];
class NewCoins
{
	public:
	int minCoins(vector <int> price)
	{
		fill(dp,dp+100005,INF);
		dp[1]=0;
		//last coin's price is i, and dp[i] is minimum number of coin used and cost is under i-1
		for(int i=1;i<=50000;i++)
		{
			for(int j=2;i*j<=100000;j++)
			{
				int cost=0;
				for(int k=0;kint ret=INF;
		for(int i=1;i<=100000;i++)
		{
			int cost=0;
			for(int k=0;kreturn ret;
	}
};

Hard: こわい。解けない。無理。

238.85+345.90=584.75(当時46位)でした。

JMO本選

1:むずかしい

2:自明(3^b+1は8で割り切れないのでc<=2,よって全探索して、どうぞとなる)

3:クリーク関連の証明を頑張る。帰納法とか知らん

4,5: 典型かもしれないし実は簡単なのかもしれないが解けない

JOI本選4

移動距離をm、下がった距離をdとすると、この問題はm+dを最小化する問題となる。

このとき、各木において「m+dが最小でかつ最も位置の低い点」のみを考慮すればよいことを示す。この点をPとする。

m+dが等しい場合、明らかに下にいたほうがdを減らすためには有利で、mは「現在の高さ」は関係しないので

この場合は示せた。

m+dがこれより大のときを考える。当然この点(Qとする)はPより下にないと意味がない。

ところが、PとQの高さの差は高々m+dの差でしかないことがわかる。

よってQのほうがPよりよくなることはない。(高さの差の分しか有利にならないから。)

よってPのみ考えればよい。

このようなPを見つけるには以下のような方法で移動してdijkstraすればよい:

・普通に降りられるなら降りる。

・普通に降りると木を超えるのなら木の頂上に着くように降りてから行く。

・普通に降りると土に墜落する場合は、高さ0につくように上ってからいく。

・高さが道の長さ未満なら、諦めて、どうぞ。となる。

よって普通のdijkstra(に+aしたもの)やるだけ。どうみてもこの問題のジャンルはGreedyってそれ一番いわれてるから

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;
typedef pair P1;
#define INF 100000000000000000LL
#define mp make_pair
#define pb push_back
ll tree[100005];
vector
edge[100005];
ll d[100005];
int n,m; ll x;
int main()
{
	scanf("%d%d%lld",&n,&m,&x);
	for(int i=0;i"%lld",&tree[i]);
	}
	for(int i=0;iint a,b; ll v;
		scanf("%d%d%lld",&a,&b,&v);
		--a; --b;
		edge[a].pb(mp(b,v));
		edge[b].pb(mp(a,v));
	}
	fill(d,d+n,INF);
	priority_queue,greater >que;
	d[0]=0;
	que.push(mp(0,mp(0,x)));
	while(!que.empty())
	{
		P1 p=que.top(); que.pop();
       		ll time=p.first;
		int cur=p.second.first;
		ll hei=p.second.second;
        	if(d[cur]!=time) continue;
		for(int i=0;iint to=edge[cur][i].first;
			ll cost=edge[cur][i].second;
        		ll add=0;
			if(tree[cur]continue;
			if(hei-cost>tree[to])
			{
				add=(hei-cost-tree[to]);
			}
			if(d[to]>d[cur]+cost+add)
			{
				d[to]=d[cur]+cost+add;
				ll nxt=hei-cost-add;
				if(nxt<=0) nxt=0;
				if(nxt>tree[to]) nxt=tree[to];
				que.push(mp(d[to],mp(to,nxt)));
			}
		}
	}
	if(d[n-1]>INF/2LL) puts("-1");
	else printf("%lld%c",(d[n-1])*2LL+tree[n-1]-x,10);
}

たぶんこれ自分が本番時に出した25点解法より短い

ツイートする