Hatena::Grouptopcoder

Hiro180の日記

 | 

2013-12-31

2014年の(意識高い)目標 00:12

<絶対達成すること>


・絶対にIOI2014に行く。日本代表になる。(迫真)

・全国統一高校生テストで10位以内に入る。



<達成すべきこと>


・PCKで金ですぽよする。

TopCoder, CodeforcesでRedcoderになる。

・オンサイトのプログラミングコンテストに出る(JOIIOI以外)



<達成できればうれしい>


・弐寺初段とる

・学校でそこそこの成績(10位くらい)をとる

・まじめに生きる

・人権を得る

2013を振り返る 16:16

イベントごとに評価

JOI...x 春合宿行きたかった

JJMO...x*INF クソクソ&クソ

広中杯...o 結構良い

挑戦状...ooo 9位はできすぎ

高校生テスト...oo 8位なので満足

中学生テスト... x 絶望

TC...oo Med3連続ACはうれしかった

CF...o 最後の復調+一時期の高騰

ほか...o おおむね順調

<まとめ>


1000人もらえるのに1006位でTシャツのがしたGCJの日の翌日が

9位だった挑戦状の日で、あの一晩で運の流れが好転した気がします

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: にぶたん


//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 long long ll;
typedef pair<ll,ll> P;
typedef pair<P,int> P1;
typedef pair<P,P> P2;

#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++)
P bug[100005];
ll abi[100005];
ll mon[100005];
P1 student[100005];
int ret[100005];
int main()
{
	int n,m;
	ll s;
	scanf("%d %d %lld",&n,&m,&s);
	ll bugmax=-1LL;
	ll abimax=-1LL;
	for(int i=0;i<m;i++)
	{
		ll bugg;
		scanf("%lld",&bugg);
		bug[i]=mp(bugg,i);
		bugmax=max(bugmax,bug[i].first);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&abi[i]);
		abimax=max(abimax,abi[i]);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&mon[i]);
		student[i-1]=mp(mp(abi[i],mon[i]),i);
	}
	if(bugmax>abimax)
	{
		puts("NO"); return 0;
	}
	sort(bug,bug+m,greater<P>());
	sort(student,student+n,greater<P1>());
//for(int i=0;i<m;i++) cout << bug[i].first << " " << bug[i].second << endl;
//for(int i=0;i<n;i++) cout << student[i].first.first << " " << student[i].first.second << " " << student[i].second << endl;
	int lb=0; int ub=100005;
	while(ub-lb>1)
	{
		int mid=(lb+ub)>>1;
		int cur=0;
		int bugn=0;
		priority_queue<P1,vector<P1>,greater<P1> >que;
		while(!que.empty()) que.pop();
		ll val=0LL;
		while(bugn<m)
		{
			while(cur!=n && student[cur].first.first>=bug[bugn].first)
			{
				que.push(mp(mp(student[cur].first.second,student[cur].first.first),student[cur].second));
				cur++; //cout << cur << " " << mid  << endl;
			}
			if(que.empty()){ lb=mid; goto end;}
			val+=que.top().first.first; que.pop();
			bugn+=mid; //if(mid==2) cout << bugn << endl;
		}
		if(val<=s) ub=mid;
		else lb=mid;
end:;
	}
	if(ub>=100001)
	{
		puts("NO"); return 0;
	}
	puts("YES");
		int mid=ub;
		int cur=0;
		int bugn=0;
		priority_queue<P1,vector<P1>,greater<P1> >que;
		while(!que.empty()) que.pop();
		ll val=0LL;
		while(bugn<m)
		{
			while(cur!=n && student[cur].first.first>=bug[bugn].first)
			{
				que.push(mp(mp(student[cur].first.second,student[cur].first.first),student[cur].second));
				cur++;
			}
			for(int i=bugn;i<min(bugn+mid,m);i++)
			{
				ret[bug[i].second]=que.top().second;
			}
			que.pop();
			bugn+=mid;
		}
		for(int i=0;i<m;i++)
		{
			printf("%d%c",ret[i],(i==m-1)?'\n':' ');
		}
}

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)


レートあがりすぎ...

 |