SRM 538 Div.1

随分空いてしまった。

結果

oo-　381.48pts
1344->1436(+92)

Highest更新&&初midpassed(450だけど)

250

xy平面上にある点の集合に対し、(0,0)を出発点として全ての点
を任意の順で訪問するとき、歩数のparity(偶奇)が与えられたものと
一致するような訪問順が存在するか？という問題。

移動は最短路で行われると書いていないのがミソかもしれない。
任意のx1,x2,x3に対してx1->x2と移動する途中にx3に寄ったとして

      x1------->x2

      x1---x3-->x2

x3<---x1
  --->x1------->x2

      x1------->x2----->x3
                  <-----x3

と書いてみると、どう寄っても途中の経路によってparityは変化しない
ということが解る。よって、与えられた点列の中に
原点からのmanhattan distanceが与えられたparityと等しくなる点が
存在すればよい。

    string isItPossible(vector <int> x, vector <int> y, int wantedParity) {
        bool isok = false;
        int n=x.size();
        for(int i=0;i<n;i++){
            if((abs(x[i]) + abs(y[i])) % 2 == wantedParity){
                isok = true;
            }
        }   
        return isok?"CAN":"CANNOT";
    }

450

({{左|右}回転|前進|後退},距離)という命令の列が与えられる。
全ての命令を実行したあとの位置のうち、原点からのeuclid distanceの最大値を返す。

前進->180度回転->後退が最大になるのは明らかなので、
結局はどの角度に回転できるかがわかればよい。
作れる角度のうち、180度に最も近いものを選べば良い。
のでDP

dp[i][j] := i個命令を実行したときにj度が作れればtrue and v.v.

あとは何度回転させるか調べて、x,y座標を求めればいい。

余弦定理を使って計算させるとオーバーフローするようだ。怖い。

     double maxDistance(vector <string> commands) {
         string str;
         int n;
         int forward =0;
         int backward= 0;
         bool angle[361];
         vector<int> order;
 
         memset(angle, false, sizeof(angle));
         angle[0] = true;
         for(int i=0;i<commands.size();++i){
             istringstream iss(commands[i]);
             iss >> str >> n;
             if(str == "forward"){
                 forward += n;
             }else if(str == "backward"){
                 backward += n;
             }else if(str == "left"){
                 order.push_back(n);
             }else{
                 order.push_back(-1 * n);
             }
         }
         for(int i=0;i<order.size();i++){
             vector<int> makable;
             for(int j=0;j<361;j++){
                 if(angle[j] == true){
                     int tmp = j + order[i];
                     if(tmp < 0){
                         tmp += 360;
                     }else if(tmp <= 360){
                         //do nothing
                     }else{
                         tmp -= 360;
                     }
                     makable.push_back(tmp);
                 }
             }
             for(int j=0;j<makable.size();j++){
                 angle[makable[j]] = true;
             }
         }
         int maxi = max(forward, backward);
         int mini = min(forward, backward);
 
         double x = maxi;
         double y = 0;
         double PI = acos(-1);
         int ang;
         for(ang=0;ang<=180;ang++){
             if(angle[180-ang] == true) break;
             if(angle[180+ang] == true) break;
         }
         x += mini * cos((double)ang/180*PI);
         y += mini * sin((double)ang/180*PI);
 
         return sqrt(x*x + y*y);
     }

challenge

450で落とせそうなものがあったけど
気力がなかった。

感想

なんとかレート維持させたいです。