TopCoder SRM 641 Div2 参加記


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;
}
};

view raw
BuyingTshirts.cpp
hosted with ❤ by GitHub

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;
}
};

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";
}
};

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


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください