Hatena::Grouptopcoder

Hiro180の日記

 | 

2014-02-12

SRM 526 21:20

Easy:

てきとうなぎにDuckを直線状に並べる問題。コストの最小化をする。

直線の候補を試していく。 必要なコストはソートして比較するだけで求められる。


//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//これは、頭が悪く競プロが世界で一番できないHIR180が
//IOI2014日本代表になるまでのN日間の記録である。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#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 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<x;i++)
class DucksAlignment
{
	public:
	int minimumTime(vector <string> grid)
	{
		int n=grid.size();
		int m=grid[0].size();
		int tot=0;
		vector<int>x,y;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				tot+=(grid[i][j]=='o');
				if(grid[i][j]=='o') x.pb(i),y.pb(j);
			}
		}
		cout << x.size() << endl;
		sort(x.begin(),x.end());
		sort(y.begin(),y.end());
		int ret=INF;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				int sum=0;
				//	tate
				if(i+tot-1>=n) goto nxt;
				for(int k=0;k<y.size();k++)
				{
					sum+=abs(y[k]-j);
				}
				for(int k=0;k<x.size();k++)
				{
					sum+=abs(i+k-x[k]);
				}
				ret=min(ret,sum);
				nxt:;
				sum=0;
				//	yoko
				if(j+tot-1>=m) continue;
				for(int k=0;k<x.size();k++)
				{
					sum+=abs(x[k]-i);
				}
				for(int k=0;k<y.size();k++)
				{
					sum+=abs(j+k-y[k]);
				}
				ret=min(ret,sum);
			}
		}
		return ret;
	}
};

Medium:


まず先手が勝つか後手が勝つか考える。

しかし、このルールだとどう見ても後手有利であり、先手が勝てる場合は相当限られる。

そもそも後手が勝てなくなる時は、素数が連続しているはずであり、そんなものは2と3しかない。

すなわち、先手の目標は後手に3つにして渡すことであるとわかる。

後手はその前に先手を潰しておかないといけないが、そのためには

先手が1~Kいずれをとっても合成数になるようにしないといけない。

つまり、1~Nのなかに合成数がK+1個以上連続している箇所があるか、N-1~N-Kが合成数であるかのいずれかが達成されないといけないし、達成されれば必ず後手が勝てる。

(前者は連続してるところの最大値の+1を渡された時に1個取ればよい、後者なら先手は何もできない)

これで先手後手のどちらが勝者になるか分かった。


(1) 先手勝ちのとき


先手は取れる範囲にある最小の素数をとればいいし、

後手はとれないなら終了、とれるなら自明に1個取ればよい。(2,3以外の素数-1は合成数だから)


(2)後手勝ちのとき


後手はもし取れる範囲で先手を潰せるなら潰す。そうでないなら最小の合成数をとる。

先手はとれないなら終了、とれるなら最大の素数をとる。


あとはこれをコードに起こすだけ。Nが極端に小さいのは埋め込んだほうが楽だし安全。


//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//これは、頭が悪く競プロが世界で一番できないHIR180が
//IOI2014日本代表になるまでのN日間の記録である。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#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 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<x;i++)
bool notprime[500000];
int ret=0;
class PrimeCompositeGame
{
	public:
	int theOutcome(int N, int K)
	{
		if(N==1) return 0;
		if(N==2) return 0;
		if(N==3) return 1;
		if(N==4) return 1;
		notprime[1]=true;
		for(int i=2;i<=500000;i++)
		{
			if(notprime[i]) continue;
			for(int j=2;i*j<=500000;j++)
			{
				notprime[i*j]=true;
			}
		}
		int len=0; int max_interval=0,fi=-1;
		for(int i=N;i>=3;i--)
		{
			if(notprime[i]) len++;
			else
			{
				max_interval=max(max_interval,len);
				if(fi<0 && i!=N && !notprime[N]) fi=len;
				len=0;
			}
		}
		bool winner=((max_interval<=K) && (fi<K));
		if(winner)
		{
			int cur=N;
			int ret=0;
			while(1)
			{
				for(int i=max(3,cur-K);i<=cur-1;i++)
				{
					if(!notprime[i])
					{
						cur=i;
						ret++;
						break;
					}
				}
				if(cur==3) return ret;
				while(!notprime[cur])
				{
					cur--;
				}
				ret++;
			}
		}
		else
		{
			int cur=N;
			int ret=0;
			while(1)
			{
				int nxt=-1;
				for(int i=cur-1;i>=max(3,cur-K);i--)
				{
					if(!notprime[i])
					{
						nxt=i;
						break;
					}
				}
				if(nxt==-1) return -1*ret;
				cur=nxt; ret++; nxt=-1; int len=0,kak=-1;
				for(int i=max(3,cur-K);i<=cur;i++)
				{
					if(!notprime[i])
					{
						if(nxt==-1 && i-1>=cur-K && notprime[i-1])
						{
							nxt=i-1;
						}
						if(len>=K+1)
						{
							kak=i-1;
						}
						len=0;
					}
					else
					{
						len++;
					}
				}
				ret++;
				if(kak>=0) cur=kak;
				else cur=nxt;
			}
		}
	}
};

DP解法?何それおいしいの?

Codeforces #229 18:27

絶望が生える


A: std:set

B: b[i]=1に気をつけて掛け算

C: 余りごとに累積和

E: 遅延評価segtreeやるだけ

D: このセット内ではダントツの難問。解法はやるだけ。嘘解法で突き進んで死んでしまいました。

Greedy苦手すぎる...

 |