naoya_t@topcoder

Codeforces Beta Round #17 (Div.2)

22:17 |

• やってる事に気づき、途中から外野で問題を解いてみた。50分ぐらい
• これは自分のレーティング（lieutenant）だと参加できないのか？

A. Flag

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  int n,m;cin>>n>>m;
  int lastline=-1;
  bool yn=true;
  rep(r,n){
    string s;cin>>s;
    int co=s[0];
    if(r>0 && co==lastline) { yn=false;goto ans;}
    FOR(c,1,m-1) if(s[c]!=co) {yn=false;goto ans;}
    lastline=co;
  }
 ans:
  cout << (yn ? "YES" : "NO") << endl;
  return 0;
}

B. Burglar and Matches

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  int n,m;cin>>n>>m;
  vector<int> bs(11,0);
  rep(i,m){
    int ai,bi;cin >> ai >> bi;
    bs[bi] += ai;
  }
  int t=0;
  for(int j=10;j>=1;--j){
    if(bs[j]==0)continue;
    if(n==0)break;
    if(bs[j]>=n){
      t+=n*j; bs[j]-=n; n=0;
    } else {
      t+=bs[j]*j; n-=bs[j]; bs[j]=0;
    }
  }
  cout << t << endl;
  return 0;
}

C. Monitor

• 入力が2e9近い時、分数の演算をintでやると桁あふれする
• (x,y)=(2,4)のとき(1,2)と同様の結果を返さなくてはならない

int gcd(int m, int n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  if (m == n) return m;
  while (1) {
    if (m == 0) return n;
    if (n == 0) return m;
    if (m > n) m %= n; else n %= m;
  }
}

int main(){
  int a,b,x,y; cin>>a>>b>>x>>y;
  int g=gcd(x,y); x/=g; y/=g;
  int r=min(a/x, b/y);
  cout << r*x << " " << r*y << endl;
  return 0;
}

D. Logging

• 分が同じ行は10行まで、という制約を見落としてた

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  int n,ans;cin>>n;
  char buf[40]; cin.getline(buf,40);
  int lastm = 0, daych = 0, cnt=0;
  rep(i,n){
    cin.getline(buf,40);
    int hh = 10*(buf[1]-'0') + (buf[2]-'0'); if(hh==12) hh=0;
    int mm = 10*(buf[4]-'0') + (buf[5]-'0');
    if (buf[7]=='p') hh+=12;
    int m = hh*60 + mm;
    if (m==lastm) {
      cnt++; if (cnt>10) { daych++; cnt=1; }
    } else if (m < lastm) {
      daych++;
      lastm = m; cnt=1;
    } else {
      lastm = m; cnt=1;
    }
  }
  cout << 1+daych << endl;
  return 0;
}

E. Fish

• 確率問題。これは時間内に解けなくて放置。