日本橋ハーフマラソンに参加しました

日本橋ハーフマラソンの参加記です．

予選

http://rco-contest-2017-qual.contest.atcoder.jp/

A問題

まずサイズ２のミノを作って，それらを繋げてサイズ４のミノを作って，それらを繋げてサイズ８のミノを作りました．
結果は640400点で109位でした．

B問題

事前にエサ間の距離を求めておいて，訪れるエサの順番をビームサーチっぽく探索しました．
結果は13658点で44位でした．

全体では66位で学生では42位でした．
本戦の学生枠は40人だったのですが，なぜか予選を通過しました．

本戦

http://rco-contest-2017-final.contest.atcoder.jp/

A問題

スコアの計算方法を見ると石油をDリットル売る度にD^2のスコアが得られるようになっているため，Dが小さいときに石油を売るのはあまり嬉しくないことが分かります．よって，できるだけ大きいDについて石油を売ることを目指すという方針にしました．具体的には以下のようなことをやりました．

  • D>31のとき，石油タンクにfillすることで時間TまでにDだけ石油を用意できるならfillしてsellする．
  • 上を満たさないならば，5未満の石油タンクを一つchangeする．
  • 上を満たさないならば，空の石油タンクを一つfillする．
  • 上を満たさないならば，passする．

結果は7169275点で3位でした．

B問題

問題名から分かる通り，愚直に実装すると大渋滞を起こしそうだったため方針を決めるのにだいぶ悩みました．悩んだ結果，選んだ方針は以下の通りになりました．

  • 各車について一番近い四隅を目的地に設定する．
  • 目的地が遠い車から順に目的地に近づくような移動ができるならば移動する．移動できないならば1/2の確率で離れる移動をする．
  • ある程度すべての車が目的地に近づいたらマップを４分割し，分割したそれぞれのマップで車の目的地を一番近い四隅に再設定する．
  • 上記を繰り返す

動き方の様子は以下の動画を見ると分かりやすいかもしれません．
youtu.be
結果は86021点で5位でした．

全体では2位で学生では1位でした．

懇親会

懇親会ではピザとケンタッキーのチキンがありました．（残念ながら🍣はありませんでした．）他には，Typing War対決とかやってて面白かったです．

来年もまだ学生なのでぜひもう一度開催してほしいです．

topcoder SRM366 Div2 Hard PickGuitars

問題URL : https://community.topcoder.com/stat?c=problem_statement&pm=8177&rd=10781

{ \displaystyle }

問題概要

n個のギターケースが円状に置かれている．
各ギターケースには価値G[i]のギターが入っている．
プレイヤーA,Bが交互にギターを取っていくゲームを行う．
ゲームのルールは以下の通りである．
空でない連続して並んでいるギターケースのグループについて，
プレイヤーAは各グループから１つずつギターケースを選びギターを取る．
次は，同じようにプレイヤーBが各グループからギターを取る．
以上の操作をギターがなくなるまで交互に繰り返す．
お互いのプレイヤーが取ったギターの価値の総和を最大にするように行動したとき，
プレイヤーAが取るギターの価値の総和を求めよ．

解法

よくある区間DP．
円状になっているが，プレイヤーAがギターを１つ選んでしまえば一列に並べて考えられる．
区間DPだと分かってしまえばあとは一瞬．

コード

vint v;
int n;

int dp[55][55];

int f(int l, int r, bool first=false){
    (l+=n)%=n;
    (r+=n)%=n;
    if(l==r) return v[l];
    if(dp[l][r]>=0) return dp[l][r];
    if(l>r) r+=n;
    int ret = -INF;
    int sum = 0;
    reep(i,l,r+1){
        sum += v[i];
    }
    if(first){
        reep(i,l,r+1){
            maxs(ret, sum-f(i+1, i-1));
        }
    }
    else{
        reep(i,l,r+1){
            if(i==l){
                maxs(ret, sum-f(l+1, r));
            }
            else if(i==r){
                maxs(ret, sum-f(l, r-1));
            }
            else{
                maxs(ret, sum-f(l, i-1)-f(i+1, r));
            }
        }
    }
    return dp[l%n][r%n] = ret;
}


struct PickGuitars {
    vector<int> g;
    int maxValue(vector<int> _guitarValues) {
        g = _guitarValues;
        n = g.size();
        v = vint(2*n);
        rep(i,n){
            rep(j,n){
                dp[i][j] = -1;
            }
        }
        rep(i,n){
            v[i] = g[i];
            v[i+n] = g[i];
        }        
        return f(0,n-1,true);
    }
};

コメント

典型でした

yukicoder No.460 裏表ちわーわ

yukicoder

問題URL : http://yukicoder.me/problems/no/460

{ \displaystyle }

問題概要

各マスが黒か白からなるm x nの盤面が与えられる．
白と黒は表裏になっている．
操作としてあるマスとその8近傍のマス（端の場合はマスが存在する箇所だけ）をひっくり返すことができる．
すべてのマスを白にすることができるならば，最小操作回数を求めよ．
不可能な場合はImpossibleと表示せよ．

解法

盤面の一番上の行と一番左の列は合計m+n-1マスある．
これらのマスで操作を行うかを全探索する．
以下，それ以外のマスについてのみ操作を行う場合を考える．
上からi行目(0-indexed)，左からj列目(0-indexed)のマスを(i,j)(0-indexed)とすると，
(1,1)で操作を行わなければならないのは(0,0)が黒である場合のみである．
なぜなら，(0,0)をひっくり返せる操作は(1,1)での操作のみだからである．
あとはこれを順番に繰り返せばよい．
(0,0), (0,1), (0,2), ..., (0,n-1), (1,0), ... といった順番でマスを見ていき，(i,j)が黒であったらその右下のマス(i+1,j+1)で操作を行う．
(m-1, n)までマスを見終わったとき，盤面が全て白になっている場合の操作回数の最小値が求める答えとなる．
計算量はO(2^(m+n)*m*n)時間

コード

vvint vv;
int h, w;

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()) {
    v.assign(a, vector<T>(b, t));
}

bool inside(int y, int x) {
    return 0 <= y && y < h && 0 <= x && x < w;
}

void change(int y, int x, vvint &vv) {
    rep(i, 3) {
        rep(j, 3) {
            if(inside(y - 1 + i, x - 1 + j)) {
                vv[y - 1 + i][x - 1 + j] ^= 1;
            }
        }
    }
}

int check() {
    int ret = 0;
    vvint tmp = vv;
    rep(i, h) {
        rep(j, w) {
            if(tmp[i][j]) {
                if(!inside(i + 1, j + 1)) return INF;
                ret++;
                change(i + 1, j + 1, tmp);
            }
        }
    }
    return ret;
}


int dfs(int y, int x) {
    if(x == w) return dfs(1, 0);
    if(y == h) return check();

    int ret = INF;
    if(y == 0) {
        mins(ret, dfs(y, x + 1));
        change(0, x, vv);
        mins(ret, dfs(y, x + 1) + 1);
        change(0, x, vv);
    }
    else {
        mins(ret, dfs(y + 1, x));
        change(y, 0, vv);
        mins(ret, dfs(y + 1, x) + 1);
        change(y, 0, vv);
    }
    return ret;
}


void mainmain() {
    cin >> h >> w;
    initvv(vv, h, w);
    rep(i, h) rep(j, w) cin >> vv[i][j];
    int ans = dfs(0, 0);
    cout << (ans >= INF / 2 ? "Impossible" : to_string(ans)) << endl;
}

コメント

SRMで似た問題を解いた気がするけど思ったより時間がかかってしまった．

topcoder SRM365 Div2 Hard HittingPerfectTarget

topcoder

問題URL : https://community.topcoder.com/stat?c=problem_statement&pm=7575

{ \displaystyle }

問題概要

2つの凸多角形p1,p2が与えられる．
格子点{ \displaystyle (i,j) \in [-100,100]^2 }にダーツを投げるゲームをする．各格子点に刺さる確率は一様である．
p1とp2に包含されている格子点にダーツが刺さる確率を求めよ．

解法

まず，[-101, 101]^2の範囲でp1に包含されない格子点を全列挙することを考える．
これは以下の深さ優先探索(DFS)を行うことで計算可能である．
格子点(-101,-101)からスタートする．
現在，格子点uにいるとし，vをuに隣接する格子点とする．
vがp1の辺上にある，または，線分uvとp1の辺が交差するならば何もしない．
そうでなければvに移動する．
DFSが終了したときに訪問済みの格子点がp1に包含されない格子点となる．

p2についても同様に包含される格子点を全列挙する．
あとは，どちらのDFSでも未訪問の格子点を数えて201^2で割れば求める確率が計算できる．

コード

typedef complex<double> P;

// 許容する誤差ε
#define EPS (1e-10)

// 内積 (dot product) : a・b = |a||b|cosΘ
double dot(P a, P b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}

// 外積 (cross product) : a×b = |a||b|sinΘ
double cross(P a, P b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

// aからbに向かって, 1 -> 右, -1 -> 左, 2 -> aの真後ろ, -2 -> bよりも奥の前, 0 -> 線分ab上に存在
int ccw(P a, P b, P c) {
    P d = b - a;
    c -= a;
    double cr = cross(d, c);
    if(cr < -EPS) { return 1; }
    if(cr > EPS) { return -1; }
    if(dot(d, c) < -EPS) { return 2; }
    if(norm(d) < norm(c) - EPS) { return -2; }
    return 0;
}

// a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
int is_intersected_ls(P a1, P a2, P b1, P b2) {
    return ccw(a1, a2, b1) * ccw(a1, a2, b2) <= 0 &&
           ccw(b1, b2, a1) * ccw(b1, b2, a2) <= 0;
}

namespace std {
bool operator <(const P &a, const P &b) {
    if(a.real() != b.real()) return a.real() < b.real();
    return a.imag() < b.imag();
}
}

int ccw2(P p, P a, P b) {
    a -= p;
    b -= p;
    if(cross(a, b) > EPS) return 1;
    if(cross(a, b) < -EPS) return -1;
    if(dot(a, b) < -EPS) return 2;
    if(norm(b) - norm(a) > EPS) return -2;
    return 0;
}

vector<P> convex_hull(vector<P> ps) {
    int n = ps.size(), k = 0;
    sort(ps.begin(), ps.end());
    vector<P> ch(2 * n);
    for(int i = 0; i < n; ch[k++] = ps[i++]) while(k >= 2 && ccw2(ch[k - 2], ch[k - 1], ps[i]) <= 0 && ccw2(ch[k - 2], ch[k - 1], ps[i]) != -2) --k;
    for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--]) while(k >= t && ccw2(ch[k - 2], ch[k - 1], ps[i]) <= 0 && ccw2(ch[k - 2], ch[k - 1], ps[i]) != -2) --k;
    ch.resize(k - 1);
    return ch;
}


struct HittingPerfectTarget {
    vector<int> x1;
    vector<int> y1;
    vector<int> x2;
    vector<int> y2;

    bool inside(int y, int x) {
        return -101 <= y && y <= 101 && -101 <= x && x <= 101;
    }
    bool check(P a, P b, vector<P> &v) {
        int n = v.size();
        rep(i, v.size()) {
            if(ccw(v[i], v[(i + 1) % n], a) == 0) return false;
            if(is_intersected_ls(v[i], v[(i + 1) % n], a, b)) return false;
        }
        return true;
    }

    void dfs(int x, int y, vvint &ret, vector<P> &v) {
        if(ret[x + 101][y + 101]) return;
        ret[x + 101][y + 101] = 1;
        int dd[] = {0, 1, 0, -1, 0};
        rep(i, 4) {
            int yy = y + dd[i];
            int xx = x + dd[i + 1];
            if(inside(yy, xx) && check(P(xx, yy), P(x, y), v)) {
                dfs(xx, yy, ret, v);
            }
        }
    }
    vvint func(vint &x, vint &y) {
        int n = x.size();
        vector<P> v(n);
        rep(i, n) v[i] = P(x[i], y[i]);
        vvint ret;
        initvv(ret, 203, 203);
        v = convex_hull(v);
        dfs(-101, -101, ret, v);
        return ret;
    }

    double getProbability(vector<int> _x1, vector<int> _y1, vector<int> _x2, vector<int> _y2) {
        x1 = _x1, y1 = _y1, x2 = _x2, y2 = _y2;
        vvint res1 = func(x1, y1);
        vvint res2 = func(x2, y2);
        double cnt = 0;
        rep(i, 203) {
            rep(j, 203) {
                if(res1[i][j] == 0 && res2[i][j] == 0) {
                    cnt += 1;
                }
            }
        }
        return cnt / 201 / 201;
    }
};

コメント

幾何は面倒

yukicoder No.456 Millions of Submits!

yukicoder

問題URL : http://yukicoder.me/problems/no/456

{ \displaystyle }

問題概要

整数a,bと実数tがm回与えられる．
各a,b,tについて以下の式を満たす最大のnを計算せよ．
{ \displaystyle n^a\log ^b n = t }

解法

mが最大10^6と大きいため，単純に二分探索を行うとTLEしてしまう．
そこでaとbで場合分けを行う．

(1) a = 0 or b = 0 のとき

計算式は
{ \displaystyle n = \mathrm{e}^{t^{\frac{1}{b}}} } or { \displaystyle n = t^{\frac{1}{a}} }
と式変形できるため簡単に計算できる．

(2) それ以外(a > 0 and b > 0) のとき

nの取りうる値の範囲について考えてみると，
a=1, b=1, t=10 のとき n = 5.72 ... で最大となり，
a=10, b=10, t=0.1 のとき n = 1.62 ... で最小となる．
よって探索範囲は1 < n < 6 とすれば十分だと分かる．
許容誤差は10^-9なので log 5/10^-9 = 32.219 ... < 33 回以上探索を繰り返せば精度は足りる．
あとは，powの計算を繰り返し二乗法で計算することでTLEせずに計算することができる．
(std::powを使うとTLE)
(for文でpowを計算しても間に合うらしい...)

コード

double mypow(double x, int y) {
	double a = 1;
	while(y) {
		if(y & 1) a = a * x;
		x = x * x;
		y >>= 1;
	}
	return a;
}

inline double f(int a, int b, double x) {
	return mypow(x, a) * mypow(log(x), b);
}

void mainmain() {
	int m;
	scanf("%d", &m);
	rep(i, m) {
		int a, b;
		double t;
		scanf("%d%d%lf", &a, &b, &t);
		if(a == 0) {
			double ans = exp(pow(t, 1. / b));
			printf("%.10lf\n", ans);
			continue;
		}
		else if(b == 0) {
			double ans = pow(t, 1. / a);
			printf("%.10lf\n", ans);
			continue;
		}
		double l = 1;
		double r = 6;
		rep(j, 35) {
			double mid = (l + r) / 2;
			double val = f(a, b, mid);
			if(t <= val) r = mid;
			else l = mid;
		}
		printf("%.10lf\n", l);
	}
}

コメント

ごり押しでごめんなさい

yukicoder No.454 逆2乗和

yukicoder

問題URL : http://yukicoder.me/problems/no/454

問題概要

非負実数xが与えられる．
{ \displaystyle \sum_{n=1}^{\infty} \frac{1}{(n+x)^2} }を計算せよ．

{ \displaystyle 0 \leq x \leq 1000 }

解法

厳密解を求めるのは難しいので近似解を求める．
xの整数部分をa，小数部分をbとする．
問題文に書かれている公式{ \displaystyle \sum_{n=1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6} }を用いて計算式を変形すると

{ \displaystyle \begin{eqnarray} \sum_{n=1}^{\infty} \frac{1}{(n+x)^2} &=& \sum_{n=1}^{\infty} \frac{1}{(n+a+b)^2} \\ &=& \sum_{n=a+1}^{\infty} \frac{1}{(n+b)^2} \\ &=& \sum_{n=a+1}^{\infty} \frac{1}{(n+b)^2} \\ &\fallingdotseq& \sum_{n=a+1}^{N} \frac{1}{(n+b)^2} + \sum_{n=N+1}^{\infty} \frac{1}{n^2} \\ &=& \sum_{n=a+1}^{N} \frac{1}{(n+b)^2} + \sum_{n=1}^{\infty} \frac{1}{n^2} - \sum_{n=1}^{N} \frac{1}{n^2} \\ &=& \sum_{n=a+1}^{N} \frac{1}{(n+b)^2} + \frac{\pi^2}{6} - \sum_{n=1}^{N} \frac{1}{n^2} \\ \end{eqnarray} }
となる．
あとは {\displaystyle N}をどれくらい大きくすれば許容誤差に収まるかを考ればよい．
{ \displaystyle \frac{1}{n^2} - \frac{1}{(n+b)^2} \leq \frac{1}{n^2} - \frac{1}{(n+1)^2} = O(\frac{1}{n^2}) }なので
{\displaystyle N = 10^5}とすれば誤差は {\displaystyle 10^{-9}}以下となる（気がする）．

コード

void mainmain() {
	double x;
	cin >> x;
	int a = x;
	double b = x - a;
	double sum1 = 0;
	double sum2 = 0;
	int N = 1e5;
	reep(i, 1 + a, N) {
		sum1 += pow(1. / (i + b), 2);
	}
	reep(i, 1, N) {
		sum2 += pow(1. / i, 2);
	}
	double ans = sum1 + pow(acos(-1), 2) / 6 - sum2;
	cout << ans << endl;
}

コメント

解説を見たら想定別解と方針は似てました．（想定別解はおそらく間違いが含まれている）