naoya_t@topcoder

Codeforces Beta Round #4

Codeforces | 18:18 |

• http://codeforces.com/
• 初参戦
• registerしといたけど歯医者に寄って帰ったら21:15…
• やめとくか
• だが参加する
• 21:19参戦
• 問題読んで、どこからsubmitするのか探したが見つからない
• ログインしてなかった！
• コンテスト中に結果がわかるのか…ちょっと時間かかるけど
• 再submitできるのか！！！する機会がなかったけど
• 4問目がWAなのが分かったのは終戦後

Problem A: Watermelon

• 簡単な問題。
• コンテストのシステムのテストを人柱でやってるのねきっと
• Accepted
• なにこれ問題開いてからじゃなくてコンテスト開始からの経過時間で得点（というかペナルティ）が決まるのか。。。19分遅刻のペナルティが痛い

#include <iostream>
using namespace std;
main(){
  int w;
  cin >> w;//1-100
  if (w&1) {
    cout << "NO" << endl;
  } else if (w==2) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }
}

Problem B: Before an Exam

• これまた簡単な問題。
• 貪欲に行きました
• Accepted

#include <iostream>
#include <vector>

using namespace std;

main(){
  int d, // 1-30
      sumtime; // 0-240
  int lower=0, upper=0;
  cin >> d >> sumtime;
  int st = sumtime;
  vector<int> tl(d), td(d);
  for(int i=0;i<d;i++){
    int l, u;
    cin >> l >> u;
    st -= l;
    upper += (u-l);
    tl[i] = l; td[i] = u-l;
  }
  if (st < 0 || upper < st) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
    for(int i=0,rest=st;i<d;i++) {
      if (i>0) cout << ' ';
      cout << (tl[i] + min(rest,td[i]));
      rest -= td[i];
      if (rest < 0) rest = 0;
    }
    cout << endl;
  }
}

Problem C: Registration system

• またまた簡単な
• Accepted

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

#define found(s,e)  ((s).find(e)!=(s).end())

main(){
  int n; // 1-1e5
  cin >> n;
  
  map<string,int> m;
  for(int i=0;i<n;i++) {
    string name;
    cin >> name;
    if(found(m,name)) {
      cout << name << m[name]++ << endl;
    } else {
      cout << "OK" << endl;
      m[name] = 1;
    }
  }
}

Problem D: Mysterious Present

• これはちょっとめんどくさいか？
• 最長パス
• Wrong Answer

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

int cmp(int w1,int h1, int w2,int h2){
  if (w1 < w2 && h1 < h2) return 1;
  else if (w1 > w2 && h1 > h2) return -1;
  else return 0;
}
main(){
  int n, // 1-5000
      w, // 1-1e6
      h; // 1-1e6
  cin >> n >> w >> h;

  vector<vector<int> > z(n,vector<int>(n,0));
  vector<int> wi(n), hi(n);
  rep(i,n) cin >> wi[i] >> hi[i];

  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      z[i][j] = cmp(wi[i],hi[i], wi[j],hi[j]);
      z[j][i] = -z[i][j];
    }
  }
  vector<int> p(n,-1);
  rep(i,n) {
    bool b=true;
    rep(j,n) { if (j==i)continue;
      if (z[i][j]==1) { b=false;break; }
    }
    if (b) p[i]=0;
  }

  int maxs=0;
  map<pair<int,int>,int> pre;
  rep(s,n) {
    rep(i,n) { if (p[i]!=s)continue;
      rep(j,n) { if (j==i)continue; //if (p[j]<s)continue;
        if (z[j][i]==1) {
          p[j]=s+1;
          pre[make_pair(j,s+1)] = i;
          maxs=max(maxs,s+1); }
      }
    }
  }

  // result
  cout << maxs+1 << endl;
  if (maxs == 0) {
    cout << 1 << endl;
  } else {
    rep(i,n) { if(p[i]<maxs)continue;
      cout << 1+i;
      for(int s=maxs,j=i;s>0;s--) {
        int j2 = pre[make_pair(i,s)];
        cout << ' ' << 1+j2;
        j = j2;
      }
      cout << endl;
      break;
    }
  }
}

結果

109/404

http://codeforces.com/contest/4/standings

19分遅刻してなければ72/404か。

ログインしてなくても問題読めるからシステムとしては仕方ないけどペナルティ痛い。

で、初レーティングは1515で中尉(Lieutenant)。

...軍曹(Sergeant)なのに

今度は最初から参戦したいな