Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1384-8420724f
この記事にトラックバックする(FC2ブログユーザー)

SRM473 DIV1 MEDIUM - RightTriangle (この記事を編集する[管理者用])

Source

TopCoder SRM473 DIV1 MEDIUM (500pt)
Problem Statement
SRM473 DIV1 自分の参加記録

問題概要

円周上に等間隔に1000000個以下の点がある.
100000個以下の点を赤く塗る.
赤く塗られた点だけからなる直角三角形の数を求める問題.
赤く塗る点の集合は,逐次,乱数で生成して,すでに塗られている点が指定されたら,時計回りにまだ塗られていない直近の点を塗る.(問題文参照)

解法

直角三角形になる条件は,一辺が直径になってる場合.
よって,円周上の点の数が奇数なら即座に0.
そうでなければ,直径になる点の組の数 * 残りの点の選び方を返せば良い.
それより,問題は乱数を作るところで,愚直にやるとO(n^2)になる.
次の空いてる場所を記憶しておいて,逐次更新した.
他には,既に塗られている点でも先に動かさず,その場所に置かれた点の数を覚えておいて,後でなぞって,ならしていく,という方法など.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

ll in[2000000], next[2000000];

int puss(int k,int len){
  if(in[k]==0){
    in[k]=1;
    next[k]=(k+1)%len;
    return next[k];
  }

  next[k] = puss(next[k],len);
}

class RightTriangle {
public:
long long triangleCount(int len, int n, int a, int b, int c) {
  ll i,j,k;
  ll st, ed;
  ll res = 0;

  if(len%2) return 0;

  rep(i,len) in[i]=0;
  rep(i,len) next[i]=i;

  rep(i,n){
    k = (((a*i)%len)*i)%len;
    k = (k + b*i)%len;
    k = (k + c)%len;

    puss(k,len);
  }

  rep(i,len/2) if(in[i] && in[i+len/2]){
    res += n-2;
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1384-8420724f
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。