Algoogle

Algorithm for Programming Contest

AMPPZ 2011 Ants

Category: AMPPZ Tag: math

Ants

問題概要


上を向いてる木がある(この木は木構造).
この木の根の左右から2匹の蟻が進んでいく.
左の蟻は上りに1辺1秒, 下りに1辺2秒かかる.
右の蟻はその倍かかる.
この蟻はぶつかると向きが反転する.
地面にぶつかっても反転する.
2回めに蟻が出会う時刻を有理数で求めよ.
ただし入力の木は左側から上るか下るかの列を16進数で圧縮したもので与えられる(グラフを陽に保存するとMLEする).

解法


AMPPZはPolish Collegiate Programming Contest.
解法はLooking for a Challengeにあるのそのまま.
ただ入力を1つづつ受け取るのが面倒+いらない部分を高速に読み飛ばすテクを知らない(そうしないとTLE)ということもあり入力をstringに突っ込んでいる.
これをやるとジャッジではREになるが手元で合うので良しとした.

ただしa, hは実数を許す.
こうすると2匹が初めて出会う時刻について以下の式が成り立つ

実数を扱うのはつらい.
入力を順に読みながら辺ごとに進めていきたい.
現在の辺をa, 高さをh, 上り下りかをbとする.
辺上で中途半端に進んでいる場合, その割合をeとすると

前の等式と合わせると

これが0以上1未満の場合, 1回目の出会いの辺にいることがわかる. tは時間
左の蟻が次に地面にぶつかるのは同じ経路を戻るので辺と高さから整理すると

1回目から2回目の邂逅までにかかる時間について同様に式を立てると

よって

となる. これが0以上1未満のとき, 2回目の出会いになる.
あとは時間を計算すると

コード


(ants.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

struct frac
{
        long long num, den;
        frac(){}
        frac(long long a) : num(a) { den = 1;}
        frac(long long a, long long b) : num(a), den(b) { normalize();}
        void normalize()
        {
                if(num == 0) {
                        den = 1;
                        return;
                }
                if(den < 0) {
                        num *= -1;
                        den *= -1;
                }
                long long t = __gcd(abs(num),den);
                num /= t; den /= t;
        }
        frac operator*=(const frac &f)
        {
                long long t = __gcd(den,abs(f.num)), u = __gcd(f.den,abs(num));
                num = num/u*f.num/t;
                den = den/t*f.den/u;
                return *this;
        }
        frac operator*(const frac &f) const { return frac(*this) *= f;}
        frac operator/=(const frac &f){ return frac(*this)*=frac(f.den,f.num);}
        frac operator/(const frac &f) const { return frac(*this)/=f;}
        frac operator+=(const frac &f){
                long long t = __gcd(den,f.den);
                num = f.den/t*num+den/t*f.num;
                den = den/t*f.den;
                normalize();
                return *this;
        }
        frac operator+(const frac &f) const { return frac(*this)+=f;}
        frac operator-=(const frac &f){
                long long t = __gcd(den,f.den);
                num = f.den/t*num-den/t*f.num;
                den = den/t*f.den;
                normalize();
                return *this;
        }
        frac operator-(const frac &f) const { return frac(*this)-=f;}
        bool operator<(const frac &f) const { return num*f.den < den*f.num;}
        bool operator>(const frac &f) const { return num*f.den > den*f.num;}
        bool operator<=(const frac &f) const { return !(num*f.den > den*f.num);}
        bool operator>=(const frac &f) const { return !(num*f.den < den*f.num);}
        bool operator==(const frac &f) const { return num*f.den == den*f.num;}
};
ostream &operator<<(ostream &os, const frac &f) {
        os<<f.num<<"/"<<f.den;
        return os;
}
const string hx = "0123456789abcdef";

int n, cur;
string b;

inline int next()
{
        cur++;
        return (hx.find(b[cur/4])>>(3-cur%4)&1)? 1: -1;
}

frac solve()
{
        cur = -1;
        int pb;
        frac a(0), h(0), a1, h1;
        for (;;) {
                const int b = next();
                const frac e = (frac(6*n)-a*9-h)/frac(9+b);
                if(frac(0) <= e and e < frac(1)) {
                        a1 = a+e;
                        h1 = h+e*b;
                        cur--;
                        break;
                }
                h += b; a += 1;
        }
        frac ret(-1);
        for (;a < 2*n; a+=1) {
                const int b = next();
                const frac e = (frac(12*n)-(a-a1)*9+h-h1)/(9-b);
                if(frac(0) <= e and e < frac(1)) return ((a1+a+e)*3+h1+h+e*b)/4;
                h = h+b;
        }
        return ((a1+a)*3+h1)/4;
}

int main()
{
        int t; cin >> t;
        while(t--) {
                cin >> n >> b;
                cout << solve() << endl;
        }
        return 0;
}

Comments