algoNote

プログラミング関連

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) C. Optimal Polygon Perimeter

問題

http://codeforces.com/contest/1074/problem/C

解法

マンハッタン距離での周囲の長さなので、選んだ多角形を囲むような(面積最小の)長方形の周囲の長さになります。よって、k=4以上のケースは自明で、n点を囲むような長方形の周長です。

問題はk=3のケースですが、「最左・最上」、「最左・最下」、「最右・最上」、「最右・最下」を固定して、それぞれについて残り1点をすべて試せば最大の周長が求まります。
(証明を書こうとしたけど上手く書けなかった&面倒になったのでeditorialを見てください(おい))

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    REP(i, n) cin >> x[i] >> y[i];
    auto mxx = max_element(ALL(x));
    auto mnx = min_element(ALL(x));
    auto mxy = max_element(ALL(y));
    auto mny = min_element(ALL(y));

    int ans = 0;
    for (auto itrx = begin(x), itry = begin(y); itrx != end(x); ++itrx, ++itry) {
        if (itrx != mnx && itry != mny) chmax(ans, abs(*itrx - *mnx) + abs(*itry - *mny));
        if (itrx != mnx && itry != mxy) chmax(ans, abs(*itrx - *mnx) + abs(*itry - *mxy));
        if (itrx != mxx && itry != mny) chmax(ans, abs(*itrx - *mxx) + abs(*itry - *mny));
        if (itrx != mxx && itry != mxy) chmax(ans, abs(*itrx - *mxx) + abs(*itry - *mxy));
    }

    vector<int> ansv;
    ansv.push_back(ans * 2);
    if (n >= 4) {
        ans = *mxx - *mnx + *mxy - *mny;
        vector<int> tmp(n - 4 + 1, ans * 2);
        ansv.insert(end(ansv), ALL(tmp));
    }
    cout << ansv << endl;
    return (0^_^0);
}

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) B. Intersecting Subtrees

問題

http://codeforces.com/contest/1074/problem/B

解法

クエリの上限は5回ですが、2回で求まります。

まず、yの中から適当なラベルを選んで、自分の木での位置を質問します。この頂点をSとして、Sとxの頂点との距離が最小になる点をPとします。Pの位置の相手のラベルを質問して、これがyに含まれていればPが答えです。そうでなければ共有点はありません。

Pの求め方ですが、Sがxの部分木中に含まれれば、P=Sです。そうでない場合、適当に根を決めると、xの部分木はSの下側か上側にあることになります。

ここで、根付き木上でxの中で一番上にある点をT、xの中で部分木にSを含む頂点のうち一番下にあるものをB(存在するなら)とおくと、Bが存在するならP=Bで、そうでないならP=Tです。

xの部分木がSの上側にあるケースのイメージ
f:id:algon_320:20181108225630p:plain

xの部分木がSの下側にあるケースのイメージ
f:id:algon_320:20181108225637p:plain

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

// in, out: 0-indexed
int ask(char type, int x) {
    cout << type << " " << x + 1<< endl;
    int y;
    cin >> y;
    if (y == -1) exit(0);
    return y - 1;
}
// in: 0-indexed
void answer(int v) {
    cout << "C " << v + 1 << endl;
}
signed main() {
    int Q;
    cin >> Q;
    while (Q--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        REP(i, n - 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb(b);
            g[b].pb(a);
        }

        int k1;
        cin >> k1;
        vector<int> x(k1);
        cin >> x; FORE(i, x) i--;
        sort(ALL(x));

        int k2;
        cin >> k2;
        vector<int> y(k2);
        cin >> y; FORE(i, y) i--;
        sort(ALL(y));

        vector<bool> color(n);
        FORE(i, x) color[i] = true;

        int S = ask('B', y[0]);
        if (color[S]) {
            answer(S);
            continue;
        }

        int T = -1;
        auto findT = [&](auto f, int v, int p) -> void {
            if (color[v] && T == -1) T = v;
            FORE(w, g[v]) {
                if (w == p) continue;
                f(f, w, v);
            }
        };
        findT(findT, 0, -1);

        int B = -1;
        auto dfs = [&](auto f, int v, int p) -> bool {
            if (v == S) return true;
            bool found = false;
            FORE(w, g[v]) {
                if (w == p) continue;
                bool res = f(f, w, v);
                if (res && color[v] && B == -1) B = v;
                found |= res;
            }
            return found;
        };
        dfs(dfs, 0, -1);

        if (B != -1) {
            if (binary_search(ALL(y), ask('A', B))) {
                answer(B);
            } else {
                cout << "C -1" << endl;
            }
        } else {
            if (binary_search(ALL(y), ask('A', T))) {
                answer(T);
            } else {
                cout << "C -1" << endl;
            }
        }
    }
    return (0^_^0);
}

インタラクティブな問題では#define endl "\n"してはいけません...

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) A. The Tower is Going Home

問題

http://codeforces.com/contest/1074/problem/A

解法

以下y軸平行な境界線を"縦線"、x軸平行な境界線を"横線"と呼びます。

方針としては、左からいくつの縦線を消すかを固定して、その時に横線をいくつ消す必要があるかを考えます。 (縦線については最も左にある縦線より右側に侵入することは出来ないので左から連続で消すことを考えればよい)

横線について、同じy座標にある別の境界と端点を共有しないという制約より、x1が1でないものについては無視して良いことが分かります。(端点を共有しない⇔x1が1でない境界についてx1-1の部分を通過出来るので)

縦線を左からk本消すことにすると、x1=1の横線のうち、k+1本目の縦線と交わるものを消せばよいことが分かります。 このような横線がl本あるとすると、k+lの最小値が答えになります。 k+1本目の縦線と交わる横線の個数は、横線を右端でソートしておけば二分探索で求まります。

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(n);
    cin >> x;
    vector<int> y;
    REP(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a != 1) continue;
        y.push_back(b);
    }
    x.push_back(1'000'000'000);
    m = SZ(y), n = SZ(x);
    sort(ALL(x));
    sort(ALL(y));

    int ans = INF;
    REP(i, n) {
        int cnt = end(y) - lower_bound(ALL(y), x[i]);
        chmin(ans, i + cnt);
    }
    cout << ans << endl;
    return (0^_^0);
}

SRM738 easy - FindThePerfectTriangle

System Testで落ちて0ptでした...

問題概要

三角形の周囲の長さ(perimeter)と面積(area)が与えられる。
周囲の長さ、面積が与えられたものに一致し、各頂点の座標が整数となるような三角形が存在するか判定し、存在するなら頂点の座標を返せ。(複数存在するならどれでもいい)

制約

  • perimeter, area は整数
  •  1 \leq area  \leq 10^6
  •  1 \leq perimeter  \leq 1000
  •  0 \leq 頂点の座標の値  \leq 3000

解法

1点を原点に固定して残りの2点の座標を探索します。

2点の座標を(x1, y1), (x2, y2)とすると、面積は area = \frac{1}{2} |x1y2 - x2y1|になります。
変形して area \times 2 = |x1y2 - x2y1|
このうちx1y2を固定することを考えます。答えとなりうる三角形の一辺の長さの値の範囲を考えると、P/2未満であることが必要です。(正の面積を持つので当たり前ですが)
よって各座標値の絶対値はP/2以下であることが分かるので、まずx1を500以下の範囲で決めて、y2をP-x1の範囲で決めます。

絶対値を外す時にx1y2, x2y1の大小によって場合分けが必要ですが、今回は条件を満たす物を1つ出力すれば良いので、x1y2 > x2y1としてしまって問題ありません。
よって、x2y1 = x1y2 - area * 2と決まります。

あとは、符号に注意しながらx2y1を約数に分割してx2,y1を決め、条件を満たすかを試せばよいです。

コード

int isqrt[2000006];

struct FindThePerfectTriangle {
    int P;
    int A;

    inline bool check_sq(int s) {
        int sq = isqrt[s];
        return (sq * sq == s);
    }
    
    inline bool check(int x1, int x2, int y1, int y2) {
        if (abs(x1) > 600 || abs(x2) > 600 || abs(y1) > 600 || abs(y2) > 600) return false;

        int sum1 = x1 * x1 + y1 * y1;
        if (!check_sq(sum1)) {
            return false;
        }
        
        int sum2 = x2 * x2 + y2 * y2;
        if (!check_sq(sum2)) {
            return false;
        }

        int sum3 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
        if (!check_sq(sum3)) {
            return false;
        }

        return (isqrt[sum1] + isqrt[sum2] + isqrt[sum3] == P);
    }

    inline int sign(int x) {
        if (x < 0) return -1;
        return 1;
    }

    vector<int> constructTriangle(int area, int perimeter) {
        for (int i = 0; i * i <= 2000000; i++) isqrt[i * i] = i;

        P = perimeter;
        A = area;

        REP(x1, 501) {
            REP(y2, P - x1) {
                int x2y1 = x1 * y2 - area * 2;

                for (int i = 1; i * i <= abs(x2y1); i++) {
                    if (x2y1 % i == 0) {
                        int x2, y1;

                        for (auto sign1 : {-1, 1}) {
                            for (auto sign2 : {-1, 1}) {
                                if (sign1 * sign2 != sign(x2y1)) continue;

                                x2 = sign1 * i;
                                y1 = sign2 * abs(x2y1) / i;
                                if (check(x1, x2, y1, y2))
                                    return {x1 + 1500, y1 + 1500, x2 + 1500, y2 + 1500, 1500, 1500};

                                y1 = sign1 * i;
                                x2 = sign2 * abs(x2y1) / i;
                                if (check(x1, x2, y1, y2))
                                    return {x1 + 1500, y1 + 1500, x2 + 1500, y2 + 1500, 1500, 1500};
                            }
                        }
                    }
                }
            }
        }

        return {};
    }
};

TLEギリギリだったので少々強引な解な気もします…

ARC103 E - Tr/ee

構築回だったので、得意な人はハッピー回だったみたい。

個人的にはD問題を誤読して部分点すら取れなかったわけですが、時間を掛けて部分点だけで終了となるよりもEを解くべきなので、Dを捨ててEをやったのは正解だったなと思います。 それにしてもみんな強い…。

問題文

E - Tr/ee

考察

まず、N頂点の木なので、サイズNは作れなくて、(葉があるので)サイズ1は必ず作れます。

木から1本辺を削除する操作は、適当な根付き木として考えると、部分木と残りに分ける操作になります。部分木のサイズがiなら残りのサイズはN-iです。 従って、サイズiを作れるなら必ずサイズN-iを作れて、サイズiを作れないならサイズN-iを作ることは出来ません。

f:id:algon_320:20180930091845p:plain

ここまでで、文字列から最後の文字を除いたものが回分になっていることが必要であることが分かりました。

上の条件は必要十分条件であり、以上を満たせば必ず構築出来ます。

具体的には、サイズの小さい順に部分木を作っていきます。
あるサイズの部分木を作るときは、サイズの1つ小さい部分木を子に持つようにした上で、足りない分だけ葉を直接生やせばいいです。(サイズ1の頂点はいくら作っても大丈夫なので)
これを最終的に木のサイズがNになるようになるまで繰り返せば完成。

コード

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    string s;
    cin >> s;
    if (s.front() != '1' || s.back() != '0') {
        cout << -1 << endl;
        return 0;
    }
    int n = s.size() - 1;
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            cout << -1 << endl;
            return 0;
        }
    }

    vector<int> a;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') a.push_back(i + 1);
    }
    a.push_back(n + 1);

    vector<pair<int, int>> ans;
    for (int i = 1; i < a.size(); i++) {
        // 部分木の親の頂点番号をそのサイズと同じにする
        ans.push_back({a[i - 1], a[i]});  // 1つ前の部分木を子に持たせる
        int r = a[i] - a[i - 1] - 1;  // 追加する必要のある葉の個数
        // 追加する葉の頂点番号は1つ前の部分木の親の番号の次から始める
        int v = a[i - 1] + 1;
        for (int j = 0; j < r; j++) {
            ans.push_back({v, a[i]});
            v++;
        }
    }

    for (auto&& p : ans)
        cout << p.first << " " << p.second << endl;
    return 0;
}

感想

コンテスト中はサイズxの部分木を作る時に、x以下でなるべく大きい部分木を子に持つように貪欲に取る必要があるか?などと考えたけど、辺の本数は関係なく頂点の個数だけ考えればいいので、必要に応じて葉をぶら下げるだけで十分でした。 (というかN頂点の木に含まれる辺は必ずN-1本なので、辺を考えても同じですね)

  • サイズxの部分木を作ろうと思ったら、ちょうどx個の頂点が必要
  • x個頂点があったら、構造によらずサイズxの部分木を作れる

この2点が自明だけど大切な点っぽい