JOI 2015 本選参加記

昨日までJOIの本選に参加していました。
結果からいうと一応通過しました。
去年こんな感じで(JOI 2014 本選 - (#・∀・))
この時の悔しさを噛み締めながら一年やって来たので、通過できたことは素直に喜びたいと思います。

2/7

potetiと一緒に新神戸から新幹線に乗って,akouryy,eyさんと新大阪で合流。
僕の友達は小さいを解いた。添字でハマってかなり時間食った。
その他色々問題見かえしたりした。
参宮橋についてから、昼飯を食べていなかったのでpotetiとMTKに入った。
注文したあとによくよく考えるとプラクティス開始まで30分しかないことに気づく。
爆速で食べ終えて走ってオリセンへ。
3時58分に会場に入る(クズ)
プラクティスはサクっと全完して師匠やHIRさん、yokozuna氏たちとお話する。
その後の講演会は全く聞かずにPKUの問題考えてた。
その後、食事会。
自己紹介で言う事なかったので予選満点じゃなくて反省してるって言った気がする。
去年同様、筑駒の部誌もらったりsnukeさんやwoさん,hogloidさんなどチューターの方とお話したりした。
風呂でpotetiが汚い話をしていた気がする。
その後師匠とnamonaki氏とravenさんと一緒にpotetiの部屋に言って色々した。
11時45分頃に就寝。

2/8

6時20分に起床して着替えて飯を食って荷物片付けて鍵返して控え室でしばらく待って、会場の席に着いた。
競技開始。

1

imosやるだけ。15分くらいでAC.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int N,M;
int P[100100];
ll A[100100],B[100100],C[100100];
ll imos[100100];
int main()
{
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++)scanf("%d",&P[i]);
	for(int i=0;i<M;i++)P[i]--;
	for(int i=0;i<N-1;i++)scanf("%lld %lld %lld",&A[i],&B[i],&C[i]);
	for(int i=0;i<M-1;i++)
	{
		int start=P[i],end=P[i+1];
		if(start>end)swap(start,end);
		imos[start]++;
		imos[end]--;
	}
	for(int i=0;i<N;i++)imos[i+1]+=imos[i];
	ll ans = 0ll;
	for(int i=0;i<N-1;i++)
	{
		ll paper = A[i]*imos[i];
		ll IC = C[i]+B[i]*imos[i];
		ans += min(paper,IC);
	}
	printf("%lld\n",ans);
	return 0;
}

2

1分位考えて区間DPやるだけだな〜と思って書く。
慎重に書いたらコンパイルエラーでず、サンプルも全部通ってさすがにビックリした。
ちょっと怖くなったのでprintfしたりして確認したけどやっぱり合ってるので提出。
AC。(ここまで45分くらい)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int N;
ll A[4010];
ll dp[4010][4010];
ll rec(int l,int r)
{
	if(l>r)return 0ll;
	if(l==r)return A[l];
	if(dp[l][r]!=-1)return dp[l][r];
	ll res;
	ll eat_l,eat_r;
	if(A[l+1]<A[r])eat_l = rec(l+1,r-1)+A[l];
	else eat_l = rec(l+2,r)+A[l];
	if(A[l]<A[r-1])eat_r = rec(l,r-2)+A[r];
	else eat_r = rec(l+1,r-1)+A[r];
	res = max(eat_l,eat_r);
	return dp[l][r]=res;
}
int main()
{
	memset(dp,-1,sizeof(dp));
	scanf("%d",&N);
	for(int i=0;i<N;i++)scanf("%lld",&A[i]);
	for(int i=0;i<N;i++)A[i+N]=A[i];
	ll ans = 0ll;
	for(int i=0;i<N;i++)
	{
		//printf("%lld\n",rec(i,i+N-1));
		ans = max(ans,rec(i,i+N-1));
	}
	printf("%lld\n",ans);
	return 0;
}

3

さすがにココらへんでムズいの来るかなと思って身構えたけどまさかのdijkstraやるだけ。
この調子で行けば目標のメダル獲得いけるのでは、思ったりする。
AC。(ここまで1時間15分くらい)

#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
#define INF 30000000000000000ll
#define fi first
#define sec second
#define pb push_back
ll dist[100100];
ll ava[100100];
vector<P> vec;
int N,M;
ll C;
struct edge
{
	int to;
	ll cost;
	edge(int to,ll cost):to(to),cost(cost){}
};
vector<edge> g[100100];
void dijkstra()
{
	for(int i=0;i<N;i++)dist[i]=INF;
	dist[0]=0;
	priority_queue<P,vector<P>,greater<P> > q;
	q.push(P(0ll,0));
	while(!q.empty())
	{
		P a = q.top();
		q.pop();
		int v = a.sec;
		for(int i=0;i<g[v].size();i++)
		{
			edge e = g[v][i];
			if(dist[e.to]>dist[v]+e.cost)
			{
				dist[e.to]=dist[v]+e.cost;
				q.push(P(dist[e.to],e.to));
			}
		}
	}
	return;
}
int main()
{
	ll sum = 0ll;
	scanf("%d %d %lld",&N,&M,&C);
	for(int i=0;i<M;i++)
	{
		int a,b;
		ll c;
		scanf("%d %d %lld",&a,&b,&c);
		a--;b--;
		sum+=c;
		g[a].pb(edge(b,c));
		g[b].pb(edge(a,c));
	}
	dijkstra();
	for(int i=0;i<N;i++)vec.pb(P(dist[i],i));
	sort(vec.begin(),vec.end());
	ll ans = INF;
	for(int i=0;i<N;i++)
	{
		int v = vec[i].sec;
		//cout << v << endl;
		sum -= ava[v];
		ans = min(C*vec[i].fi+sum,ans);
		//cout << C*vec[i].fi << ' ' << sum << endl;
		for(int j=0;j<g[v].size();j++)
		{
			edge e = g[v][j];
			ava[e.to]+=e.cost;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

4

考えてみたけどイマイチよくわからなくて、制約的ににぶたんぽいなぁと踏んで、
判定関数以外のところをまず書いて、O(N)くらいで判定する方法を考えるもわからず。
とりあえず自明な部分点(8点)だけとって5へ。

5

去年の切り取り線みたいなヤバ問かと思ったら案外シンプルで解けそうだな〜と思いながら考える。
平面走査かなぁと踏んでsegtreeで平面走査して解けないか考えたり、PCKのFrameみたいに枠を半分に分けて出来ないかどうか考えたりしたけど結局わからず部分点を狙いに行く。
小課題1は2次元imosやるだけなのでOK.小課題2は包除原理でいけそうだなぁと思ったけど複数点通る枠の数を数えるのが複雑すぎて挫折。
とりあえず小課題1だけを取った(4点)

その後4の判定考えたり色々したけど時間だけが過ぎていき、競技終了。
100 + 100 + 100 + 8 + 4 = 312点
結果ほぼ0点同然の点だった。本当に自明な問題しか解いていないしとてもつらくなった。

競技終了直後に師匠に点数を聞いたら笑顔で全完と言っていてさすがだなぁと思った
解説を聞いた。4番はやはり予想は合っていたらしく、O(N)の判定が美しくて感動した。
反省しないといけないのは、三分木に見えていなかったことで、そう見えていればあとはできたと思う。
5番もそこまでヤバくなかったし、解けないといけない問題だった。

で、その後は特になにもなく帰りました。

今日のお昼に学校で春合宿にいけると知りました。
正直落ちたんじゃないかと思っていたので、ボーダーぎりぎりとはいえチャンスをつかめたので
嬉しいです。

更に実力をあげて、春合宿に望むつもりです。