naoya_t@hatenablog

いわゆるチラシノウラであります

CodeChef SnackDown17 Pre-Elimination Round-A

f:id:n4_t:20170529101554p:plain
SnackDown17の本戦前選抜ラウンド(その1)。
5問目(PROTEPOI)考えながら寝落ちしてた。4完742位でElimination Roundに進出。
(通過ラインは4完で、1469チームが進出した模様)
> Qualifiers: 1問通せばOK→ (10000+)
> Pre-Elimination Round-A/B: (10000+) -> 各1000+
> Elimination: 2000+ -> 57
> Onsite final: 57 -> 1

Ranklist - SNCKPA17 | CodeChef
チーム名はケロン軍っぽいやつ。(※メンバー1名)

1. Team Formation For Snackdown (TEAMFORM)

https://www.codechef.com/SNCKPA17/problems/TEAMFORM
8954/12859 teams; accuracy=74.7%

nが偶数ならOK、奇数ならNG、でいいんだよね

def solve(n, m, uvs):
    return n % 2 == 0

みたいな。mもu_i, v_iも使わずに。
(そんな簡単な問題なはずがない、とか思って少し悩んだ)
→AC

def read_line():
    return raw_input().rstrip()

def read_tokens():
    return read_line().split(' ')

def read_ints():
    return map(int, read_tokens())

def read_int1():
    (intv,) = read_ints()
    return intv

def solve(n, m, uvs):
    # assert 1 <= m <= n/2
    # assert len(uvs) == m
    return n % 2 == 0

def main():
    T = read_int1() # 1-100
    for t in range(T):
        n, m = read_ints() # 2-100, 1-n/2
        uvs = []
        for i in range(m):
            ui, vi = read_ints()
            uvs.append((ui, vi))
        ans = solve(n, m, uvs)
        print ('no', 'yes')[int(ans)]

main()

2. Is It a Snake (ISSNAKE)

https://www.codechef.com/SNCKPA17/problems/ISSNAKE
3839/12859 teams; accuracy=17.75%

2行しかスペースがない。水平方向に伸びても1回しか折り返せない。

####....
########

水平折り返しパターンは垂直折り返しパターンでもカバーできるので考えなくていい(上の例だと、(3,0)→(0,0)→(0,1)→(7,1) のような水平折り返しパターンを考える代わりに (0,1)→(0,0)→(1,0)→(1,1)→(2,1)→(2,0)→(3,0)→(3,1)→(7,0) のように垂直折り返しパターンでも同じことができる。)
左端から見て行って(1行目左端からと2行目左端からを両方試す)全体をなぞれるか調べる。
1投目WA。1行目からのチェックでうまく行かない時に2行目を見に行かずにFalseを返してしまう実装上の不具合があったのを直して2投目AC。

## 入力系はAと共通
from collections import Counter

def solve(n, mp):
    assert 1 <= n <= 500 # from Constraints
    assert len(mp) == n and len(mp[0]) == 2

    cn = Counter(''.join(mp))
    len0 = cn['#']
    assert len0 > 0 # from Constraints

    first = -1
    for i, col in enumerate(mp):
        if col != '..':
            first = i
            break

    assert first >= 0 and mp[first] != '..'
    mp = mp[first:]

    last = -1
    for i, col in enumerate(mp):
        if col == '..':
            last = i
            break
    if last >= 0:
        mp = mp[:last]
        pass

    for col in mp:
        assert col != '..'

    cn = Counter(''.join(mp))
    len1 = cn['#']
    if len1 == 0: # empty
        return False
    elif len1 < len0: # body is splitted
        return False

    ## solve
    possible = False

    for s in range(2): # start : 0 or 1
        if mp[0][s] != '#': continue

        row = s
        visited = 0
        for col in mp:
            if col == '##':
                visited += 2
                row = 1 - row
            else: # '#.' or '.#'
                if col[row] == '#':
                    visited += 1
                else:
                    break  # ここで return False してしまっていて初投WA

        if visited == len1:
            possible = True
            break

    return possible

def main():
    T = read_int1() # 1-500
    for t in range(T):
        n = read_int1() # 1-500
        l1 = read_line()
        l2 = read_line()
        mp = [l1[i]+l2[i] for i in range(n)]
        ans = solve(n, mp)
        print ('no', 'yes')[int(ans)]

main()

3. A Temple of Snakes (SNTEMPLE)

https://www.codechef.com/SNCKPA17/problems/SNTEMPLE
2141/12859 teams; accuracy=13.43%

高さhの山に必要なブロックはh^2個。
// h + 2*h(h-1)/2 = h + h(h-1) = h^2
全部で Σh_i = S ブロックあるとすると、山をどこに取ろうが S - h^2 個のブロックを削り取ることになる。
どこなら取れるのか。
ある地点まで(左から)登ってこられる最遠地点という概念があるとしたら、その初期値はその地点そのもの。
これが求められれば、その地点を頂点にする山(左半分)の最高高度 = (ある地点まで登って来られる一番遠い麓までの距離) + 1 であり、右側バージョンとの min() の最大値が、可能な一番高い山の高さになる。
後者の「ある地点まで登って来られる一番遠い麓までの距離」の方を更新していった方が計算が楽そう。初期値オール0だし。

u_i = h_i - (1+i) みたいな数列を用意して(別に用意せずその場で計算しても良いんだけど、ここでは自分が考えやすくするために用意)、即ち、h から [1 2 3 4 5 6 7... ] を引いた(h を45度倒した)数列を左から見ていって、どこまで非負でいられるかを見てみる。
[1 2 3 4 4 3 2] が [0 0 0 0 -1 -3 -5] になって、これは先頭(i=0)から i=3の位置まで登れることを意味する。高さでいうと 4 (=(3-0)+1)。
i=1 の地点まで登れる最遠の麓までの距離を 1-0=1 で更新。
i=2 の地点まで登れる最遠の麓までの距離を 2-0=2 で更新。
i=3 の地点まで登れる最遠の麓までの距離を 3-0=3 で更新。
(i=4 では -1 なので、ここを崖の位置として覚えておく)

登り始めるのを i=1 にした場合は h[1:] から [1 2 3 4 ...] を引いたものを見るわけだけど、これは先の 0 0 0 0 -1 -3 -5 に1ずつ加えて (1) 1 1 1 0 -2 -4 にしたものを見るのと同等。今回は i=4 の位置まで登れる。(i=0 から登り始める時に i=3 までは行けていて、崖がi=4 だったのを覚えているので、今回はその崖の位置から先のみを調べれば良かった)。
i=2 の地点まで登れる最遠の麓までの距離を 2-1=1 で…既にi=0からの登頂の際に最大距離2が記録されているので更新なし。
i=3 の地点まで登れる最遠の麓までの距離を 3-1=2 で...同じく3なので更新なし
i=4 の地点まで登れる最遠の麓までの距離を 4-1=3 で更新。

このようにして、元のブロックの高さが [1 2 3 4 4 3 2] の場合の「ある地点まで登って来られる一番遠い麓までの距離」が L = [0 1 2 3 3 2 1] のように求まる。これは左から登頂した場合。
右からの登頂の場合も同様に計算して R = [0 1 2 3 2 1 0] を得る。
L = [0 1 2 3 3 2 1]
R = [0 1 2 3 2 1 0]
ある地点を頂点にした場合の最高高度は、min(L[i], R[i]) の最大値に1を加えたもの。ここでは h = max([0 1 2 3 2 1 0])+1 = 4
h=4の山を作るのに必要なブロック数 = 1+2+3+4+3+2+1 = 4^2 = 16
元のS = Σ(1 2 3 4 4 3 2) = 19 からこれを引いた 3 が答え。

1投目WA。一番高くまで登れた地点のデータしか更新していなかった。(3 3 3 3 とかで
0122 2210 になるべきところが0022 2200になってしまってmax(min())が0になる)
そこを修正してAC。(コードでコメントアウトしてる部分)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

typedef long long ll;

#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) x.begin(),x.end()

ll solve(int n, vector<int>& h) {
    ll S = 0LL; rep(i, n) S += (ll)h[i];
    //
    vector<int> lfarthest(n, 0), rfarthest(n, 0);

    vector<int> ltor(n), rtol(n);
    rep(i, n) {
        ltor[i] = h[i] - (1+i);
        rtol[(n-1)-i] = h[(n-1)-i] - (1+i);
    }

    for (int i=0,to=1; i<n; ++i) {
        while (to < n && i+ltor[to] >= 0) {
            lfarthest[to] = max(lfarthest[to], to-i);
            ++to;
        }
//        while (to < n && i+(h[to]-(1+to)) >= 0) ++to;
//        lfarthest[to-1] = max(lfarthest[to-1], (to-1)-i);
    }

    for (int i=0,to=n-2; i<n; ++i) {
        while (to >= 0 && i+rtol[to] >= 0) {
            rfarthest[to] = max(rfarthest[to], (n-1)-i-to);
            --to;
        }
//        while (to >= 0 && i+(h[(n-1)-to]-(1+to)) >= 0) --to;
//        rfarthest[to+1] = max(rfarthest[to+1], (n-1)-i-(to+1));
    }

    int highest = 0;
    rep(i, n) {
        int hi = min(lfarthest[i], rfarthest[i]) + 1;
        if (hi > highest) highest = hi;
    }
    return S - highest*highest;
}

int main() {
    int T; cin >> T;
    rep(t, T) {
        int n; cin >> n;
        vector<int> h(n);
        rep(i,n) cin >> h[i];
        ll ans = solve(n, h);
        cout << ans << endl;
    }

    return 0;
}

4. Consecutive Snakes (CONSESNK)

https://www.codechef.com/SNCKPA17/problems/CONSESNK

1404/12859 teams; accuracy=13.12%

とりあえず、入力データの蛇の位置Si がソートされてるか分からないのでソートする
蛇(の頭)の行き先は x, x+1L, x+2L, ..., x+(n-1)L である。但し A ≦ x ≦ B-nL。
ここに左の蛇から順にあてがっていけばいい?(ここで、入れ替わった方が合計移動距離が減らせるケースってあるんじゃないか、と暫く悩んだ。入れ替わっても合計移動距離が変わらないケースはあるが、減らせはしない、よね)
合計移動距離は Σ |(x+kL)-Sk| = Σ|x - (Sk-kL)| で。
これが最小になる整数x(A ≦ x ≦ B-nL)を求めたい。
折れ線(x = Sk - kL の箇所で傾きが変わって行く)で下に凸な関数になるはずだよねこれは。なので頂点(というか、頂点に一番近いx)を求めるのは三分探索でOK。
1投目WA。xの探索範囲を(A ≦ x ≦ B)にしてしまっていた。
自明っぽいテストデータ

3
1 10 10 20
3
1 10 10 20
13
1 10 10 20
23

に 7 0 3 みたいな答えを返してきていて気づいた。(7 3 13が正しい答え)
xの探索範囲を修正してAC。

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
using namespace std;

typedef long long ll;

#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) x.begin(),x.end()
#define found(s,e)  ((s).find(e)!=(s).end())

int N;
ll L,A,B;
vector<ll> S, u;

ll p(ll t) {
    ll sum = 0LL;
    rep(k,N) sum += abs(t - u[k]);
    return sum;
}

ll solve() {
    sort(all(S));

    u.resize(N);
    rep(k,N) u[k] = S[k] - L*k;

    mm.clear();

//  ll a=A, b=B;  ##OOPS##
    ll a=A, b=B-N*L;
    while (a+3 <= b) {
        ll d = (b-a)/3;
        ll m1 = a+d, m2 = b-d;
        assert(m1 < m2);
        ll p1 = p(m1), p2 = p(m2);
        if (p1 < p2) {
            b = m2;
        } else if (p1 > p2) {
            a = m1;
        } else {
            a = m1; b = m2;
        }
    }

    ll best = 1LL << 62LL, best_arg;
    for (ll x=a; x<=b; ++x) {
        ll px = p(x);
        if (px < best) {
            best = px;
            best_arg = x;
        }
    }
    return best;
}

int main() {
    int T; cin >> T;
    rep(t, T) {
        cin >> N >> L >> A >> B;
        S.resize(N);
        rep(i,N) cin >> S[i];

        ll ans = solve();
        cout << ans << endl;
    }
    return 0;
}

5. Protecting The Poison (PROTEPOI)

https://www.codechef.com/SNCKPA17/problems/PROTEPOI

863/12859 teams; accuracy=16.68%

上下方向からの守りと左右方向からの守りは独立に考えてよさそう。
KxK の各セル(というか各行、各列)が守られるのに最低限必要な蛇ってどう最適化すればいい?
(フローとか色々考えながら寝落ちして、目が覚めたらコンテストは終わってた)

【practice】

冷静に考えたらそんなに難しい問題じゃなかった
KxK正方形の縦の辺をカバーする蛇・横の辺をカバーする蛇、に分ける(どちらにも属さないものは捨てる。両方に属することはない)。
あとは、(電車で言ったら)端の駅から乗って一番遠くまで行けるやつに乗って、降りたら、そこを走ってる電車の中で一番遠くまで行けるやつに乗って、の繰り返しで何本で逆の端まで行けるか(あるいは行けないか)。というのを縦・横独立に求めればいい。
各蛇がカバーしている区間をinterval tree(区間木)に登録しておいたら、ある地点をカバーしているすべての蛇を求める、みたいなクエリが恐らくO(log M + w)で出来ると思うのだけれど(wはクエリで出てくる区間数)。interval treeの構築にかかる計算量はO(MlogM)かな。ただ、interval treeがカバーする全領域の端から端までの分に比例したメモリを食うので、多分座標圧縮したほうがいい。
初投WA。蛇の頭と尾が反対に記述されるケースでもあるのかと思って、逆転してたらswapするみたいなコードを追加したけどまたWA。
あ。座標圧縮の仕方が悪いのか。
例えば [1-2, 3-4, 6-7] → [1-2, 3-4, 5-6] で、元の 5 が飛ばされてることを表現できてない。
区間ではなく開区間で出てくる座標を拾ったら [1-3, 3-5, 6-8] → [1-2, 2-3, 4-5] で、圧縮してから閉区間に戻せば [1-1, 2-2, 4-4] のように途中の断絶がちゃんと表現される。
という修正を加えてAC。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) x.begin(),x.end()

#define NDEBUG
#ifdef DEBUG
#include "cout11.h"
#undef NDEBUG
#endif
#include <cassert>


typedef pair<int,int> Segment;

inline int ceil2(int n) {
    if (n == 0) return 1;
    int k = (sizeof(int) << 3) - __builtin_clz(n-1);
    return 1 << k;
}

class IntervalTree {
public:
    vector<vector<Segment> > stock;
    int N, l, r;

public:
    IntervalTree(int l, int r) {
        this->l = l;
        this->r = r;
        this->N = ceil2(r - l + 1);
        stock.assign(N*2, vector<Segment>());
    }
    ~IntervalTree() {}

public:
    void insert(Segment seg) {
        int sl = seg.first - this->l, sr = seg.second - this->l;
        queue<ii> q;
        q.push(ii(0, N));
        while (!q.empty()) {
            int b = q.front().first, w = q.front().second;
            q.pop();
            if (sl <= b && b+w-1 <= sr) {
                //here
                int L = N/w, i = b/w;
                stock[L+i].push_back(seg);
                continue;
            }
            if (w == 1) continue;
            int m = w/2;
            if (sl < b+m) {
                q.push(ii(b, m));
            }
            if (b+m <= sr) {
                q.push(ii(b+m, m));
            }
        }
    }

    vector<Segment> search(int p) {
        vector<Segment> res;

        if (p < l || r < p) return res;
        p -= l;

        int cnt = 0;
        for (int w=1,i=0,m=N; m>=1; w*=2,m/=2,i*=2) {
            int x = N/w;
            if (p & m) {
                ++i;
                p -= m;
            }
            res.insert(res.end(), all(stock[w+i]));
        }
        return res;
    }
};


int compress(int K, set<ii>& spans, vector<ii>& compressed) {
    set<int> xs;
    xs.insert(0); xs.insert(K);
    for (auto span : spans) {
        xs.insert(span.first);
        xs.insert(span.second + 1);
    }

    map<int, int> mp;
    int i = 0;
    for (int x : xs) mp[x] = i++;

    for (auto span : spans) {
        compressed.push_back(ii(mp[span.first], mp[span.second+1]-1));
    }

    return mp[K];
}

int sub(int K, set<ii> spans) {
    vector<ii> compressed;
    int cK = compress(K, spans, compressed);

    IntervalTree it(0, cK-1);
    for (ii cx : compressed) it.insert(cx);

    int ans = 0;
    for (int x=0; x<=cK-1; ) {
        vector<Segment> sg = it.search(x);
        if (sg.size() == 0) return -1;
        priority_queue<int> pq;
        for (Segment s : sg) {
            pq.push(s.second);
        }
        int latest = pq.top();

        ans++;
        x = latest + 1;
    }
    return ans;
}

int solve(int N, int K, int M, vector<int>& HX, vector<int>& HY, vector<int>& TX, vector<int>& TY) {
    assert(HX.size() == M && HY.size() == M);
    assert(TX.size() == M && TY.size() == M);

    int margin = (N - K)/2;
    int start = margin, end = margin + (K-1); // [start, end]

    set<ii> tate, yoko;
    rep(i, M) {
        int hx = HX[i]-margin-1, hy = HY[i]-margin-1, tx = TX[i]-margin-1, ty = TY[i]-margin-1;
        if (hx >= tx && hy >= ty) {
            swap(hx, tx); swap(hy, ty);
        }
        // [1..N] -> [-margin .. K+margin-1]
        assert(hx <= tx && hy <= ty);
        if (hx == tx) { // vertical. x=hx, y=[hy..ty]
            int x = hx;
            if (0 <= x && x <= K-1) {
                assert(ty < 0 || K-1 < hy);
                // above/below the KxK box
                yoko.insert(ii(x, x));
            } else { // x < start || end < x
                hy = max(0, hy); // if (hy < start) hy = start;
                ty = min(K-1, ty); // if (end < ty) ty = end;
                if (0 <= hy && hy <= ty && ty <= K-1) {
                    tate.insert(ii(hy, ty));
                }
            }
        }
        else if (hy == ty) { // horizontal. y=hy, x=[hx..tx]
            int y = hy;
            if (0 <= y && y <= K-1) {
                assert(tx < 0 || K-1 < hx);
                tate.insert(ii(y, y));
            } else { // y < start || end < y
                hx = max(0, hx);
                tx = min(K-1, tx);
                if (0 <= hx && hx <= tx && tx <= K-1) {
                    yoko.insert(ii(hx, tx));
                }
            }
        }
        else {
            assert(false);
        }
    }

    int tate_ans = sub(K, tate);
    int yoko_ans = sub(K, yoko);
    if (tate_ans < 0 || yoko_ans < 0) return -1;
    return tate_ans + yoko_ans;
}

int main() {
    int T; cin >> T;
    rep(t, T) {
        int N, K, M;
        cin >> N >> K >> M; // 3-1e9, [1, N-2], 1-1e5
        vector<int> HX(M), HY(M), TX(M), TY(M);
        rep(i, M) {
            cin >> HX[i] >> HY[i] >> TX[i] >> TY[i]; // [1, N]
        }
        int ans = solve(N, K, M, HY, HX, TY, TX);
        cout << ans << endl;
    }

    return 0;
}

6. A Game of Balls (GAMEBALL)

https://www.codechef.com/SNCKPA17/problems/GAMEBALL
368/12859 teams; accuracy=17.04%
開いてない