naoya_t@hatenablog

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

CodeChef SnackDown17 Online Qualifier Round

f:id:n4_t:20170525094530p:plain
17/5/20〜24 (5pm IST)
期間は4日あって、1問だけ通せばいいみたいなんだけど
参加者、というか参加チーム数21038

Snake Procession [SNAKPROC] 11776 38.93%

許容される状態は2つ(蛇の胴体の途中=1か、そうでない=0か)
状態0で初めて、左からスキャンして
'. ' : 0→0, 1→1
'H': 0→1, 1→error
'T': 0→error, 1→0
全部読んだ後 0 になっていればOK

#!/usr/bin/env python

def solve(line):
    mode = 0
    for ch in line:
        if ch == '.':
            continue
        elif ch == 'H':
            if mode != 0: return False
            mode = 1
        elif ch == 'T':
            if mode != 1: return False
            mode = 0
        else:
            assert False
    return mode == 0

def main():
    R = int(raw_input())
    for r in range(R):
        L = int(raw_input())
        line = raw_input().rstrip()
        assert len(line) == L
        ans = solve(line)
        print ('Invalid', 'Valid')[int(ans)]

main()

Temple Land [TEMPLELA] 10798 51.38%

1234321みたいな
・長さLが奇数であること
・H=(L+1)/2 としたとき i=[0..H) について a[i] = a[L-1-i] = 1+i であること

#!/usr/bin/env python

def solve(line):
    L = len(line) 
    # print L, line
    if L % 2 != 1: return False
    H = (L+1) / 2
    for i in range(H):
        if line[i] != (1+i): return False
        if line[L-1-i] != (1+i): return False
    return True

def main():
    R = int(raw_input())
    for r in range(R):
        L = int(raw_input())
        line = map(int, raw_input().rstrip().split(' '))
        assert len(line) == L
        ans = solve(line)
        print ('no', 'yes')[int(ans)]

main()

Same Snake [SAMESNAK] 2857 12.87%

水平・水平、または垂直・垂直の場合は同一直線状で、繋がっているか重なっているか:(x_max - x_min) ≦ (x1max - x1min) + (x2max - x2min)
水平・垂直、または垂直・水平の場合はL字状に接していること
2匹が成す長方形領域で、水平のほうが上辺か下辺になっていて、垂直の方が左辺か右辺になっていること

#!/usr/bin/env python

def solve(x11,y11,x12,y12, x21,y21,x22,y22):
    v1 = x11 == x12 
    h1 = y11 == y12 
    assert v1 != h1
    v2 = x21 == x22
    h2 = y21 == y22
    assert v2 != h2

    left   = min(x11,x12,x21,x22)
    top    = max(y11,y12,y21,y22)
    right  = max(x11,x12,x21,x22)
    bottom = min(y11,y12,y21,y22)
    # print (left, top, right, bottom)

    if v1 and v2:
        w = top - bottom
        w1 = abs(y11 - y12)
        w2 = abs(y21 - y22)
        return x11 == x21 and w1 + w2 >= w
        
    elif h1 and h2:
        w = right - left
        w1 = abs(x11 - x12)
        w2 = abs(x21 - x22)
        return y11 == y21 and w1 + w2 >= w

    elif v1 and h2:
        return x11 in (x21, x22) and y21 in (y11, y12)

    elif h1 and v2:
        return y11 in (y21, y22) and x21 in (x11, x12)


def main():
    R = int(raw_input())
    for r in range(R):
        line1 = map(int, raw_input().rstrip().split(' '))
        assert len(line1) == 4
        x11, y11, x12, y12 = line1

        line2 = map(int, raw_input().rstrip().split(' '))
        assert len(line2) == 4
        x21, y21, x22, y22 = line2

        ans = solve(x11,y11,x12,y12, x21,y21,x22,y22)
        print ('no', 'yes')[int(ans)]

main()

Snake Eating [SNAKEEAT] 1640 5.62%

T ≦5, N≦1e5, Q≦1e5 という条件で、2秒制限。O(T(N^2+NQ)) 解はNG
O(T(N+Q)logN) に落としたい
・(T x 1 x) L を大きい順に並べておく : O(N logN)
・(T x Q x) 各クエリ qi について、
・L
で q 以上の長さの蛇が何匹いるか調べる : O(logN)
・長さq未満の蛇について、何匹を犠牲にすれば残りの蛇の長さがq以上になるか、を二分探索で調べられるものなら調べる。調べられるようにしたい。調べられるかな。: O(logN)
・一番長い蛇の長さ(L[0])に揃えるにはどれだけ伸ばすべきか(どれだけ食料が必要か)を長い順に1匹ずつ増やして累算した配列を用意 : 最初にO(N)
・k 匹を長さ m にするのに必要な食料(蛇)を求めるのは、
長さm以上の蛇を除外して (これをa匹とすると、残りk-a匹に餌が必要)
a[k] - a[0]
先の累積配列はL[0]ベースなので、ここから(L[0] - m)(k - a) だけ差し引く
で、それが N-k 以内ならいける

#include <iostream>
#include <algorithm>
#include <vector>
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()

int main() {
    int T; cin >> T; // 5
    rep(t, T){
        int N, Q; cin >> N >> Q; // 1-1e5

        vector<ll> L(N);
        rep(i,N) cin >> L[i];

        sort(all(L), greater<ll>());

        vector<ll> a(1+N); a[0] = 0LL;
        for (int i=0; i<N; ++i) {
            a[1+i] = a[i] + (L[0] - L[i]);
        }
/*
        auto p = [=](int x,int cnt,int i) -> bool {
            return (a[i] - a[cnt] + (x - L[0]) * (i - cnt)) <= N-i;
        };
*/
        rep(q, Q) {
            ll x; cin >> x;
            ll level = x - L[0];
            int cnt = (int)(lower_bound(all(L), x, greater<ll>()) - L.begin());

            if ((a[N] - a[cnt] + level * (N - cnt)) <= 0) {
                cout << N << endl;
                continue;
            }

            int lo = cnt, hi = N+1, m;
            ll rhs = a[cnt] + level * cnt + N;
            while (lo+1 < hi) { // lo=always
                m = (lo + hi)/2;
                if (a[m] + (level + 1)*m <= rhs) {
                    lo = m;
                } else {
                    hi = m;
                }
            }
            cout << lo << endl;
        }
    }
    return 0;
}

今回得られた知見

  • ループの中でλを宣言するのは結構重い

↑O(logN)でもかなり大きな定数がかかってTLE

  • テストケースの全部が最悪ケースだと5秒ぐらいかかるけど投げてみたら1.3秒ぐらいで終わってAC