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

ichirin2501's diary

いっちりーん。

SRM443 DIV2

積ん読ではなくて積ん記事状態だった、
最強最速アルゴリズマー養成講座:あなたの論理的思考とコーディング力は3倍高められる (1/2) - ITmedia エンタープライズ
を漸く読み始めた。このような記事がもっと増えたらいいのになぁ

550pt

早速記事に取り上げられている問題をやってみました。

class CirclesCountry
{
public:
  int leastBorders(vector<int> X,vector<int> Y,vector<int> R,int x1,int y1,int x2,int y2){
    vector<int> ans;
    for(int i=0;i<X.size();i++){
      double r1=sqrt((x1-X[i])*(x1-X[i])+(y1-Y[i])*(y1-Y[i]));
      double r2=sqrt((x2-X[i])*(x2-X[i])+(y2-Y[i])*(y2-Y[i]));
      if(r1<R[i]){
        int j;
        for(j=0;j<ans.size() && i!=ans[j];j++);
        if(j==ans.size())ans.push_back(i);
        else ans.erase(ans.begin()+j);
      }
      if(r2<R[i]){
        int j;
        for(j=0;j<ans.size() && i!=ans[j];j++);
        if(j==ans.size())ans.push_back(i);
        else ans.erase(ans.begin()+j);
      }
    }
    return ans.size();
  }
};

一応正解したけど、無駄が多すぎるw
記事に載せられてあるコードを見るまでXOR判定に考えが全く及びませんでした。


memo
・XORなどのビット演算の使い道


それから暇潰しに、この問題を
・点は3つ以上与えられる(点は全て通過する
・スタート地点は予め決定しているが、ゴール地点は決められていない
・円の最小通過経路とその距離を出力する
・円の通過数が同じ経路が2つ以上存在するなら距離が小さい経路とその距離を出力する


のように条件を付けたして拡張してみた。
暫く考え悩んだけど、たぶん今いる地点から各々の点への円の通過数と距離を出して、
円の通過数が一番小さい(円の通過数が同じなら距離が小さいほう)点から順に移動すれば良い(はず