Hatena::Grouptopcoder

blu_rayの日記

2011-11-26

Codeforces Beta Round #95 Div2

| 19:44

xox---

敗北。

最近さぼってたつけがまわってきた。

A. cAPS lOCK / WA

問題が読めなかった。ひどい。

あんまりのてんぱりで、ここで長い時間ロスする。。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

bool isLowerCase(char c) {
  return 'a' <= c && c <= 'z';
}

char toUpperCase(char c) {
  if (!isLowerCase(c)) return c;
  return 'A' + (c - 'a');
}

char toLowerCase(char c) {
  return 'a' + (c - 'A');
}

int main() {
  string in;
  while (cin >> in) {
    if (in.size() == 1) {
      char res = 0;
      res = !isLowerCase(in[0]) ? toLowerCase(in[0]) : toUpperCase(in[0]);
      cout << res << endl;
      continue;
    }
    bool ok = true;
    for (int i = 1; i < in.size(); ++i) {
      if (isLowerCase(in[i])) {
        ok = false;
        break;
      }
    }
    if (ok) {
      rep (i,in.size()) {
        if (isLowerCase(in[i])) {
          in[i] = toupper(in[i]);
        } else {
          in[i] = tolower(in[i]);
        }
      }
    } 
    cout << in << endl;
    
  }
  return 0;
}

B. Opposites Attract / Accepted / 742(00:52)

これは調子悪い中運良くできたけど、遅すぎる。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
typedef long long ll;

int n;
ll a[22];

int main() {
  while (cin >> n) {
    memset(a, 0, sizeof(a));
    int temp;
    ll ans = 0, zeroCnt = 0;
    rep (i,n) {
      cin >> temp;
      if (temp == 0) {
        zeroCnt++;
      } else if (temp > 0) {
        a[temp]++;
      } else {
        a[-temp + 10]++;
      }
    }
    for (int i = 1; i <= 10; ++i) {
      ans += a[i] * a[i+10];
    }
    ans += zeroCnt * (zeroCnt-1) / 2;
    cout << ans << endl;
  }
  return 0;
}

C. The World is a Theatre / WA

intのオーバーフローでシステムテスト死亡。初歩的なみす。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
typedef long long ll;

const int MAX_N = 40;
ll dp[MAX_N][MAX_N];

// int rec(int n, int k) にしてた
ll rec(int n, int k) {
  if (dp[n][k] >= 0) return dp[n][k];
  if (n == k) {
    return 1;
  } else if (k == 1) {
    return n;
  } else if (0 < k && k < n) {
    return dp[n][k] = rec(n-1, k-1) + rec(n-1, k);
  }
  //cout << n << "C" << k << endl;
  return 1;
}

void init() {
  // rep (i,30+1) {
  //   dp[i][0] = dp[i][i] = 1;
  //   for (int j = 1; j < i; ++j)
  //     dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
  // }
  rep (i,40) rep (j,40) {
    dp[i][j] = -1;
  }
  rep (i,40) rep (j,40) {
    dp[i][j] = rec(i,j);
  }
}

int main() {
  init();
  int n, m, t;
  while (cin >> n >> m >> t) {
    ll ans = 0;
    for (int i = 4; i <= n; ++i) {
      int girls = t - i;
      if (girls < 1) break;
      if (girls > m) continue;
      ans += dp[n][i] * dp[m][girls]; 
    }
    cout << ans << endl;
  }
  return 0;
}

D. Subway

終了してから10分後くらいにできたけど、TLE臭がすごかったのに、

システムテスト後にPracticeで出したら通った。630ms。

枝が1つしかない頂点をグラフから順番に外していって閉路を見つけるようにしているけど、

外すときの情報を使うようにして高速化できてるひとがいた。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
typedef pair<int,int> P;

const int MAX_V = 3002;
vector<int> V[MAX_V];
vector<int> T[MAX_V];
int v;
set<int> cycle;

int main() {
  while (cin >> v) {
    rep (i,v) V[i].clear();
    int _u, _v;
    rep (i,v) {
      cin >> _u >> _v;
      _u--; _v--;
      V[_u].push_back(_v);
      V[_v].push_back(_u);
    }

    //vector<int> answers(v, 0);
    cycle.clear();
    rep (i,v) {
      T[i].assign(V[i].begin(), V[i].end());
    }
    rep (i,v) {
      // search size() == 1 vector
      vector<int> ts;
      rep (j,v) {
        if (T[j].size() == 1) ts.push_back(j);
      }
      if (ts.size() == 0) break;
      rep (j,v) {
        if (T[j].size() < 1) continue;
        rep (k,ts.size()) {
          T[j].erase(remove(T[j].begin(), T[j].end(), ts[k]), T[j].end());
        }
      }
      rep (j,ts.size()) {
        T[ ts[j] ].clear();
      }
    }
    rep (i,v) {
      if (T[i].size() > 0) cycle.insert(i);
    }

    rep (i,v) {
      if (cycle.count(i)) {
        cout << 0 << " ";
        continue;
      }

      bool used[MAX_V];
      fill(used, used + MAX_V, false);
      queue<P> que;
      que.push(P(i,0));
      while(!que.empty()) {
        P p = que.front(); que.pop();
        int cur = p.first;
        if (used[cur]) continue;
        used[cur] = true;
        if (cycle.count(cur)) {
          cout << p.second << " ";
          break;
        }
        rep (j,V[cur].size()) if (!used[ V[cur][j] ]) {
          que.push(P(V[cur][j], p.second+1));
        }
      }
    } cout << endl;
  }
  return 0;
}

E. Yet Another Task with Queens

この問題もよく読めばそこまで難しくなくて、たて、よこ、2種類のななめの

情報をもっておいて、あとで比較するだけ。

こっちは実行時間が910ms。set使ってるけど、普通にvectorをsort

するようにしても同じなので、完全にメモリと実行時間の無駄ですね。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

const int MAX_N = 100002;
int n, m, a[MAX_N][2];
set<int> x_axis[MAX_N], y_axis[MAX_N];
set<int> downL[2][MAX_N], downR[2][MAX_N];

int main() {
  while (cin >> n >> m) {
    rep (i,MAX_N) {
      x_axis[i].clear();
      y_axis[i].clear();
      rep (j,2) {
        downL[j][i].clear();
        downR[j][i].clear();
      }
    }

    rep (i,m) {
      cin >> a[i][0] >> a[i][1];
      x_axis[ a[i][1] ].insert(a[i][0]);
      y_axis[ a[i][0] ].insert(a[i][1]);
      const int d = min(a[i][0], a[i][1]);
      const int r = a[i][0] - d, c = a[i][1] - d;
      if (c > r) {
        downL[0][c].insert(a[i][1]);
      } else {
        downL[1][r].insert(a[i][1]);
      }
      const int dd = a[i][1] + (a[i][0] - 1);
      if (dd <= n) {
        downR[0][dd].insert(a[i][1]);
      } else {
        downR[1][dd-n].insert(a[i][1]);
      }
    }

    vector<int> ans(9, 0);
    rep (i,m) {
      int w = 0;
      const int r = a[i][0], c = a[i][1], dd = a[i][0] + (a[i][1] - 1);
      if (x_axis[c].upper_bound(r) != x_axis[c].end()) w++;
      if (x_axis[c].lower_bound(r) != x_axis[c].begin()) w++; // ?

      if (y_axis[r].upper_bound(c) != y_axis[r].end()) w++;
      if (y_axis[r].lower_bound(c) != y_axis[r].begin()) w++; // ?

      const int rr = r - min(r,c), cc = c - min(r,c);
      if (c > r) {
        if (downL[0][cc].upper_bound(c) != downL[0][cc].end()) w++;
        if (downL[0][cc].lower_bound(c) != downL[0][cc].begin()) w++;
      } else {
        if (downL[1][rr].upper_bound(c) != downL[1][rr].end()) w++;
        if (downL[1][rr].lower_bound(c) != downL[1][rr].begin()) w++;
      }

      if (dd <= n) {
        if (downR[0][dd].upper_bound(c) != downR[0][dd].end()) w++;
        if (downR[0][dd].lower_bound(c) != downR[0][dd].begin()) w++;
      } else {
        if (downR[1][dd-n].upper_bound(c) != downR[1][dd-n].end()) w++;
        if (downR[1][dd-n].lower_bound(c) != downR[1][dd-n].begin()) w++;
      }
      ans[w]++;
      //printf("(%d,%d) = %d\n", c, r, w);
    }
    rep (i,9) cout << ans[i] << " "; cout << endl;
  }
  return 0;
}

F. Present to Mom

問題は読めたけど、全然わからない。

rate

1580(-78)