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

naoya_t@hatenablog

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

2014 TopCoder Open Algorithm Round 1C(無事通過しました)

TopCoder Programming Contest

今度こそ通過
ooo +0/-0 1352.95pt 80th 1320→1432

レーティングも少し取り戻せました。
Round2でお会いしましょう!
(Round2はチャンス3回:(A)5/18 (B)6/8 (C)7/6 それぞれ日本時間の日曜1am*

Easy (250) Unique

  • サーバに接続できなかった数分の間に沢山の人が248点台とかで通してたので、これは超早解きなのかと思って落ち着いて開いたのが良かった。
  • AC (248.50pt = 2'12'')
#include <vector>
#include <set>
#include <string>
using namespace std;

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

class Unique {
 public:
  string removeDuplicates(string S) {
    vector<char> vc;
    set<char> s;
    int n=sz(S);
    rep(i,n){
      char c=S[i];
      if(found(s,c))continue;
      vc.pb(c);
      s.insert(c);
    }
    return string(all(vc));
  }
};

Medium (450) FizzBuzzTurbo

  • for (ll x=A; x<=B; ++x) ... とかしなければ大丈夫なのでは?
    • と思ったけど両端の15で割った余りがどうこうとか考えだすと境界でうにーってなるのか?
  • AC (436.49pt = 5'1'')
#include <vector>
using namespace std;

typedef long long ll;

class FizzBuzzTurbo {
  ll fizz(ll x){
    return (x/3) - (x/15);
  }
  ll buzz(ll x){
    return (x/5) - (x/15);
  }
  ll fb(ll x){
    return x/15;
  }
 public:
  vector<long long> counts(long long A, long long B) {
    vector<long long> vl(3);
    vl[0] = fizz(B) - fizz(A-1);
    vl[1] = buzz(B) - buzz(A-1);
    vl[2] = fb(B) - fb(A-1);
    return vl;
  }
};

Hard (950) RedPaint


「長さ(L)で、左端からのi番目(i=0..L-1)のセルにいる確率」みたいなのをDPで。

  • 最初は「長さ1、左端+0」確率1.0
  • 次は「長さ2, 左端+0」と「長さ2、左端+1」にそれぞれ確率0.5
    • これは左右対称なので、「長さ2、左端+0」(確率1.0)にまとめてしまっている
  • 次は「長さ3、左端+0」に0.5、「長さ2、左端+1」に0.5
    • てな具合に、長さが+1したりしなかったりするのを考慮しながら。
    • 両端にいる場合は長さが+1する可能性があるが、両端以外では長さ固定で位置だけ移動。
  • N=500でメモリも足りるし時間も間に合う(500msecちょい)のを確認してsubmit
  • AC (667.96pt = 20'21'')
#include <vector>
using namespace std;

typedef long long ll;
typedef long double dd;

#define rep(var,n)  for(int var=0;var<(n);++var)

class RedPaint {
 public:
  double expectedCells(int N) {
    // 501 x 501
    int W = N+1;
    vector<vector<vector<dd> > > dp(2,
                                    vector<vector<dd> >(W+1,
                                                        vector<dd>(W+1,
                                                                   0)));
    dp[0][1][0] = 1.0;
    rep(t,N){
      int i0=t%2, i1=1-i0;
      rep(i,W+1) rep(j,W+1) dp[i1][i][j] = 0; // length, offset
      for(int l=1; l<=1+t; ++l){
        for(int o=0; o<l; ++o) {
          dd h = dp[i0][l][o]/2;
          if (l==1) {
            dp[i1][2][0] = h*2;
          } else if (o==0) {
            dp[i1][l+1][0] += h;
            dp[i1][l][1] += h;
          } else if (o==l-1) {
            dp[i1][l][o-1] += h;
            dp[i1][l+1][o+1] += h;
          } else {
            dp[i1][l][o-1] += h;
            dp[i1][l][o+1] += h;
          }
        }
      }
    }

    dd total = 0;
    int ix=N%2;
    rep(i,W+1) rep(j,W+1){
      total += i * dp[ix][i][j];
    }
    return (double)total;
  }
};