2014-02-12

■ SRM 526 21:20

Easy:

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

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

//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 DucksAlignment
{
	public:
	int minimumTime(vector  grid)
	{
		int n=grid.size();
		int m=grid[0].size();
		int tot=0;
		vector<int>x,y;
		for(int i=0;ifor(int j=0;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;ifor(int j=0;jint sum=0;
				//	tate
				if(i+tot-1>=n) goto nxt;
				for(int k=0;kfor(int k=0;knxt:;
				sum=0;
				//	yoko
				if(j+tot-1>=m) continue;
				for(int k=0;kfor(int k=0;kreturn 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 
#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
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) && (fiif(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苦手すぎる...

ツイートする