読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

「問。次のDiv1 Medium提出コードはWAなのに撃墜されませんでした。編集距離1でACにしてください。」(SRM536 配点:50)

TopCoder
  • Easy(250): AC<199.76>
  • Medium(500): WA<214.78→0>
  • Hard(1000): opened<0>

14/20 in the room, 513/860 in Div1
1610 -> 1568

500 はChallenge phaseまで耐えたけれどfailed system test。
編集距離1で通るような話だけれど(凡ミスではなく)考えが足りなかったせい。

Easy (250): MergesDivOne

  • ハフマン符号化みたいな解き方をしてるけれど、ソート済みだし先頭2つで取った平均が先頭以外に来ることがないのでそんな事しなくてよかった。
  • というわけで早解き勝負で無駄なことをした感
  • 一応通るけどあれだ
  • 最近あんまりやってないからスピードつけるために過去問いろいろ解くなりしたい
#include <vector>
#include <queue>
using namespace std;
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class MergersDivOne {
 public:
  double findMaximum(vector<int> revenues) {
    priority_queue<double> pq;
    tr(revenues,it) pq.push(-(double)*it);
    while (!pq.empty()) {
      double t1 = pq.top(); pq.pop();
      if (pq.empty()) return -t1;
      double t2 = pq.top(); pq.pop();
      pq.push((t1 + t2)/2);
    }
  }
};

Medium (500): RollingDiceDivOne

問。次の提出コードはWAなのに撃墜されませんでした。編集距離1でACにしてください。(配点:50点)

#include <vector>
using namespace std;
typedef long long ll;
#define all(c)  (c).begin(),(c).end()

class RollingDiceDivOne {
 public:
  long long mostLikely(vector<int> dice) {
    int N = dice.size();
    if (N == 1) return 1LL;

    sort(all(dice), greater<int>());

    ll a = 0, b = (ll)dice[0], c = b;
    for (int i=1; i<N; i++) {
      ll d = dice[i];
      c += (d - 1);
      if (d <= b) {
        b = b - d + 1;
      } else {
        ll r = d - b;
        if (r & 1) {
          b = 1;
        } else {
          b = 2;
        }
      }
      a = (c - b) / 2;
    }
    return a + N;
  }
};

ネタバレになっちゃうので以下白字で。(RSSで読んでる人の事までは知らん)

  • 上が平らで左右対象な山を畳み込んで行って、というか1ステップずつ形を変えていくイメージで
  • でもこの提出コードだと左右対称にならない場合があるよね><

Hard (1000): BinaryPolynomialDivOne

  • 残り9分。Hardもいちおう開いて題意は理解。残り9分で書けないことも理解。
  • 諦めたのでここで試合終了。