Hatena::Grouptopcoder

Hiro180の日記

 | 

2013-12-31

SRM 602 && CF#222 (Div2) && bad bye 2013 10:50

SRM 602


Easy:

mapでDPをする。TLEは回避できたので提出


//Bokan ga bokka--nn!! 
//Daily Lunch Special Tanoshii !! 
#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> 
#include <sstream>  
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 TypoCoderDiv1{ 
public: 
int getmax(vector <int> D, int X) 
{ 
  map<int,int>dp[55]; 
  dp[0][X]=0; 
  for(int i=0;i<D.size();i++) 
  { 
    for(map<int,int>::iterator it=dp[i].begin();it!=dp[i].end();it++) 
    { 
      int x=it->first; 
      if(x>=2200) 
      { 
        dp[i+1][max(0,x-D[i])]=max(dp[i+1][max(0,x-D[i])],it->second+1); 
      } 
      else 
      { 
        int s=0; 
        if(x+D[i]>=2200) s++; 
        if(i!=D.size()-1 && x+D[i]-D[i+1]>=2200) goto next; 
        dp[i+1][x+D[i]]=max(dp[i+1][x+D[i]],it->second+s); 
        next:; 
        dp[i+1][max(0,x-D[i])]=max(dp[i+1][max(0,x-D[i])],it->second); 
      } 
    } 
  } 
  int ret=0; 
  for(map<int,int>::iterator it=dp[D.size()].begin();it!=dp[D.size()].end();it++) 
  { 
    ret=max(ret,it->second); 
  } 
  return ret; 
} 
};

Med: たて<よこ固定していいと気づかなかったのでぽよ

チャレンジ 落とせぬ

systest 通る

1706->1774(+68)

2013年 1127->1774でした。

来年はMed1/3とredcoderになることを

目標にします


Cf #222


A,B やるだけ

C 良問です(白目)

//Daily Lunch Special Tanoshii !!
#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 ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i<x;i++)
char f[505][505];
bool ok[505][505]={};
int main()
{
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0;i<n;i++)
	{
			scanf("%s",&f[i]);
	}
	if(!k)
	{
			for(int i=0;i<n;i++) printf("%s\n",f[i]);
			return 0;
	}
	int cur=0;
	queue<P>que;
	int emptyc=0;
	for(int i=0;i<n;i++)
	{
			for(int j=0;j<m;j++)
			{
				if(f[i][j]=='.')
				{
					if(que.empty()) que.push(mp(i,j));
					emptyc++;
				}
			}
	}
	
	while(!que.empty())
	{
		P p=que.front(); que.pop();
		if(ok[p.first][p.second]) continue;
		ok[p.first][p.second]=true;
		cur++;
		if(cur==emptyc-k)
		{	
			for(int i=0;i<n;i++)
			{
				for(int j=0;j<m;j++)
				{
					if(!ok[i][j] && f[i][j]=='.') f[i][j]='X';
				}
			}
			for(int i=0;i<n;i++) printf("%s\n",f[i]);
			return 0;
		}
		int dx[4]={0,1,0,-1};
		int dy[4]={1,0,-1,0};
		for(int i=0;i<4;i++)
		{
				int nx=p.first+dx[i];
				int ny=p.second+dy[i];
				if(!(0<=nx && nx<n)) continue;
				if(!(0<=ny && ny<m)) continue;
				if(!ok[nx][ny] && f[nx][ny]=='.')
				{
					que.push(mp(nx,ny));
				}
		}
	}
}

D: にぶたん

 que.pop();

systest 通る

11位

Rating 1641->1759 (+118)

good bye

A~C やるだけ

D 帰って

E~G ><

hack BでO(N^2log N)がいたので+1

systest D落ちる

rating 1759->1927(+168)


レートあがりすぎ...

 |