HIR180's diary

ICPC World Finals 2022 を集大成に

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  
#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; 
#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;i1;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;iint inter[55]={}; 
  for(int i=1;iint a=rev[Y[i-1]]; 
    int b=rev[Y[i]]; 
    for(int j=min(a,b);jint s=0; 
  for(int i=0;i<55;i++) 
  { 
    s=max(s,inter[i]); 
  } 
  map<int,int>num; 
  for(int i=0;iint g=Y[i],vl=0; 
    for(int j=0;j1;j++) 
    { 
      if(Y[j]==g) vl++; 
      else if(Y[j]>g && Y[j+1]else if(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  
#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; 
#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  dynasties, vector  battles, vector  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; 
      } 
    } 
  } 
  vectora,b,c; 
  a=dynasties; b=battles; c=queries; 
  for(int i=0;iint ans=0,idx=0; 
    for(int j=0;jif(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;ifor(int i=0;i""; 
    while(all[i]!=' ' && iint 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;i10; 
      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;kfor(int i=0;ifor(int j=0;jif(i==j) continue; 
        maxi[i][j]=min(maxi[i][j],maxi[i][k]+maxi[k][j]); 
      } 
    } 
  }   
  for(int k=0;kfor(int i=0;ifor(int j=0;jif(i==j) continue; 
        mini[i][j]=min(mini[i][j],mini[i][k]+mini[k][j]); 
      } 
    } 
  }   
   
  for(int i=0;ifor(int j=0;j1); 
    } 
  } 
  string ret=""; 
  for(int i=0;iint 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;j10; 
      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
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かな？？？？ｗｗＷｗｗｗＷｗ┏(;^o^)┛

再帰かな？？やっぱDPかな？？？？？ｗＷｗＷＷｗｗ(´･｀;)

こ…これ…これは…………やるだけだあああああ┗(^o^)┛ＷｗｗＷｗｗ┏(^o^)┓ﾄﾞｺﾄﾞｺﾄﾞｺﾄﾞｺｗｗｗｗｗｗｗｗ

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

//E? Nandatte? 
#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; 
#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  
#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; 
#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;i2) 
  { 
    par+=vec[i]; 
  } 
  par*=W; 
  ret+=par; 

  double all=W*1.0/4.0; 
  double cur=0.0; 
  for(int i=0;idouble 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:

つらい