Hatena::Grouptopcoder

blu_rayの日記

2012-02-07

Codeforces Round #105 Div2

| 00:48

本番は出てないです。主に卒論とかあったりして。

A. Insomnia cure

1からdの数値の中で{k,l,m,n}の倍数数えるだけ。

#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++)

int main() {
  vector<int> in(4,0);
  int D;
  while (cin >> in[0]) {
    rep(i,3) cin >> in[i+1];
    cin >> D;
    vector<int> a(D+1, 0);
    rep(i,4) {
      for (int j = in[i]; j <= D; j+=in[i])
        a[j] = 1;
    }
    printf("%d\n", count(a.begin(), a.end(), 1));
  }
  return 0;
}

B. Escape

Vp * x + [お姫様の位置] = Vd * x

を計算する。

#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++)

double Vp, Vd, T, F, C;

int main() {
  while (cin >> Vp) {
    cin >> Vd >> T >> F >> C;
    if (Vp >= Vd) { puts("0"); continue; } // #
    double lb = T * Vp;
    int ans = 0;
    while (1) {
      double x = lb / (Vd - Vp);
      lb += Vp * x;
      if (lb >= C) break;
      lb += Vp * x + Vp * F;
      ++ans;
    }
    printf("%d\n", ans);
  }
  return 0;
}

C. Terse princess

とりあえず出力される数列を1で初期化しといて、0番目の要素を先頭として、

1番目の要素からA個だけ t[i] = t[i-1] + 1

Aの処理が終わった後に、B個だけ t[i] = accumulate(t, t + A+i, 0)

で大丈夫そうですが、

1 2 3 4 5 ...

のように1番目の要素から t[i] = t[i-1] + 1 をやるとAの要素じゃなくてBの要素として考慮されてしまうので、先にBの処理を行ってからAの処理を行うと必要なNが少なくて済む。

#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++)

int N, A, B;

template <class Iterator>
Iterator get_advnaced_itr(Iterator _itr, int n) {
  Iterator itr(_itr);
  advance(itr, n);
  return itr;
}

void print(const vector<int>& vi) {
  rep(i,vi.size()) {
    if (i) putchar(' '); printf("%d",vi[i]);
  }
  puts("");
}

int main() {
  while (cin >> N >> A >> B) {
    vector<int> a(N, 1);
    if (N == 1 || (A == 0 && B == 0)) { print(a); continue; }
    if (2 + A > N) { puts("-1"); continue; }

    for (int i = 0; i < B; ++i) {
      a[1+i] += accumulate(a.begin(), get_advnaced_itr(a.begin(), i+1), 0);
    }

    int endB = 1+B;
    if (endB == 1) ++endB;
    if (endB + A > N) { puts("-1"); continue; }
    for (int i = 0; i < A; ++i) {
      a[endB+i] = a[endB+i-1]+1;
    }
    print(a);
  }
  return 0;
}

D. Bag of mice

なんとなくそれっぽい再帰を書いて、メモ化したら出来た。

掛け合わせるdouble変数がnanとかinfになったりしてつまった。

#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++)

int W, B;
double dp[1002][1002];

double rec(int w, int b) {
  double dw = w, db = b;
  // bounds checking
  if (b == 0) { return w > 0 ? 1 : 0 ; }
  if (w <= 0 || b < 0) return 0;
  if (dp[w][b] >= 0) return dp[w][b];

  double &d = dp[w][b];
  
  // princess chose w
  double pcw = dw/(dw+db);
  // princess chose b
  double pcb = db/(dw+db);
  // dragon chose b
  double dcb = (db-1)/(dw+db-1);
  // espace w, b
  double sw = (dw)/(dw+db-2), sb = (db-2)/(dw+db-2);
  // calc
  d = pcw;
  if (w >= 1 && b >= 2)
    d += pcb * dcb * sw * rec(w-1, b-2);
  if (w > 0 && b >= 3)
    d += pcb * dcb * sb * rec(w, b-3);
  // debug
  if (isnan(dp[w][b])) {
    printf("%d:%d %lf %lf %lf %lf %lf\n", w, b, pcw, pcb, dcb, sw, sb);
    printf("%lf %lf\n", dp[w-1][b-2], dp[w][b-3]);
    assert(false);
  }
  return d;
}

int main() {
  while (cin >> W >> B) {
    if (W == 0) { puts("0"); continue; }
    memset(dp, -1, sizeof dp);
    printf("%.9lf\n", rec(W, B));
  }
  return 0;
}

E. Porcelain

適当に状態を考えると

[i][l][r][m] => [100][100][100][10000] := 叫んだ回数がm回で、i番目の本棚の陶磁器が左からl個壊れて右からr個壊れている状態

のような、やばい状態数が考えられますが、

1番目の棚の左端が壊れる事と2番目の棚の右端が壊れる事のような、異なる棚での陶磁器が壊れる現象はどちらが先に起きても問題ないので、(陶磁器の壊れる順番が大事なのは、それぞれの棚における端から壊れるということだけ)

棚同士の状態は分けて考えることが出来て、i番目の本棚でm回叫んだ時の破壊できる陶磁器の価値の和の最大値を求めて、それを利用して求めつづけるのをやったら通った。

一番大きなループが最大ケースで、100 * 100 * 10000 くらいあってTLEすると思ったけど、なんか実行時間330msで通った。

#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 kMaxM = 10002, kInf = 1 << 30;
int N, M;
int ns[102], a[102][102];
int dp[2][10002];

int main() {
  while (cin >> N >> M) {
    rep(i,N) {
      cin >> ns[i];
      rep(j,ns[i]) cin >> a[i][j];
    }
    rep(i,2) fill(dp[i], dp[i] + kMaxM, -kInf);
    dp[0][0] = 0;
    int *prv = dp[0], *nxt = dp[1];
    rep(i,N) {
      vector<int> dp2(kMaxM, 0);
      // calc
      for (int l = 0; l <= ns[i]; ++l) {
        for (int r = 0; l + r <= ns[i]; ++r) {
          int um = l + r;
          int v = accumulate(a[i],a[i]+l,0) +
                  accumulate(a[i]+ns[i]-r,a[i]+ns[i],0);
          dp2[um] = max(dp2[um], v);
        }
      }
      // update
      for (int j = 1; j <= ns[i]; ++j) {
        const int add = dp2[j];
        for (int k = 0; k <= M; ++k) {
          if (k-j >= 0)
            nxt[k] = max(nxt[k], max(prv[k], prv[k-j] + add));
          else
            nxt[k] = max(nxt[k], prv[k]);
        }
      }
      swap(prv, nxt);
    }
    printf("%d\n", prv[M]);
  }
  return 0;
}

2012-01-06

Codeforces Round #100

| 04:12

x-x---

0完。眠いときはやめたほうがいい。

A. New Year Table

#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 double PI =  3.141592653589793;
const double Eps = 1e-8;
int n, R, r;

void solve() {
  if (n == 1) {
    if (R >= r) { puts("YES"); return; }
    puts("NO"); return;
  }

  if (R/2.0 < r) { puts("NO"); return; }
  
  double tan_ = r / sqrt((double)R*R - 2.0*R*r);
  double need = atan(tan_) * 180.0 / PI * 2 * n;
  if (360.0 + Eps > need) { puts("YES"); return; }
  puts("NO");
}

皿の直径がテーブルの半径より大きい時は多分複数枚置けないと思うので"NO"にして、あとは一枚あたりに必要な角度だしてn枚分数えたときに360°に収まるか愚直にみる。

B. New Year Cards

#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++)

int N, pl[302][302];

void solve() {
  vector<int> ret(N+2, -1);
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      int cur = -1;
      rep(k,N) {
        if (pl[0][k] <= i && j != pl[0][k]) { cur = pl[0][k]; break; }
      }
      if (cur == -1) continue;
      if (ret[j] == -1) { ret[j] = cur; continue; }
      if (find(pl[j], pl[j]+N, cur) < find(pl[j], pl[j]+N, ret[j])) {
        ret[j] = cur;
      }
    }
  }
  rep(i,N) { if(i) putchar(' '); printf("%d", ret[i+1]); } puts("");
}

Aと比べて問題文長すぎ。

年賀メールを受信する毎に手札が増えていって、相手毎に送信すべき年賀メールを選択して、優先度が高い場合は更新するようにする。findの実装よく知らないけど多分要素数に比例して、結局全体でO(N^3)?

C. New Year Snowmen

#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;

int N, r[100002];

void solve() {
  map<int,int> m;
  priority_queue<P> q;

  rep(i,N) { if (m.count(r[i])) ++m[r[i]]; else m.insert(make_pair(r[i],1)); }
  foreach(m,i) q.push(P(i->second, i->first));

  vector<int> v;
  vector<vector<int> > ret;
  vector<P> temp;
  while(!q.empty()) {
    P p = q.top(); q.pop();
    v.push_back(p.second);
    --p.first;
    temp.push_back(p);
    if(v.size() == 3) {
      sort(v.begin(), v.end(), greater<int>());
      ret.push_back(v);
      rep(i,3) if(temp[i].first > 0) q.push(temp[i]);
      temp.clear();
      v.clear();
    }
  }
  
  printf("%d\n", ret.size());
  rep(i,ret.size()) {
    rep(j,3) {
      if(j) putchar(' '); printf("%d",ret[i][j]);
    }
    puts("");
  }
}

priority queue.本番中はvector<P>とか使ってTLEた。

D. New Year Contest

#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 Inf = 1<<28;
int N, a[102], dp[102][800], pl[102][800];

void solve() {
  rep(i,N+1) rep(j,750) { dp[i][j] = -Inf; pl[i][j] = -Inf; }
  sort(a, a+N);
  dp[0][0] = 0;
  pl[0][0] = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 720 ; ++j) {
      dp[i+1][j] = dp[i][j];
      pl[i+1][j] = pl[i][j];
      if (j-a[i] >= 0) {
        if(dp[i+1][j] < dp[i][j-a[i]] + 1) {
          dp[i+1][j] = dp[i][j-a[i]] + 1;
          pl[i+1][j] = pl[i][j-a[i]];
          if(j > 350) pl[i+1][j] += j-350;
        }
      } 
    }
  }
  
  int ret = 0, penal = 0;
  rep(i,711) if (dp[N][i] > ret) { ret = dp[N][i], penal = pl[N][i]; }
  //if (penal >= 350) penal -= 350;
  printf("%d %d\n",ret,penal);
}

終わった後始めて読み始める。problems tagにdpがあったのでなんとなくそれっぽく書いてみたけどpenalty timeが合わない。同じくtagにsortingがあったからsortしてみたら通った。ていうかこんな変なことしなくてもsortしてやるだけにしてみても大体同じだと思って書いたら通った。

int N, a[102];

void solve() {
  sort(a, a+N);
  int ret = 0, cur = 10, penal = 0;
  rep(i,N) {
    if (cur + a[i] > 720) break;
    ++ret;
    cur += a[i];
    if (cur > 360) { penal += cur - 360; }
  }
  printf("%d %d\n", ret, penal);
}

rate

1423(-80)

2011-11-30

SRM 525 Div2

| 06:40

ox-

無理。

250. RainyRoad / Passed : 168

まんまとBFSで出してしまう。遅い。

600. DropCoins / Failed

Challenge Phase始まって1分くらいで撃墜される。TLE

全部終わった後、泣きながらPracticeRoomのwriterさんのコードを見る。

わざわざO(n^4)の解き方とO(n^6)の解き方があって丁寧さに泣ける。

O(n^6)の方を写経して、自分で最悪ケースでチャレンジしたら死んだけど、6重ループでも出来てる人がいるので、なんか工夫すればいいんですね。

O(n^4)の方は

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + g;

が脳内でイメージ出来たときにおどろいた。こういうのって思いつかないと駄目なのか。

rate

996(-75)

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)

2011-11-13

Codeforces Beta Round #93 Div2

| 00:46

ooox-

A. Wasted Time / Accpeted(00:12) / 476

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++)

int n, k, x[102], y[102];

double dist(int _ax, int _ay, int _bx, int _by) {
  double ax = _ax, ay = _ay, bx = _bx, by = _by;
  return sqrt( (ax - bx) * (ax - bx) + (ay - by) * (ay - by) );
}

int main() {
  cin >> n >> k;
  rep (i,n) {
    cin >> x[i] >> y[i];
  }
  int _x = x[0], _y = y[0];
  double times = 0;
  for (int i = 1; i < n; ++i) {
    times += dist(_x, _y, x[i], y[i]) / 50.0;
    _x = x[i], _y = y[i];
  }
  times *= k;
  printf("%.8lf\n", times);
  return 0;
}

B. Canvas Frames / Accepted(00:18) / 878

n個の数列が与えられて、ペアの数 / 2を答える問題。

nが最大100なので、下の愚直なコードでも十分通る。こっちがAじゃないか。

int main() {
  cin >> n;
  rep (i,n) cin >> a[i];

  int ans = 0;  
  for (int i = 0; i < n-1; ++i) {
    if (a[i] == -1) continue;
    for (int j = i+1; j < n; ++j) {
      if (a[i] == a[j]) {
        ans++;
        a[i] = a[j] = -1;
        break;
      }
    }
  }
  cout << ans / 2 << endl;  
  return 0;
}

C. Hot Bath / Accepted(01:50) / 690

適当に、t0に近づくようにお湯の量と水の量をちょっとずつ出してくようにして解を求めるようにしたら通った。

(t1 * y1 + t2 * y2) / (y1 + y2) = t0となる、y1, y2を求められればそこで探索を打ちきっていいんだけどめんどかったので省略。

多分、whileループが最大2*10^6くらいのはずなので、計算量的には大丈夫だと思った。

あとはコーナーケースに気をつける。

#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 double eps = 1e-8;
int t1, t2, x1, x2, t0;

double derive(int _y1, int _y2) {
  double _t1 = t1, _t2 = t2, y1 = _y1, y2 = _y2;
  double ret = (t1 * y1 + t2 * y2) / (y1 + y2);
  return ret;
}

int main() {
  while (cin >> t1 >> t2 >> x1 >> x2 >> t0) {

    
    if (t1 == t2 && t1 == t0) {
      cout << x1 << " " << x2 << endl; continue;
    }

    if (t1 >= t0) {
      cout << x1 << " " << 0 << endl; continue;
    }
    
    if (t2 == t0) {
      cout << 0 << " " << x2 << endl; continue;
    }
    
    double min_dist = double(1 << 30);

    int y1 = 0, y2 = 1;
    int ny1 = -1, ny2 = -1;

    while (true) {
      double t = derive(y1, y2);
      double dist = t - t0;
      //printf("%d, %d : %lf\n", y1, y2, t);
      if (dist >= 0 && dist < min_dist) {
        ny1 = y1, ny2 = y2;
        min_dist = dist;
      }
      if (t > t0) {
        y1++;
      } else {
        y2++;
      }
      if (y1 > x1 || y2 > x2) {
        y1 = ny1, y2 = ny2;
        break;
      }
    }
    
    int t = 1;
    for (; t * y1 <= x1 && t * y2 <= x2; ++t);
    if (t > 1) t--;
    y1 *= t;
    y2 *= t;
    
    cout << y1 << " " << y2 << endl;
  }  
  return 0;
}

D. Password / WA(TLE)

Cを解いている人の数がなかなか伸びない中、Dを解いている人の数が増えてったので出したら通ってしまったのだけど、TLE解で10^12だった。。Cが解けずにてんぱっていて見積もってなかった。

二分探索か、場所を覚えておけばいいっぽい。

rate := 1658(+73)

これってDiv1なのか...な。

rateごとのクラス名が軍人の階級的なものから変更されたけど、Expertは自分にとっちゃ畏れ多い