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

2012-08-07

round 132 div2 a bicycle chain

| 22:59

やるだけ。

/*! 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>


using namespace std;



int a[100], b[100];
int na, nb;
int max_val;
int c;

int main(int argc, char *argv[]){
  scanf("%d", &na);
  for(size_t i = 0; i < na; ++i){
    scanf("%d", a+i);
  }
  scanf("%d", &nb);
  for(size_t i = 0; i < nb; ++i){
    scanf("%d", b+i);
  }
  max_val = 0;
  c = 0;
  int temp;
  for(size_t i = 0; i < na; ++i){
    for(size_t j = 0; j < nb; ++j){
      if(b[j]%a[i]==0){
	temp=b[j]/a[i];
	if(temp>max_val){
	  max_val=temp;
	  c=1;
	}
	else if(temp==max_val){
	  c++;
	}	
      }
    }
  }
  printf("%d\n", c);  
  return 0;
}


round 132 div2 b olympic medal

| 23:01

やるだけ。

/*! 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>


using namespace std;

int n, m, k;
double x[5010], y[5010], z[5010];
double a, b;

int main(int argc, char *argv[]){
  scanf("%d", &n);
  for(size_t i = 0; i < n; ++i){
    scanf("%lf", x+i);
  }
  scanf("%d", &m);
  for(size_t i = 0; i < m; ++i){
    scanf("%lf", y+i);
  }
  scanf("%d", &k);
  for(size_t i = 0; i < k; ++i){
    scanf("%lf", z+i);
  }
  scanf("%lf%lf", &a, &b);
  double r1 = *max_element(x, x+n);
  double p1 = *max_element(y, y+m);
  double p2 = *min_element(z, z+k);
  cerr << r1 << "," << p1 << "," << p2 << endl;
  cout.precision(15);
  double temp = ((p2/p1)*(a/b)+1) * 1/r1/r1;
  cout << 1/(sqrt(temp)) << endl;

  return 0;
}


結局、やるだけ問題を解くだけに終わってしまった。精進します。。。

2012-07-13

round 129 div 2 a Little Elephant and Rozdil

| 18:12

やるだけ。

/*! 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>


using namespace std;
typedef long long ll;
typedef pair<ll, int> p;

int main(int argc, char *argv[]){
  int n;
  scanf("%d", &n);
  if(n==1){
    printf("1\n");
    return 0;
  }

  vector<p> v(n);
  for(size_t i = 0; i < n; ++i){
    ll buf;
    scanf("%I64d", &buf);
    v[i] = make_pair(buf, i+1);
  }
  sort(v.begin(), v.end());
  if(v[0].first == v[1].first) printf("Still Rozdil\n");
  else printf("%d\n", v[0].second);
  return 0;
}

round 129 div2 b Little Elephant and Sorting

| 18:15

  • a[i-1] > a[i]となっている部分を「へこみ」と呼ぶ。
  • i番目の要素がへこみである時(a[i-1] > a[i]の時)、このへこみを解消するためにa[i-1]-a[i]回の操作が必要。
    • 複数箇所のへこみを同時に解消することは出来ないので、結局すべてのへこみについて上の回数を足し上げたものが答え。
/*! 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>


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

ll buf[100010];

int main(int argc, char *argv[]){
  int n;
  scanf("%d", &n);
  ull ret=0;
  cin >> buf[0];
  for(size_t i = 1; i < n; ++i){
    cin >> buf[i];
    ret += max(buf[i-1]-buf[i], (ll)0);
  }
  cout << ret << endl;
  return 0;
}

round 129 div 2 c Little Elephant and Interval

| 18:46

本番では提出出来なかった。。。

  • 「f(n):n -> n以下で最上位桁と最下位桁が一致する整数の数」という関数を用意して、f(l)-f(r-1)を計算するのがスマートなやり方っぽい。

なるほど。。。

2012-07-04

round 128 div2

| 19:37

Cは、何か、条件反射的にナップサック問題?とか思ってしまって、大きい方から詰め込むだけという単純な事に気づかず。勿体無いことをした。

A Two problems

  • 全探索
  • 最初、1問しか解かない場合を考慮せず、pretestで落とされる。
    • こういう「見落としやすいパターン」って、何か明示的に法則として言語化出来ればなぁとか妄想。
/*! 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>


using namespace std;


int main(int argc, char *argv[]){
  int x, t, a, b, da, db;
  scanf("%d%d%d%d%d%d", &x, &t, &a, &b, &da, &db);
  if(x==0) {printf("YES\n"); return 0;}
  for(int i = 0; i < t; i++){
    if(a-i*da==x || b-i*db==x){
      printf("YES\n");
      return 0;
    }
    for(int j = 0; j < t; j++){
      if(a-i*da+b-j*db==x){
	printf("YES\n");
	return 0;
      }
    }
  }
  printf("NO\n");
  return 0;
}

B Game on paper

  • 新しくマスを塗る度に、3x3の正方形が出来たかをチェック。
  • 何だか、焦ってしまって偉いデバッグに手間取った記憶。
  • 焦らないためにも、アルゴリズム・コードパターンの引き出しを多くしておくことが大事と思う。

??? ちょっとチェックする範囲が広すぎる気がががががががが。

/*! 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>


using namespace std;

bool c[2000][2000];
int n, m;
int dx[9] = {0,1,2,0,1,2,0,1,2};
int dy[9] = {0,0,0,1,1,1,2,2,2};
int dx2[25] = {-2,-1,0,1,2,
	       -2,-1,0,1,2,
	       -2,-1,0,1,2,
	       -2,-1,0,1,2,
	       -2,-1,0,1,2};
int dy2[25] = {-2,-2,-2,-2,-2,
	       -1,-1,-1,-1,-1,
	       0,0,0,0,0,
	       1,1,1,1,1,
	       2,2,2,2,2};

bool check(int x, int y){
  //cout << x << "," << y << endl;
  if((x<0 || x+2>=n || y<0 || y+2>=n)){
      return false;
    }         
    bool flag=true;
  for(size_t i = 0; i < 9; ++i){
    flag = flag && c[x+dx[i]][y+dy[i]];
  }
    return flag;
}

int main(int argc, char *argv[]){
  scanf("%d%d", &n, &m);
  for(size_t i = 0; i < n; ++i){
    fill(c[i], c[i]+n, false);
  }

  for(size_t i = 0; i < m; ++i){
    //cout << i+1 << endl;
    int x, y;
    scanf("%d%d", &x, &y);
    x-=1; y-=1;
    //cout << x << "," << y << endl;
    c[x][y]=true;
    for(size_t j = 0; j < 25; ++j){
      if(check(x+dx2[j], y+dy2[j])){
	printf("%d\n", (int)i+1);
	return 0;
      }
    }
  }

  printf("-1\n");
  return 0;
}


D Hit Ball

  • やるだけ

/*! if g++ -g d.cpp -o d.out; then ./d.out < d.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>


using namespace std;


int a, b, m;
int vx, vy, vz;


double getpos(double v, double init, int limit){
  double pos = m * v / abs(vy) + init;
  double pos_i_buf, pos_f;
  pos_f = modf(pos, &pos_i_buf);
  int pos_i = (int)pos_i_buf;

  //cout << pos << "," << pos_i << "," << pos_f << endl;

  double ret;
  if(pos < 0){
    int nref = abs(pos_i) / limit + 1;
    ret = abs(pos_i)%limit + abs(pos_f);
    if(nref%2==0) ret = limit - ret;
  }
  else if(pos > limit){
    int nref = abs(pos_i) / limit;
    ret = abs(pos_i)%limit + abs(pos_f);
    if(nref%2==1) ret = limit - ret;
  }
  else{
    ret = pos;
  }

  return ret;
}

int main(int argc, char *argv[]){
  scanf("%d%d%d%d%d%d", &a, &b, &m, &vx, &vy, &vz);

  cout.precision(10);
  cout << getpos(vx, (double)a/2, a) << " ";
  cout << getpos(vz, 0, b) << endl;

  return 0;
}

2012-06-30

round 127 A

| 12:02

Aだけしか出来ず。無念。

方針

brute force. これだけ書くのに30分も掛けてしまった。その時点で負けた感じがする。

他の人の解答を見ると、実は、最大の文字をその出現回数分出せば良かったぽい。むぅ。確かに、回分という条件が利いてそういうことになるんだね。

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



#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>
#include <numeric>


using namespace std;


string sub(string x, long n){
  stringstream s;
  for(int i = 0; i < x.size(); i++){
    int k = x.size()-i-1;
    if((1<<k) & n){
      s << x[k];
    }
  }
  return s.str();
}

bool check(string s){
  int n = s.size();
  for(size_t i = 0; i < n/2; ++i){
    if(s[i]!=s[s.size()-i-1])return false;
  }
  return true;
}


int main(int argc, char *argv[]){
  string s;
  cin >> s;
  long N = (1<<s.size());
  long i=0;
  vector<string> v;
  while(++i<N){
    string temp = sub(s, i);
    if(check(temp)) v.push_back(temp);
  }
  sort(v.begin(), v.end());
  cout << v.back() << endl;
  return 0;
}

NokwandaNokwanda2012/11/15 06:21Stay ifnomrative, San Diego, yeah boy!

wqzqvvwqzqvv2012/11/16 05:30F4XGPb <a href="http://sndjxmfszsii.com/">sndjxmfszsii</a>

zirfzskzirfzsk2012/11/17 04:58zSftqc , [url=http://zeqvfnsebnus.com/]zeqvfnsebnus[/url], [link=http://llcmxssjmgun.com/]llcmxssjmgun[/link], http://fxsoqrflwadb.com/

galaxkzuegalaxkzue2012/11/17 12:074HRJQB <a href="http://cbtilzygdkwe.com/">cbtilzygdkwe</a>

alngnexalngnex2012/11/17 21:35VvsB3q , [url=http://dqdpnehdoukj.com/]dqdpnehdoukj[/url], [link=http://zhitnubghxwi.com/]zhitnubghxwi[/link], http://rfbmvqpijfig.com/