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)

やったね!!

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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/IH19980412/20130607