Hatena::Grouptopcoder

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

 | 

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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/hotoku/20121013
リンク元
 |