TopCoder SRM 587 Div1
最近、Div1の底辺で迷走中のtatsyです。
今日は久しぶりにSRMの解説をやりたいと思います。
今回はEasyとMiddleの2問を解説します。問題のカテゴリとしては、
- Easy (単純計算)
- Middle (幾何)
です。
それでは、見ていきましょう。
Easy (250点)
この問題は、あらかじめターンごとに進める歩数の決まった状況下で一番遠くに行ける場所はどこかを探す問題です。
ある数Nが与えられて、Nターンにわたりiターン目にはi歩だけ進むか、全く進まないで次のターンを迎えるかを選ぶことができます。
ただし、もう一つの数badStepが与えられており、合計がbadStepになるように歩を進めることはできません。
この状況下で最も多く歩数を稼ぐ方法を見つけます。
とはいえ、この問題はとても簡単で単純に1からiまでを足していったときにbadStepに重なるようならば、1ターン目に1歩進むのをやめればいいだけなのです。
したがって、解き方としては、毎ターン歩数iを積算していき、運悪くbadStepと同じ歩数進んでしまうようなら、1を合計歩数から引いて、残りのターンを通常通りに積算していけばいいというわけです。
この問題はほとんどの人が15分くらいで解けてましたね。私も15分くらいかかってしまい、全然点数もらえませんでした。
解答のコードは次の通りです。
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define RPA(i,s,e) for(int i=s; i<=e; i++)
#define RPD(i,s,e) for(int i=s; i>=e; i--)
class JumpFurther {
public:
int furthest(int N, int badStep) {
int S = 0;
RPA(i,1,N) {
S += i;
if(S == badStep) {
S -= 1;
}
}
return S;
}
}
余談ですが、上のコードに示す通り、足してはbadStepとの比較をするのではなく、badStepとの比較をしては足すというコードを書いている人が数人いました。
そうすると、当然ながら最後の1ターンでbadStepに到達してしまった場合のチェックを怠ることになりますので通りません。それでChallengeされている人がいたので一応書いておきます。
Middle (550点)
次の問題は、問題自体はとても単純です。
高さが1、幅がWの長方形が与えられた時、3点(0, 1), (W, 1), (i, 0)で作られる三角形をT[i]とします。
このT[i]により覆われる領域が1、覆われない領域に0を割り当てることにしたとき、T[0]からT[W]までのW+1個の三角形をXORしたら1になる領域の面積はどのくらいか、というのが問題です。
単純に考えれば、地道に交点を求めて、面積を足して行けば良いのですが、なにせ交点はWの2乗くらいはありますので、それでは時間が足りません。
着眼点は横方向にならぶ四角形が同じ面積であるというところで、等面積の四角形は0の部分と1の部分とで合計しても高々W-1種類しかないので、これなら問題を解くことができそうです。
以下が正解のコードです。
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define RPA(i,s,e) for(int i=s; i<=e; i++)
#define RPD(i,s,e) for(int i=s; i>=e; i--)
const double EPS = 1.0e-10;
const double PI = 4.0 * atan(1.0);
int sign(double r) { return r < -EPS ? -1 : r > EPS ? 1 : 0; }
class P {
public:
double x, y;
P() {}
P(int x_, int y_) : x(x_), y(y_) {}
P(double x_, double y_) : x(x_), y(y_) {}
P(const P& p) : x(p.x), y(p.y) {}
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator-() const { return P(-x, -y); }
P operator*(double s) const { return P(x*s, y*s); }
P operator/(double s) const { return P(x/s, y/s); }
P& operator=(const P& p) { x=p.x; y=p.y; return (*this); }
double det(P p) const { return x*p.y - y*p.x; }
double norm() const { return sqrt(x*x + y*y); }
};
double tri(P a, P b, P c) { return (b - a).det(c - a); }
class L {
public:
P s, t;
L() {}
L(P s_, P t_) : s(s_), t(t_) {}
L(const L& l) : s(l.s), t(l.t) {}
L& operator=(const L& l) { s=l.s; t=l.t; return (*this); }
double length() { return (s - t).norm(); }
P vec() const { return t - s; }
P pLL(const L& l) const { return s + vec() * (l.s - s).det(l.vec()) / vec().det(l.vec()); }
};
class TriangleXor {
public:
// compute area of rectangle
double calcArea(P a, P b, P c, P d) {
P p1 = b - a;
P p2 = c - a;
P p3 = d - a;
return 0.5 * (abs(p1.det(p2)) + abs(p3.det(p2)));
}
int theArea(int W) {
double rects = 0.0; // rectangle parts
double tris = 0.0; // triangle parts
P prev = P(0, 0);
const P p1 = P(1, 0);
const P p2 = P(W, 1);
const P p3 = P(0, 1);
P d = P(1, 0);
int cnt = W-1; // number of equivalent rectangles
int mul1 = 1; // whether renctangle part is 0 or 1
int mul2 = 1; // whether triangle part is 0 or 1
RPA(i,1,W) {
double x = i;
x = x / (W + i);
x = x * W;
double y = i;
y = y / (W + i);
P a = P(x, y); // intersection of {(0, 0), (W, 1)} and {(0, 1), (i, 0)}
if(i != 1) {
L l1 = L(p1, p2);
L l2 = L(p3, P(i, 0));
P c = l1.pLL(l2);
rects += cnt * mul2 * calcArea(prev, a, c, d);
d = c;
cnt--;
mul2 ^= 1;
}
tris += mul1 * 0.5 * abs((p3 - a).det(prev - a));
mul1 ^= 1;
prev = a;
}
double S = rects + 2.0 * tris;
if(W%2 == 0) S += W / 4.0;
return (int)S;
}
}
このコードは少し分かりづらいですが、3点(0, 0), (0, 1), (W, 1)が作る三角形の中に現れる四角形を下にあるものから順に処理しています。
もし余裕があったら後で図を作ります。
まとめ
Div1での戦いにもだいぶ慣れてきてEasyは外さなくなってきましたが、まだまだ速度が足りません。Middleなんかも運が良ければ解けそうですが、今のところ手がでてないですね。
少しずつやりながら覚えていくしかないです。