SRM641参加しました。 またしても、簡易解説もどきと一緒にコードを貼っていきます。

今回は翌朝用事があったので、CODEINE Phaseが終わったら、そのまま離脱したのですが、終了5秒前にHardをSubmit、その5分後にバグがあることに気づくという慌ただしい回でした。なお、Hardは翌日確認したらやはりシステムテストで落ちてました。 easyとmiddleは、結構早く通せていい感じだったのですが、Hardでつまり、さらにHardのバグに気づいたあと直せると思った手法も誤りがあり、結局再修正が必要と散々な結果でした。

250 : BuyingTshirts

問題概要

Quimey と Pabloがそれぞれ、時間iにQ[i]、p[i]の資金を得て、T以上の資金を持った時、Tシャツを購入する。 Quimey と PabloがTシャツを同じ時間に買うタイミングは何回起こるかを答える。

解法

iは最大100なので、時間0～i-1まで2人の手持ち金額を確認し、同時にTを超えるタイミングを数えればOKです。

コード

class BuyingTshirts {
    public:
    int meet(int T, vector<int> Q, vector<int> P) {
      int ans=0;
      int qq=0;
      int pp=0;

      for(int i=0;i<Q.size();i++)
        {
          qq+=Q[i];
          pp+=P[i];
          if(pp>=T && qq>=T)
            ans++;
          if(pp>=T)
            pp-=T;
          if(qq>=T)
            qq-=T;
        }
        return ans;
    }
};BuyingTshirts.cpp

500 : TrianglesContainOriginEasy

問題概要

複数の点のX,y座標が与える。 その点で三角形を作る時、座標(0,0)を内部に含む組み合わせが何通りあるかをカウントする。

解法

点の数は最大50のため、3重ループで点の組み合わせの全探索を行っても時間的に問題ありません。 三角形と点の内包関係の判定は、それぞれの辺と点の位置関係を見て、同一方向にあるか否かで判定できます。 (ただ、例のごとく私の幾何ライブラリはほとんどないため、判定部分はこちらのサイトのコードを利用しました。)

コード

struct point
{
    point() : x(0), y(0) { }
    point(double x_, double y_) : x(x_), y(y_) { }
    double x, y;
};
point operator-(const point& a, const point& b) { return point(a.x - b.x, a.y - b.y); }
point operator+(const point& a, const point& b) { return point(a.x + b.x, a.y + b.y); }

typedef point vector2d;

// 外積を求める
double cross(const vector2d& a, const vector2d& b)
{
    return a.x * b.y - a.y * b.x;
}

// 点 p が反時計回りの三角形 abc の内側にあるかどうか判定
bool point_in_triangle(const point& p, const point& a, const point& b, const point& c)
{
    // p が ab の右側にあれば三角形の外側にある
    if (cross(p - a, b - a) < 0.0) return false;
    // p が bc の右側にあれば三角形の外側にある
    if (cross(p - b, c - b) < 0.0) return false;
    // p が ca の右側にあれば三角形の外側にある
    if (cross(p - c, a - c) < 0.0) return false;
    return true;
}


class TrianglesContainOriginEasy {
    public:
    int count(vector<int> x, vector<int> y) {
      int ans=0;

      for(int i=0;i<x.size();i++)
        for(int j=i+1;j<x.size();j++)
          for(int k=j+1;k<x.size();k++)
            {

              if(point_in_triangle(point(0,0),point(x[i],y[i]), point(x[j],y[j])
                                   , point(x[k],y[k]))||
                 point_in_triangle(point(0,0),point(x[i],y[i]), point(x[k],y[k])
                                   , point(x[j],y[j]))||
                 point_in_triangle(point(0,0),point(x[j],y[j]), point(x[i],y[i])
                                   , point(x[j],y[j]))||
                 point_in_triangle(point(0,0),point(x[j],y[j]), point(x[k],y[k])
                                   , point(x[i],y[i]))||
                 point_in_triangle(point(0,0),point(x[k],y[k]), point(x[i],y[i])
                                   , point(x[j],y[j]))||
                 point_in_triangle(point(0,0),point(x[k],y[k]), point(x[j],y[j])
                                   , point(x[i],y[i])))
                ans++;
            }

        return ans;
    }
};TrianglesContainOriginEasy.cpp

900 : ShufflingCardsDiv2

問題概要

2n個の要素を{1,2,3…,2n}の順で持つ数列を以下の手順で2回シャッフルする。

1. 現在の数列の先頭n文字を数列A,後方n文字を数列Bと分ける。
2. 数列Aと数列Bを任意の順番にシャッフルする
3. {A[0],B[0],A[1],B[1]…A[n-1],B[n-1]}という順序でマージした数列をあたらしい数列とする

この2回のシャッフルで数列permutationが作成できる場合、“Possible”を、作成できない場合、“Impossible”を返す。

解法

本番中は、{1…2n}からpermutation作ると誤読して、そもそも間違ってました。 手順2の数列の組み合わせは無数にあるので、単純に探索すると厳しいですが、シャッフル回数が2回のため、到達すべき数列から判定することもできます。はじめに1度目のシャッフル後、数列Aは最終的な数列(permutation)の偶数番目の要素番号の要素を持ち、数列Bは奇数番目の要素番号の要素を持っておく必要があります。さらにこの時の数列Aは、1回目のシャッフル後の数列の先頭N文字です。この先頭N文字は、1回めのシャッフル中の際、{A0[0],B0[0],…,A0[(n-1)/2],B0[(n-1)/2]}のようにして作られます。そのため、最初のシャッフル時に数列A0,B0に分けた後、A0,B0それぞれからこの個数の要素を抜き出して数列Aを作るため事ができれば、permutationは作成可能ということになります。

コード

class ShufflingCardsDiv2 {
    public:
    string shuffle(vector<int> permutation) {

      const int n=permutation.size();
      vector<int> ga,gb;
      for(int i=0;i<n;i++)
        {
          if(i%2==0)
            ga.push_back(permutation[i]);
          else
            gb.push_back(permutation[i]);
        }
      sort(ga.begin(),ga.end());
      sort(gb.begin(),gb.end());

      vector<int> a,b;
      int ac=0;
      int bc=0;
      for(int i=1;i<=n;i++)
        {
          if(i<=n/2)
            a.push_back(i);
          else
            b.push_back(i);
        }
      for(int i=0;i<ga.size();i++)
        {
	  if(find(a.begin(),a.end() ,ga[i])!=a.end())
	    ac++;
	  if(find(b.begin(),b.end() ,ga[i])!=b.end())
	    bc++;
	}
      if(ac==(n/4)+(n/2)%2)
        return "Possible";
      else
	return "Impossible";
    }
};ShufflingCardsDiv2.cpp

厳密には今回の解法では、permutationを数列A,Bに分ける際、Aが決まれば自動的にBも決まるため、Aのみの判定で大丈夫なのですが、最初に書き始めた際に一旦保存していたのと、合ったほうがわかりやすいかと思ったので、残しています。