Hatena::Grouptopcoder

Hiro180の日記

 | 

2013-08-02

SRMとかCFとかについて 13:58

Now rating:


SRM 1772(Highest 1772)

CF 1886 (Highest 2058)


Contents:


SRM

ここ二回83位->43位で+275. とてもいい感じ。

それぞれMedのジャンルが強実装,幾何で解けたのも大きい。

これからしばらくはMedを解くことを最優先に考えていこうと思います。

チャレンジもそれなりに頑張る。


参加記(SRM 586 & 587)


SRM 586


Easy

Easyなもんだい。

区間の数と端の点に分ければやるだけ。

面倒...

209.84pts

//E? Nandatte? 
#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  
PiecewiseLinearFunction{ 
public: 
int maximumSolutions(vector <int> Y) 
{ 
  vector<int>Z=Y; 
  for(int i=0;i<Y.size()-1;i++) 
  { 
    if(Y[i]==Y[i+1]) return -1; 
  } 
  sort(Z.begin(),Z.end()); 
  Z.erase(unique(Z.begin(),Z.end()),Z.end()); 
  int val[55]; 
  map<int,int>rev; 
  for(int i=0;i<Z.size();i++) 
  { 
    val[i]=Z[i]; 
    rev[Z[i]]=i; 
  } 
  int inter[55]={}; 
  for(int i=1;i<Y.size();i++) 
  { 
    int a=rev[Y[i-1]]; 
    int b=rev[Y[i]]; 
    for(int j=min(a,b);j<max(a,b);j++) 
    { 
      inter[j]++; 
    } 
  } 
  int s=0; 
  for(int i=0;i<55;i++) 
  { 
    s=max(s,inter[i]); 
  } 
  map<int,int>num; 
  for(int i=0;i<Y.size();i++) 
  { 
    int g=Y[i],vl=0; 
    for(int j=0;j<Y.size()-1;j++) 
    { 
      if(Y[j]==g) vl++; 
      else if(Y[j]>g && Y[j+1]<g) vl++; 
      else if(Y[j]<g && Y[j+1]>g) vl++; 
    } 
    if(g==Y[Y.size()-1]) vl++; 
    s=max(s,vl); 
  } 
  return s; 
  } 
};

Medium

Reading-hardでやる気が98%減になるが頑張って読む

とりあえず面倒な入力をする間に


・国同士のずれの最小最大をもてばよさげ

・でも間接的な差はどう対処すればいいの

・あっWF(察し)

を思いついたのでひたすらやる。


void rec()

{

if(バグなし) return ;

バグを見つける->バグをつぶす

rec();

}

!!STACK OVERFLOW!!


となるも終了間際にサンプル通る。

出す

202.01pts

//E? Nandatte? 
#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 2000000 
  int beg[27][12],en[27][12]; 
  int match[27][12][27][12]={}; 
  int maxi[27][27]; 
  int mini[27][27]; 
class History{ 
public: 
string verifyClaims(vector <string> dynasties, vector <string> battles, vector <string> queries) 
{ 
  for(int i=0;i<27;i++) 
  { 
    for(int j=0;j<27;j++) 
    { 
      maxi[i][j]=INF; 
      mini[i][j]=INF; 
      if(i==j) 
      { 
        maxi[i][j]=0; 
        maxi[i][j]=0; 
      } 
    } 
  } 
  vector<string>a,b,c; 
  a=dynasties; b=battles; c=queries; 
  for(int i=0;i<a.size();i++) 
  { 
    string s=a[i]; 
    int ans=0,idx=0; 
    for(int j=0;j<s.size();j++) 
    { 
      if(s[j]==' ') 
      { 
        if(idx) en[i][idx-1]=ans-1; 
        if(j!=s.size()-1) beg[i][idx++]=ans; 
        ans=0; 
      } 
      else 
      { 
        ans*=10; 
        ans+=s[j]-'0'; 
      } 
    } 
    if(ans) 
    { 
        if(idx) en[i][idx-1]=ans-1; 
        ans=0;     
    } 
  } 
  string all=""; 
  for(int i=0;i<b.size();i++) all+=b[i]; 
  for(int i=0;i<all.size();i++) 
  {   
    string par=""; 
    while(all[i]!=' ' && i<all.size()) 
    { 
      par.pb(all[i]); 
      i++; 
    } 
    int s=par[0]-'A'; 
    int f=1; 
    int ddd=0; 
    while(par[f]!='-') 
    { 
      ddd*=10; 
      ddd+=par[f]-'0'; 
      f++; 
    } 
    f++; 
    int ss=par[f]-'A'; 
    int dddd=0; 
    for(int i=f+1;i<par.size();i++) 
    { 
      dddd*=10; 
      dddd+=par[i]-'0'; 
    } 
    match[s][ddd][ss][dddd]=true; 
    match[ss][dddd][s][ddd]=true; 
    int beg1=beg[s][ddd]; 
    int beg2=beg[ss][dddd]; 
    int en1=en[s][ddd]; 
    int en2=en[ss][dddd]; 
    maxi[s][ss]=min(maxi[s][ss],en1-beg2); 
    mini[s][ss]=min(mini[s][ss],en2-beg1); 
    maxi[ss][s]=mini[s][ss]; 
    mini[ss][s]=maxi[s][ss];   
    printf("s%d %d %d %d\n",s,ddd,ss,dddd); 
    printf("s%d %d\n",mini[s][ss],maxi[s][ss]);     
  } 
  for(int k=0;k<a.size();k++){ 
    for(int i=0;i<a.size();i++){ 
      for(int j=0;j<a.size();j++){ 
      if(i==j) continue; 
        maxi[i][j]=min(maxi[i][j],maxi[i][k]+maxi[k][j]); 
      } 
    } 
  }   
  for(int k=0;k<a.size();k++){ 
    for(int i=0;i<a.size();i++){ 
      for(int j=0;j<a.size();j++){ 
      if(i==j) continue; 
        mini[i][j]=min(mini[i][j],mini[i][k]+mini[k][j]); 
      } 
    } 
  }   
   
  for(int i=0;i<a.size();i++) 
  { 
    for(int j=0;j<a.size();j++) 
    { 
      mini[i][j]*=(-1); 
    } 
  } 
  string ret=""; 
  for(int i=0;i<c.size();i++) 
  { 
    string par=c[i]; 
    int s=par[0]-'A'; 
    int f=1; 
    int ddd=0; 
    while(par[f]!='-') 
    { 
      ddd*=10; 
      ddd+=par[f]-'0'; 
      f++; 
    } 
    f++; 
    int ss=par[f]-'A'; 
    int dddd=0; 
    for(int j=f+1;j<par.size();j++) 
    { 
      dddd*=10; 
      dddd+=par[j]-'0'; 
    } 
    printf("%d %d %d %d\n",s,ddd,ss,dddd); 
    printf("%d %d\n",mini[s][ss],maxi[s][ss]); 
    for(int dif=mini[s][ss];dif<=maxi[s][ss];dif++) 
    { 
      int p=beg[s][ddd]; 
      int q=en[s][ddd]; 
      int r=beg[ss][dddd]+dif; 
      int t=en[ss][dddd]+dif; 
      if(t<p || q<r) continue; 
      else 
      { 
        ret+='Y'; 
        break; 
      } 
    } 
    if(ret.size()==i) ret+='N'; 
  } 
  return ret; 
  } 
};

ちゃれんじ ふぇーず

Dezoo氏一つ分けてくだされ(懇願)

Systest 通る。初の2完

oo- +0/-0 411.85pts 83位

Rating 1497->1637(+140)


SRM587


Easy


Easy!!┗(^o^;)┓DPかな????wwWwwwWw┏(;^o^)┛

再帰かな??やっぱDPかな?????wWwWWww(´・`;)

こ…これ…これは…………やるだけだあああああ┗(^o^)┛WwwWww┏(^o^)┓ドコドコドコドコwwwwwwww

というわけで迷走して194.20pts(大草原)

//E? Nandatte? 
#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 
bool dp[4000005]={}; 
class JumpFurther{ 
public: 
int furthest(int N, int badStep) 
{ 
  int sum=0; 
  int g=INF; 
  for(int i=1;i<=N;i++) 
  { 
    sum+=i; 
    if(sum==badStep) { g=i; break;} 
  } 
  if(g==INF) return sum; 
  else return N*(N+1)/2-1; 
} 
};

Medium

くぅ~疲れましたw これにて黄色生活終了です!


と思った時期が僕にもありました(ゲス顔)

上きゅうり: W%2==0ならok

右きゅうり左きゅうり:対角線の長さをもち適当に足す

下きゅうり:一瞬とても面倒そうにみえるが平行に切れば超簡単

というわけで出来ました

306.99pts(全体17番目だってさ!)

//E? Nandatte? 
#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  
TriangleXor{ 
public: 
int theArea(int W) 
{ 
  vector<double>vec; 
  vector<double>rev; 
  double now=0.0; 
  for(int i=1;i<=W;i++) 
  { 
    double bs=(double)i; 
    double bb=(double)(i+W); 
    vec.pb(bs/bb-now); 
    rev.pb(bs/bb-now); 
    now=bs/bb; 
  } 
  reverse(rev.begin(),rev.end()); 
  double ret=0.0; 
  if(W%2==0) ret+=W*1.0/4.0; 
  double par=0.0; 
  for(int i=0;i<vec.size();i+=2) 
  { 
    par+=vec[i]; 
  } 
  par*=W; 
  ret+=par; 

  double all=W*1.0/4.0; 
  double cur=0.0; 
  for(int i=0;i<rev.size();i++) 
  { 
  double prev=cur; 
  cur+=rev[i]; 
    double now=all*(cur*cur*4.0-prev*prev*4.0); 
    if(i%2==W%2) 
    { 
      ret+=now*cur/(prev+cur); 
    } 
    else 
    { 
      ret+=now*prev/(prev+cur); 
    } 
  } 
  return floor(ret); 
  } 
};

Hard

同じ->同じ

違う->違うでないとだめなので

適当にやればよさげだが時間がない

ちゃれんじ ふぇーず

しらね

systest

通る。50位以内に入った!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

oo- +0/-0 501.19pts 43位

Rating 1637->1772(+135)

実装量も少ないし問題も面白いしイイ問題セットだった。

ir5さんありがとうございます


CF:

つらい

 |