Hatena::Grouptopcoder

hotokuの日記@topcoder部 このページをアンテナに追加 RSSフィード

2013-01-30

Facebook Hacker Cup 2013 Qualification Round

21:26

20点問題をつまらないヘマで落とす。泣。

Balanced Smileys

先頭から1文字づつ読んでいく。"(" / ")"に出会ったら、"深さ"が1つ深く / 浅くなる。但し、":"の次であれば、顔文字の一部とみなして、"深さ"を深く / 浅くしなくても良い。というルールで、最後の文字を読んだ時に"深さ"が0になるような読み方はあるかどうか。

#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <numeric>
#include <functional>

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


int T;
const int n = 200;
bool mat[n][n];
string s;

void debug(){
  for(size_t i = 0; i < n; ++i){
    copy(mat[i], mat[i]+n, ostream_iterator<bool>(cout, " "));
    cout << endl;
  }
  cout << "==========" << endl;
}

void update(int pos, int d){
  for(int i = 0; i < n; ++i){
    // cout << pos+1 << "," << i+d << endl;
    if(mat[pos][i] && i+d >= 0) mat[pos+1][i+d] = true;
  }
}

bool check(char s){
  return
    (s >= 'a' && s <= 'z') ||
    s == ' ' ||
    s == ':' ||
    s == '(' ||
    s == ')';
}

void doit(int num){
  getline(cin, s);
  for(size_t i = 0; i < n; ++i){
    fill(mat[i], mat[i]+n, false);
  }
  mat[0][0]=true;
  bool after_colon = false;
  for(size_t i = 0; i < s.size(); ++i){
    if(!check(s[i])){
      cout << "Case #" << (num+1) << ": NO" << endl;
      return;
    }
    if(s[i]=='('){
      update(i, 1);
      if(after_colon)update(i, 0);
    }
    else if(s[i]==')'){
      update(i, -1);
      if(after_colon)update(i, 0);
    }
    else{
      update(i, 0);
    }
    after_colon = s[i] == ':';
  }
  // debug();
  cout << "Case #" << (num+1) << ": ";
  if(mat[s.size()][0]) cout << "YES";
  else cout << "NO";
  cout << endl;
}

int main(int argc, char *argv[]){
  cin >> T;
  string temp;
  getline(cin, temp);
  for(size_t i = 0; i < T; ++i){
    doit(i);
  }
  return 0;
}


Find the Min

馬鹿正直にシミュレーションしてしまうと、時間が足りなくなる。制限の中で、kだけ小さいので、こいつで何とかなるんでないかと考える。で、やはり、よく考えると、2k までシミュレーションしてしまえば、残りは周期kの列になる。

#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <numeric>
#include <functional>



using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int T;
ll k, n, a, b, c, r;
int used[100010];
ll m[200010];

void debug(){
  copy(m, m+2*k+1, ostream_iterator<ll>(cerr, " "));
}

ll getmin(){
  ll i = 0;
  while(used[i]){
    i++;
  }
  return i;
}
void doit(int num){
  cin >> n >> k >> a >> b >> c >> r;
  fill(used, used+k+1, 0);
  fill(m, m+(2*k+1), -1);
  m[0] = a; if(a<=k)used[a]++;
  for(size_t i = 1; i < k; ++i){
    m[i] = (b*m[i-1]+c) % r;
    if(m[i]<=k){
      used[m[i]]++;
    }
  }
  m[k] = getmin();
  used[m[k]]++;
  for(size_t i = k+1; i <= 2*k; ++i){
    if(m[i-k-1]<=k) used[m[i-k-1]]--;
    m[i] = getmin();
    used[m[i]]++;
  }
  //debug();
  ll ret;
  if(n-1<=2*k){
    ret = m[n-1];
  }
  else{
    ret = m[k+(n-1-k)%(k+1)];
  }
  cout << "Case #" << (num+1) << ": " << ret << endl;
}

int main(int argc, char *argv[]){
  cin >> T; char c;
  while((c=getchar())!='\n'){}
  ungetc(c, stdin);
  for(size_t i = 0; i < T; ++i){
    doit(i);
  }
  return 0;
}

2013-01-23

NinjaTurtles

| 17:41

本番で落としたので、反省の為に晒しておく。

Shut the shut up and write some code. というのは本当にそうだなと。ちょっとサボってただけのつもりだったのに…。久し振りに参加してグングン落ちるレーティングを見て思う。

閑話休題。a-1 < floor(a) <= aを利用して、Nの取りうる範囲を求めてその間をしらみ潰す(下のコードは念の為に広めに取っている)。他の人のを見たらそんな面倒な事はせず[0, 4P]の範囲をしらみ潰している人も居た。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class NinjaTurtles{
public:
  int countOpponents(int P, int K){
    for(int N = 3*K*(P-10)/(9+K); N <= 3*K*(P+10)/(9+K); ++N){
      if(3*(N/K) + N/3==P) return N;
    }
    return -1;
  }
};

2012-10-21

SRM 558 div2 easy Stamp

| 11:01

問題を見た時に、きっとDPで解くんだろうなと思いつつ、結局提出出来なかった。苦手な感じの問題なので、メモを残す。→問題

方針

スタンプを左から押していくDPを考える。DP用の配列として、dp[i][j]を用意。dp[i][j]には、「色iのスタンプをjに押した場合の最小コスト」を保存。ここで、「色iのスタンプをjに押す」とは、色iのスタンプを右端がj番目のマス目に来るように押す事と理解する。

スタンプの長さをLとすると、色iのスタンプをjに押すことが出来るのは、

  • j-L番目に別の色のスタンプを押している場合
  • j-L番目に同じ色のスタンプを押している場合
  • j-L+1番目に同じ色のスタンプを押している場合
  • (途中省略)
  • j-1番目に同じ色のスタンプを押している場合

のどれかなので、dp[i][j]にはこれらの中の最小コスト+pushCostを入れれば良い。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

int d[100];
int n;
int dp[3][100];
int cost, push;


class Stamp{
public:
  bool check(int c, int pos, int L);
  int do_dp(int L);
  int getMinimumCost(string desiredColor, int stampCost, int pushCost);



};

void debug(){
  for(int i = 0; i < 3; ++i){
    copy(dp[i], dp[i]+n, ostream_iterator<int>(cout, "\t")); cout << endl;
  }
  cout << endl;
}

bool Stamp::check(int c, int pos, int L){
  for(int i = 0; i < L; ++i){
    if(d[pos-i]==c || d[pos-i]==-1) continue;
    else return false;
  }
  return true;
}
int Stamp::do_dp(int L){
  for(int i = 0; i < 3; ++i){
    fill(dp[i], dp[i]+n, 1<<30);
    if(check(i, L-1, L)) dp[i][L-1]=push;
  }
  for(int i = L; i < n; ++i){
    for(int j = 0; j < 3; ++j){
      if(!check(j, i, L)) continue;
      for(int k = 0; k < 3; ++k){
	dp[j][i] = min(dp[k][i-L]+push, dp[j][i]);
      }
      for(int k = 1; k < L; ++k){
	dp[j][i] = min(dp[j][i-k]+push, dp[j][i]);
      }
      // cout << L << endl;
      // debug();
    }
  }
  return min(dp[0][n-1], min(dp[1][n-1], dp[2][n-1]));
}
int Stamp::getMinimumCost(string desiredColor, int stampCost, int pushCost){
  n = desiredColor.size();
  cost = stampCost;
  push = pushCost;
  for(int i = 0; i < n; ++i){
    if(desiredColor[i]=='R')d[i]=0;
    if(desiredColor[i]=='G')d[i]=1;
    if(desiredColor[i]=='B')d[i]=2;
    if(desiredColor[i]=='*')d[i]=-1;
  }
  int ret=INT_MAX;
  for(int i = 1; i<=n; ++i){
    int p = do_dp(i);
    if(p>0)ret=min(stampCost*i+p, ret);
  }
  return ret;
}

2012-10-13

codeforces 144 div 2

| 16:04

A

P_{P_i}=iという条件をよく考える。P_i=jとするとP_{P_i}=P_j=i。従って、P_i=P_{P_j}=j

上の考察とP_i\neq iから、nが奇数なら条件を満たす順列は無い。nが偶数なら、適当なペアを作ってお互いに移り合うようにすれば良い

/*! if g++ -g a.cpp -o a.out; then ./a.out < a.test; fi
 */

#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <numeric>
#include <functional>



using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int n;

int main(int argc, char *argv[]){
  scanf("%d", &n);
  if(n%2==1){
    printf("%d\n", -1);
  }
  else{
    for(size_t i = 0; i < n/2; ++i){
      printf("%d %d", 2*i+2, 2*i+1);
      if(i==n/2-1) printf("\n");
      else printf(" ");
    }
  }
  return 0;
}

B

s(x)>=0は自明。適当な単調関数gで、g(x)>=s(s)なるものを探してくる。すると、方程式の解はx(x+g(x))=nの解とx^2=nの解の間にある。

/*! if g++ -g b.cpp -o b.out; then ./b.out < b.test; fi
 */

#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <numeric>
#include <functional>



using namespace std;
typedef unsigned long long ull;
typedef long long ll;

ull n;


double mysqrt(ull x){
  if(x==1) return 1;
  else return sqrt(x);
}
double mylog(ull x){
  return log(x)/log(10);
}
double f(ull x){
  return x*(x+10*mylog(x));
}
ull search(ull l, ull r){
  if(r-l<=1) return l;
  ull c = (l+r)/2;
  if(f(c)>=n) return search(l, c);
  else return search(c, r);
}
int s(ull x){
  if(x==0) return 0;
  return x%10 + s(x/10);
}
int main(int argc, char *argv[]){
  cin >> n;
  for(ull i = search(1,n); i <= mysqrt(n); i++){
    if(i*(i+s(i))==n){
      cout << i << endl;
      return 0;
    }
  }
  printf("-1\n");
  return 0;
}



SRM 557

| 15:54

midに時間掛かり過ぎ。殆ど、時間ギリまで使ってしまった。アルゴリズムは単純なので、こういうのをスムーズに提出出来るようにならないとなかなか上に行けない。


easy

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class GreatFairyWar{
public:
  int minHP(vector <int> dps, vector <int> hp){
    int ret=0;
    size_t n = dps.size();
    for(size_t i = 0; i < n; ++i){
      for(size_t j = i; j < n; ++j){
	ret+=dps[j]*hp[i];
      }
    }
    return ret;
  }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


mid IncubatorEasy

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

size_t n;
bool magical[100], proc[100], visit[100];
vector<string> graph;


class IncubatorEasy{
public:
  void dfs(int pos, bool is_proc);
  int count_valid(int flag);
  int maxMagicalGirls(vector <string> love);
};

void IncubatorEasy::dfs(int pos, bool is_proc){
  if(is_proc){
    proc[pos]=true;
  }
  if(visit[pos]) return;
  visit[pos]=true;
  for(size_t i = 0; i < n; ++i){
    if(graph[pos][i]=='Y'){
      dfs(i, true);
    }
  }
}
int IncubatorEasy::count_valid(int flag){
  fill(proc, proc+n, false);
  fill(visit, visit+n, false);
  for(size_t i = 0; i < n; ++i){
    magical[i] = flag & 1<<i;
    if(magical[i]) dfs(i, false);
  }
  int ret=0;
  for(size_t i = 0; i < n; ++i){
    if(magical[i] && !proc[i]){
      ret++;
    }
  }
  // copy(magical, magical+n, ostream_iterator<bool>(cout, ","));
  // cout << ":" << ret << endl;
  return ret;
}
int IncubatorEasy::maxMagicalGirls(vector <string> love){
  n = love.size();
  graph = love;
  int flag=0;
  int ret=0;
  while(flag < 1<<n){
    ret=max(ret, count_valid(flag++));
  }
  return ret;
}