SRM538

結果報告

250-450-1050回でした。

Level	ProblemName	Status	Point
Easy	EvenRoute	PassedSystemTest	230.16
Medium	TurtleSpy	ChallengeSucceeded	0.00
Hard	SkewedPerspective	Opened	0.00

450ミスが痛い…このトラップは覚えておこうと思う。

Easy EvenRoute

問題

二次元座標上の頂点列が数列とによって与えられている。
（がi番目の座標であるとする）
(0,0)から始まり、
座標軸と並行な向きにのみ移動するパスで、与えられた頂点をすべて最低一度は通り、与えられた頂点のどれかを終点とするものを考える。
そのようなパスで、その長さを２で割ったあまりがParity（引数として与えられる）と等しいようなものが存在するか判定せよ。

考えたこと

最低一回通るって事は行ったり来たりしても良いはずである。最短路じゃないし。
というわけで、ある頂点ペアでそのあいだの距離が奇数なものがある場合、その間を行ったり来たりしてパスの偶数奇数を調節できる。
任意の頂点ペアでその間の距離が偶数の場合は、(0,0)->どっかの点への距離がそのまま最終的な距離として反映される。
ここまで考えてコード書いた。

コード

  string isItPossible(vector <int> x, vector <int> y, int wantedParity) {
    int size = x.size();
    for( int i = 0 ; i < size; i++ ){
      for( int j = i+1 ; j < size; j++ ){
        int diff = abs(x[i]-x[j])+abs(y[i]-y[j]);
        if( diff%2 == 1 ) return "CAN";
      }
    }
    int par = (abs(x[0])+abs(y[0]))%2;
    if (wantedParity != par) return "CANNOT";
    return "CAN";
  }

計算量は。

他の人の解答を見て思った事

でもなんとかなるしその方が多数派っぽかった。
具体的には、（0,0)からvまでの距離%2がParityと等しい頂点が一つでもあればYes,でなければNoと返せば良い。

先の僕の考えに沿ってこれを解釈すると、頂点v,u間の距離%2は
（(0,0)からのvまでの距離%2+(0,0)からuまでの距離%2）%2で計算できる。

よって、
ある頂点ペア(u,v)間の距離が奇数である時とは、(0,0)からvまでの距離%2と(0,0)からuまでの距離%2が異なる時と言える。（このとき、少なくともどちらかの頂点は(0,0)からの距離%2がParityと等しいので、上述のアルゴリズムでTrueを返す。これは期待される返り値である。）
一方、任意頂点間の距離が偶数である時とは、(0,0)からvまでの距離%2がすべてParityと等しいorすべてParityと異なる時と言える。（このとき、前者の場合は上述アルゴリズムでもTrueを返し、後者の場合Falseを返す。これは期待される返り値である）

と、取り敢えず正しい事は確認出来る。もうちょっとスマートな解釈の仕方ありそうだけど。

Medium TurtleSpy

問題

「○度右回転」「○度左回転」「距離○だけ前進」「距離○だけ後退」
の４種類の命令から構成される命令列が与えられる。
これらの命令をすべて用いて（順番の入れ替えは許す）、初期位置からできる限り遠い所に行くようにしたい。
得られうる初期位置〜終端位置の距離の最大値を求めよ。

考えたこと

変にグネグネ曲がるよりも前進でできる限り行く・曲がる（出来るだけ１８０度に近く）・後退でできる限り行くとしたほうがお得であろう。
曲がる角度は前進する前に捨てることも考えると任意の組み合わせを考えたいが、
命令数50まで・角度は整数ということを考えると、50*360のDPで愚直に求めても問題ない。
というわけでGreedyで書いた。
実質あってたみたいだけれど、最終距離を余弦定理で出そうとしたら、int*intをする箇所がオーバーフローする、なんていう罠に引っかかって落ちた、悔しい。

教訓：50000*50000はオーバーフローする

コード（PracticeでPass確認済み）

  double maxDistance(vector <string> commands) {
    double result;
    int size = commands.size();
    int length=0;
    int forlength=0;
    vector<int> angle;
    for( int i = 0 ; i < size ; i++ ){
      string  curcom = commands[i];
      istringstream is( curcom );
      string command;
      int value;
      is>> command >> value;
      if( command == "forward" ) forlength+= value;
      if( command =="backward") length+= value;
      if( command == "right" ) angle.push_back( value );
      if( command == "left" ) angle.push_back( -value );
    }
    int anglesize = angle.size();
    bool validangle[51][360];
    memset( validangle , false, sizeof(validangle) );
    validangle[0][0] = true;
    for( int i = 1 ; i <= anglesize; i++ ){
      for( int ang = 0 ; ang < 360; ang++ ){
        if( validangle[i-1][ang] == true ){
          validangle[i][ang] = true;
          validangle[i][(ang+360+angle[i-1])%360] = true;
        }
      }
    }
    int useang=0;
    for( int ang = 180 ; ang >= 0 ; ang-- ){
      if( validangle[anglesize][ang] || validangle[anglesize][360-ang]){
        useang = ang;
        break;
      }
    }
    result = ((double)forlength)*forlength + ((double)length)*length -2.0*forlength*length*cos( 2.0*M_PI*useang/360.0 );
    result = sqrt(result );
    return result;
  }

Hard SkewedPerspective

問題

色々な色のブロックがあり、その個数を数列として与える。（はi種類目のブロックの個数である。また、普通のブロック2個分の高さを持つ黒いブロックをB個持っているとする。
これをw列にわたって積み上げ、それを横から（ブロックが1列に見えるような角度で）見る事を考える。
この視点で見えるブロックの並びのパターン数をmod 1000000007で答えよ。

考えたこと（未完）

……わかんね(´・ω・｀)