Hatena::Grouptopcoder

IH19980412の日記

2013-06-07

SRM579,580 & Codeforces 183 , Croc Champ 2013 - Finals (online version, Div. 1) ,185

22:26

SRM 579

Easy:

・英語読解

・map使えば終わり

#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; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 2000000000 
class UndoHistory{ 
public: 
int minPresses(vector <string> lines) 
{ 
  map<string,int>ma; 
  ma[""]=1; 
  string za=""; 
  int ret=0; 
  for(int i=0;i<lines[0].size();i++) 
  {   
    za+=lines[0][i]; 
    ma[za]=1; 
    ret++; 
  } 
  ret++; 
  for(int i=1;i<lines.size();i++) 
  { 
    string zan=""; 
    int res=0; 
    for(int j=0;j<lines[i].size();j++) 
    {   
      zan+=lines[i][j]; 
      if(ma[zan]) res=j+1; 
      else ma[zan]=1; 
    } 
    int zas=0; 
    if(lines[i-1].size()<=lines[i].size()) 
    { 
      bool ok=true; 
      for(int j=0;j<lines[i-1].size();j++) 
      {   
        if(lines[i-1][j]!=lines[i][j]) 
        { 
          ok=false; 
          break; 
        } 
      } 
      if(ok) zas=lines[i-1].size(); 
    } 
    if(zas) 
    { 
      ret+=lines[i].size()-zas; 
    } 
    else 
    { 
      ret+=lines[i].size()-res+2; 
    } 
    ret++; 
  } 
  return ret; 
  } 
};

Medium

・ふつうのBitDP

・サンプル弱過ぎ

#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; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 100000000 
int dp[55][(1<<17)]; 
bool vis[55][(1<<16)]={}; 
vector<P>edge[55]; 
int open[55]; 
int cloze[55]; 
int dur[55]; 
class TravellingPurchasingMan{ 
public: 
int maxStores(int N, vector <string> interestingStores, vector <string> roads) 
{ 
  int m=interestingStores.size(); 
  for(int i=0;i<roads.size();i++) 
  { 
    int cur=0; 
    int p[4]; 
    int zan=0; 
    for(int j=0;j<roads[i].size();j++) 
    { 
      if(roads[i][j]==' ') 
      { 
        p[cur]=zan; 
        zan=0; 
        cur++; 
      } 
      else 
      { 
        zan*=10; 
        zan+=roads[i][j]-'0'; 
      } 
    } 
    if(zan) 
    { 
      p[cur]=zan; 
    } 
    edge[p[0]].pb(mp(p[1],p[2])); 
    edge[p[1]].pb(mp(p[0],p[2])); 
  } 
   
  for(int i=0;i<m;i++) 
  { 
    int cur=0; 
    int p[4]; 
    int zan=0; 
    for(int j=0;j<interestingStores[i].size();j++) 
    { 
      if(interestingStores[i][j]==' ') 
      { 
        p[cur]=zan; 
        zan=0; 
        cur++; 
      } 
      else 
      { 
        zan*=10; 
        zan+=interestingStores[i][j]-'0'; 
      } 
    } 
    if(zan) 
    { 
      p[cur]=zan; 
    } 
    open[i]=p[0]; 
    cloze[i]=p[1]; 
    dur[i]=p[2]; 
  } 
   
  queue<pair<int,int> > que; 
  for(int i=0;i<55;i++) for(int j=0;j<(1<<16);j++) dp[i][j]=INF; 
   
  //dp[a][b] a[\u12395][\u12356][\u12427],[\u20170][\u12414][\u12391][\u12398][\u35370][\u21839][\u28168][\u12415][\u12399]b[\u12398][\u12392][\u12365][\u12395][\u21205][\u12365][\u20986][\u12379][\u12427][\u31186][\u25968] 
   
  if(N-1<=m-1) 
  { 
    dp[N-1][(1<<(N-1))]=open[N-1]+dur[N-1]; 
    que.push(mp(N-1,(1<<(N-1)))); 
    dp[N-1][0]=0; 
    que.push(mp(N-1,0)); 
  } 
  else 
  { 
    dp[N-1][0]=0; 
    que.push(mp(N-1,0)); 
  } 
   
  while(!que.empty()) 
  { 
  // a is poz 
  // b is visited-V 
    P p=que.front(); 
    que.pop(); 
    int a=p.first; 
    int b=p.second; 
    if(vis[a][b]) continue; 
    vis[a][b]=true; 
    int now=dp[a][b]; 
    for(int i=0;i<edge[a].size();i++) 
    { 
      int c=edge[a][i].first; 
      int d=edge[a][i].second; 
      if(c<=m-1) 
      { 
        if(!((b>>c) & 1)) 
        { 
          if(now+d<=cloze[c]) 
          { 
            int st=max(now+d,open[c]); 
            dp[c][b | (1<<c)]=st+dur[c]; 
            que.push(mp(c,(b | (1<<c)))); 
            printf("%d %d %d %d\n",a,b,c,d); 
          }     
        } 
      } 
      else 
      { 
        dp[c][b]=now+d; 
        que.push(mp(c,b)); 
        printf("%d %d %d %d\n",a,b,c,d); 
      } 
    } 
  } 
   
  int ret=0; 
  for(int i=0;i<55;i++) 
  { 
    for(int j=0;j<(1<<16);j++) 
    { 
      if(dp[i][j]!=INF) 
      { 
        int g=j; 
        int res=0; 
        while(g) 
        { 
          res+=(g%2); 
          g/=2; 
        } 
        ret=max(ret,res); 
      } 
    } 
  } 
  return ret; 
  } 
};

Challenge はじめの店で購入することを考慮してないのを2撃墜 Easy撃墜される

誤発覚後我愚故深絶望。

Systest Medium落ちる\(^o^)/\(^o^)/\(^o^)/

xx- +2/-0

Rating 1484->0(-21)

SRM 580

Easy:

・決めうちゲー

#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; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 2000000000 
class EelAndRabbit{ 
public: 
int getmax(vector <int> l, vector <int> t) 
{ 
  vector<int>cor; 
  for(int i=0;i<l.size();i++) 
  { 
    cor.pb(l[i]+t[i]); 
    cor.pb(t[i]); 
  } 
  sort(cor.begin(),cor.end()); 
  cor.erase(unique(cor.begin(),cor.end()),cor.end()); 
  int ret=0; 
  for(int i=0;i<cor.size();i++) 
  { 
    for(int j=i+1;j<cor.size();j++) 
    { 
    int res=0; 
      for(int k=0;k<l.size();k++) 
      { 
        bool v=false; 
        if(t[k]<=cor[i] && cor[i]<=l[k]+t[k]) 
        { 
          v=true; 
        } 
        if(t[k]<=cor[j] && cor[j]<=l[k]+t[k]) 
        { 
          v=true; 
        }       
        if(v) 
        { 
          res++; 
        } 
      } 
      ret=max(ret,res); 
    } 
  } 
return ret; 
} 
};

Medium

・グラフに帰着してしまった(死)

Challenge 亀

Systest とおる

Rating 0->1503(+40)

やったね!!

clcxryisjcclcxryisjc2013/12/17 23:29tatocupqdpefs, <a href="http://www.hjvwtxospk.com/">hlntrjtise</a> , [url=http://www.oosjvritfo.com/]fwyxxskrsg[/url], http://www.proucxsxvs.com/ hlntrjtise

2013-05-06

SRM578 & CF#182 Div1

14:18

まとめます

SRM 578

Easy:

・問題文を理解するのに時間を食う

・要は距離D以下の鳥をつなげてUFするだけ

・あとはDPする

・鳥がいないマスを消していなかったのでさらに時間を食う(絶望)

submit

#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; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 2000000000 
#define mod 1000000007 
int par[4005]; 
int ran[4005]; 
void init(){ 
  for(int i=0;i<4005;i++){ 
    par[i]=i; 
    ran[i]=0; 
  } 
} 
int find(int x){ 
  if(par[x] == x){ 
    return x; 
  }else{ 
    return par[x]=find(par[x]); 
  } 
} 
void unite(int x,int y){ 
  x=find(x); 
  y=find(y); 
  if(x == y) return ; 
  if(ran[x]<=ran[y]){ 
    par[x]=par[y]; 
  }else{ 
    par[y]=par[x]; 
    if(ran[x] == ran[y]) ran[x]++; 
  } 
} 
bool same(int x,int y){ 
  return find(x)==find(y); 
} 
bool used[4005]={}; 
long long dp[2505][2]={}; 
class GooseInZooDivOne{ 
public: 
int count(vector <string> field, int dist){ 
vector<int>ko; 
ko.pb(0); 
int eo=0; 
  vector<string>vec=field; 
  init(); 
  int base=vec[0].size(); 
  for(int i=0;i<vec.size();i++) 
  { 
    for(int j=0;j<vec[0].size();j++) 
    { 
      if(vec[i][j]=='v') 
      {eo++; 
          for(int ii=0;ii<vec.size();ii++) 
          { 
            for(int jj=0;jj<vec[0].size();jj++) 
            { 
              if(vec[ii][jj]=='v' && !(i==ii && j==jj) && abs(i-ii)+abs(j-jj)<=dist) 
              { 
                unite(i*base+j,ii*base+jj); 
              } 
            } 
          } 
        } 
      else 
      { 
        used[i*base+j]=true; 
      } 
      } 
    } 
    int ep=0; 
  for(int i=0;i<vec.size()*base;i++) 
  { 
    if(used[i]) continue; 
    used[i]=true; 
    int cnt=1; 
    for(int j=i+1;j<vec.size()*base;j++) 
    {   
      if(same(i,j) && !used[j]) 
      { 
        used[j]=true; 
        cnt++; 
      } 
    } 
    ko.pb(cnt); 
    ep+=cnt; 
  } 
  cout << ep << " " << eo << endl; 
  for(int i=0;i<ko.size();i++) 
  { 
    printf("%d %d\n",i,ko[i]); 
  } 
  dp[0][0]=1; 
  for(int i=1;i<ko.size();i++) 
  { 
    if(ko[i]%2==0) 
    { 
      dp[i][0]=dp[i-1][0]+dp[i-1][0]; 
      dp[i][1]=dp[i-1][1]+dp[i-1][1]; 
    }else 
    { 
      dp[i][0]=dp[i-1][0]+dp[i-1][1]; 
      dp[i][1]=dp[i-1][1]+dp[i-1][0]; 
    }     
    dp[i][0]%=mod; 
    dp[i][1]%=mod; 
  } 
  return (int)dp[ko.size()-1][0]-1; 
  } 
};

Medium:

・おっ解けそう

・解けぬ

終了

Challenge メモ化してなくてこれ終わらないよねと思ったら終わってくれて萎えた

Systest 通る

o-- +0/-1

Rating 1436->1484(+48)

黄色が見えてきたなあ。次回become yellow したい

CF182#Div1

0:30->1:05(+0:35)

A:

・小さいN個をひっくり返して合計が減ったらおわり♪

・2WA

・これ負になるの0か1だけですむやん

・submit

//CF301
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int main(){
	int n;
	scanf("%d",&n);
	vector<int>num;
	vector<int>abss;
	for(int i=0;i<2*n-1;i++)
	{
		int e;
		scanf("%d",&e);
		num.pb(e);
		abss.pb(abs(e));
	}
	sort(num.begin(),num.end());
	sort(abss.begin(),abss.end());
	int minus=0;
	for(int i=0;i<num.size();i++)
	{
		if(num[i]<0)
		{
			minus++;
		}
	}
	int ret=0;
	if(minus%2==1 && n%2==0)
	{
		ret=-1*abss[0];
		for(int i=1;i<abss.size();i++)
		{
			ret+=abss[i];
		}
	}
	else{
		ret=0;
		for(int i=0;i<abss.size();i++)
		{
			ret+=abss[i];
		}
	}
	printf("%d\n",ret);
}

B:

・どう見ても辺(u,v)のコストを(abs(u.x-v.x)+abs(u.y-v.y))*D-a[v]にして最短経路する問題に見える

・submit

//CF301
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
long long d[105][105];
long long gen[105]={};
int V;
long long D;
void warshall_floyd(){
	for(int k=1;k<=V;k++){
		for(int i=1;i<=V;i++){
			for(int j=1;j<=V;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
}

int main(){
	cin >> V >> D;
	for(int i=2;i<V;i++)
	{
		cin >> gen[i];
	}
	P cor[105];
	for(int i=1;i<=V;i++)
	{
		int f,s;
		cin >> f >> s;
		cor[i].first=f;
		cor[i].second=s;
	}
	for(int i=1;i<=V;i++)
	{
		for(int j=1;j<=V;j++)
		{
			if(i==j) continue;
			int dis=abs(cor[i].first-cor[j].first);
			dis+=abs(cor[i].second-cor[j].second);
			long long cost=1LL*dis*D;
			cost-=gen[j];
			d[i][j]=cost;
		}
	}
	warshall_floyd();
	printf("%lld\n",d[1][V]);
}

D:

p[w]%p[q]==0 & w>=qと勘違いしていたので無理

(w<qでも問題ない)</ppp>

Systest 通る

oo--- +0/-0

Rating 2058->2058(Unrated)

(after contest)

D:

・よく知られていることだが、(1/1+1/2+...+1/N)≒log Nである

・つまり組(a,b)を{p[a],p[b]の片方が片方を割り切る}と定義すると

そのような組はNlog N個できる、そしてaの値で(a,b)をソートしておく。

・aの値の順に並べ、節点がカバーしている範囲内にaが存在するすべての組のbの値をソートしてもつsegtreeをくむ

・left,rightが与えられたときに,[left,right]に完全に含まれる節点で

 b以下の数がいくつあるかを調べる。これはにぶたんたんで出来る。

・segtreeの構成にO(N log^2 N),クエリ一つにO(log N log (N log N))≒O(log^2 N)かかるので

 時間計算量O(N log^2 N+M log^2 N),空間計算量O(N log^2 N)でできる。

・枝刈りして自明な操作をなくしてinlineつけてhogeしたら1984/2000 msで通った

・明らかにTLE解法...

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
vector<int>seg[(1<<19)];
int lim;
int inv[200005],n,q,s,le,ri;

inline void update()
{
	for(int i=((1<<18)+n)/2+1;i>=1;i--)
	{
		if(i==2 || i==6 || seg[i*2+1].size()+seg[i*2+2].size()==0) continue;
		seg[i].resize(seg[i*2+1].size()+seg[i*2+2].size());
		merge(seg[i*2+1].begin(),seg[i*2+1].end(),seg[i*2+2].begin(),seg[i*2+2].end(),seg[i].begin());
	}
}

inline int calc(int a,int b,int k,int l,int r)
{
	if(r<a || b<l) return 0;
	if(a<=l && r<=b)
	{
		int ret=upper_bound(seg[k].begin(),seg[k].end(),lim)-seg[k].begin();
		return ret;
	}
	return calc(a,b,k*2+1,l,l+(r-l+1)/2-1)+calc(a,b,k*2+2,l+(r-l+1)/2,r);
}

int main()
{
	scanf("%d %d",&n,&q);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&s);
		inv[s]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=2;i*j<=n;j++)
		{
			seg[min(inv[i],inv[i*j])+(1<<18)-1].pb(max(inv[i],inv[i*j]));
		}
	}
	for(int i=0;i<n;i++)
	{
		sort(seg[i+(1<<18)-1].begin(),seg[i+(1<<18)-1].end());
	}
	update();
	while(q--)
	{
		scanf("%d %d",&le,&ri);
		lim=ri-1;
		printf("%d\n",calc(le-1,ri-1,0,0,(1<<18)-1)+ri-le+1);
	}
	return 0;
}

もっとデータ構造に慣れたい。

2013-04-27

SRM577

19:04

久々のSRM。青に別れを告げに行く。

Easy:

・期待値?

・普通にやればいいよね

・(バグとの死闘)

・やっとサンプル通った...

・submit

#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; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 2000000000 
class EllysRoomAssignmentsDiv1{ 
public: 
double getAverage(vector <string> ratings){ 
vector<int>rate; 
int own; 
string go=""; 
  for(int i=0;i<ratings.size();i++) 
  { 
    go+=ratings[i]; 
  } 
  for(int i=0;i<go.size();i+=5) 
  { 
    int a=go[i]-'0'; 
    int b=go[1+i]-'0'; 
    int c=go[i+2]-'0'; 
    int d=go[i+3]-'0'; 
    rate.pb(a*1000+b*100+c*10+d); 
    if(!i) own=a*1000+b*100+c*10+d; 
  } 
  sort(rate.begin(),rate.end(),greater<int>()); 
  int room=rate.size(); 
  room=(room+19)/20; 
  if(room==1) 
  { 
    double sum=0.0; 
    for(int i=0;i<rate.size();i++) sum+=(double)rate[i]; 
    sum/=(double)rate.size(); 
    return sum; 
  } 
  double ret=0.0; 
  double beh; 
  bool out=false; 
  int div=0; 
  bool kak=0; 
  for(int i=0;;i++) 
  { 
    double res=0.0; 
    for(int j=i*room;j<min((int)rate.size(),(i+1)*room);j++) 
    { 
      res+=(double)rate[j]; 
      if(j==rate.size()-1) out=true; 
    } 
    res/=(double)(min((int)rate.size(),(i+1)*room)-i*room); 
    if(rate[i*room]>=own && own>=rate[min((int)rate.size(),(i+1)*room)-1]){ 
      res=(double)own; 
      if(out) kak=1; 
    } 
    if(out) beh=ret; 
    ret+=res; 
    div++; 
    if(out) break; 
  } 
  double ans; 
  if(!kak){ 
    ans=ret/(double)(div)*((double)(rate.size()%room==0?room:rate.size()%room)/(double)(room)); 
    ans+=beh/(double)(div-1)*((double)((room-rate.size()%room)==room?0:(room-rate.size()%room))/(double)(room)); 
  }else{ 
    ans=ret/(double)div; 
  } 
  return ans; 
  } 
};

Medium:

・貪欲?

・しらん

終わり

systest 通る

o-- +0/-0 355位

rating 1381->1436(+55) Highest

黄色にはなれなかったけど王手をかけたのでよしとする

あとマンハッタン距離の問題は45°回しましょう(戒め)

2013-04-24

Croc Champ 2013 - Round 2

05:56

とにかく二完を目標に。

A:

・最近ゲーム系多いなあ

・特に工夫はいらない?

・11,10,01の数でやればよさげ

書く。通った

#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int main(){
	int n;
	string a,b;
	cin >> n;
	cin >> a >> b;
	int r1=0,r2=0;
	int x=0,xy=0,y=0;
	for(int i=0;i<2*n;i++){
		if(a[i]=='0' && b[i]=='1') x++;
		if(a[i]=='1' && b[i]=='0') y++;
		if(a[i]=='1' && b[i]=='1') xy++;
		r1+=a[i]-'0';
		r2+=b[i]-'0';
	}
	int gen0=0,gen1=0;
	if(xy%2==0){
		gen0=gen1=xy/2;
		if(x>y){
			gen0+=(x-y+1)/2;
		}else{
			gen1+=(y-x)/2;
		}
	}
	else{
		gen0=xy/2+1;
		gen1=xy/2;
		if(x<y){
			gen1+=(y-x+1)/2;
		}else{
			gen0+=(x-y)/2;
		}
	}
	r1-=gen1;
	r2-=gen0;
	if(r1<r2){
		puts("Second");
	}else if(r1>r2){
		puts("First");
	}else{
		puts("Draw");
	}
}

B:

・縦+横<=11なのにN,M<=1000って...

・最大でもそんなに大きくならなそう

・全探索むずい><

・Cへ

C:

・(a+b+c)^3-a^3-b^3-c^3からa,b,cのあり得る場合の数か

・(a+b+c)^3-a^3-b^3-c^3=3(a+b)(a+c)(b+c)じゃん

・与えられた数を3で割って、その後X<=Y<=Z,X+Y>Z,X*Y*Z=(与えられた数/3)となるX,Y,Zを列挙か

書く。通る

#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
vector<long long>vec;
int main(){
	long long r;
	scanf("%lld",&r);
	if(r%3!=0){
		puts("0");
		return 0;
	}
	r/=3;
	for(long long i=1;i*i<=r;i++){
		if(r%i==0){
			vec.pb(i);
			if(i*i!=r){
				vec.pb(r/i);
			}
		}
	}
	sort(vec.begin(),vec.end());
	int ret=0;
	for(long long i=1;i*i*i<=r;i++){
		long long s;
		s=r/i;
		int F=lower_bound(vec.begin(),vec.end(),i)-vec.begin();
		for(int d=F;;d++){
			if(vec[d]*vec[d]>s){
				break;
			}
			if(s%vec[d]==0){
				long long a,b,c,D,e,f;
				a=i;
				b=vec[d];
				c=s/vec[d];
				if((a+b+c)%2==0 && a+b>c){
					D=(a+b+c)/2-a;
					e=(a+b+c)/2-b;
					f=(a+b+c)/2-c;
					if(D==f){
						ret++;
					}else if((D==e) || (e==f)){
						ret+=3;
					}else{
						ret+=6;
					}
				}
			}
		}
	}
	printf("%d\n",ret);
}

あとはすることがなかった><

systest 通る。

実はCでバグがあったんだけどなぜかとおってしまった(if(r%i==0){をいれていないので、本当は割り切れないパターンをカウントする恐れがあった)

rating 1936->2058(+122)

ここまで来ると赤くなってしまいたい(無理)

2013-04-21

Codeforces Round #180 (Div. 1)

21:03

とりあえず1800代キープを目標にする。

A:

SRMみたいな問題

・1000だからシュミレートかなあ

・めんどい(却下)

・何か注目すると良さそう

・!!!1の個数!!!

・もともと2n+1こあったら2n+2こまでにしか増やせない。もともと2nこあったら2nこまでにしか増やせない。

・もしかして任意の1をk個含む文字列から他の任意の1をk個含む文字列が作れる...?

・できる(1...1という長さkのをつくって、0を挟むだけ)

書く。通る。

#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int main(){
	string a,b;
	cin >> a >> b;
	int A=0,B=0;
	for(int i=0;i<a.size();i++){
		A+=a[i]-'0';
	}
	for(int i=0;i<b.size();i++){
		B+=b[i]-'0';
	}
	A+=(A%2);
	if(A<B){
		puts("NO");
	}else{
		puts("YES");
	}
}

B:

・またSRMみたいなのが来た...

・もし相手が自分のどの魚に対してもより大きいか同じな魚を持っていたらout

・じゃあそうじゃなかったら?

・仮にA,Bの魚を自分、相手が持っていたとすると(A>B)

・1~A-1を重さ0,B~Kを重さINFにすると、相手と自分の差が0かINF

・よって勝利

・あとN>Mなら必ず勝つよね(上と同様のことをする)

書く。通る。

#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
vector<int> N,M;
int main(){
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	if(n>m){
		puts("YES");
		return 0;
	}
	for(int i=0;i<n;i++){
		int s;
		scanf("%d",&s);
		N.pb(s);
	}
	for(int i=0;i<m;i++){
		int s;
		scanf("%d",&s);
		M.pb(s);
	}
	sort(N.begin(),N.end());
	sort(M.begin(),M.end());
	bool ok=false;
	for(int i=0;i<n;i++){
		if(N[i]>M[i+m-n]){
			ok=true;
		}
	}
	puts(ok?"YES":"NO");
}

C:

・解けぬ

HACK!!!

・怪しげなコードがある、hack敢行

・Unsuccessful...

・1missで部屋内4位->13位

・やばい(涙)

・ええい、Bhack解禁っ!!!

・お、意味の分からないことをしているひとがいる!!!もらった!!!

・Successful

・よっしゃ!!!

・13位->4位

・なんだこの僅差の戦いは(戦慄)

・チキン化

終わり〜

systest 通る

oo--- +1/-1 108位

rating 1806->1936(+130)

レートがハイパーインフレしてる...