れんしゅうちょう。

■ [FacebookHackerCup]FHC2013 QR 01:33

結果はまだ不明.

1/30 追記: ooo 100pts 27:11:12 208位

テンプレにはよくあるやつと, Case #まで出力するやつ.

int to_i(string s){
    stringstream ss;
    ss << s;
    int res;
    ss >> res;
    return res;
}
int main(){
    cout.setf(ios::fixed); cout.precision(10);
    string s;
    getline(cin, s);
    int n = to_i(s);
    rep(i, n){
        cout << "Case #" << (i+1) << ": ";
        solve();
    }
    return 0;

Beautiful strings

出現頻度でソートして, 多かったのに高い点を割り当てる.

bool inRange(int a, int x, int b){
    return a <= x && x < b;
}
void solve(){
    string s;
    getline(cin, s);
    vector<ll> cnt(26);
    repsz(i, s){
        if(inRange('A', s[i], 'Z'+1)) s[i] += 'a'-'A';
        if(inRange('a', s[i], 'z'+1)){
            ++cnt[s[i]-'a'];
        }
    }
    sort(all(cnt));
    ll res = 0;
    repsz(i, cnt) res += cnt[i] * (i+1);
    cout << res << endl;
}

Balanced Smileys

言い訳:

まず, |s|<=50と勘違いしていた. dpを思いつかず, 半分全列挙した.

Cより難しいんじゃねえのこれとか思っていた.

O(2^(|s|/2/2)*log)くらい.

顔文字ばかり50個とか来たら割と死んだはずだけど, テストケース甘くて助かった感強い.

enum Type{
    OPEN, CLOSE, NONE
};
struct parenthesis{
    Type type;
    bool smilable;
    parenthesis(Type type, bool smilable): type(type), smilable(smilable){}
    parenthesis operator-() const {
        parenthesis res(type, smilable);
        if(type == OPEN) res.type = CLOSE;
        if(type == CLOSE) res.type = OPEN;
        return res;
    }
};

bool chk(const vector<parenthesis> &in, int mask, int &depth){
    int cnt = 0;
    depth = 0;
    repsz(i, in){
        Type t = in[i].type;
        if(in[i].smilable){
            if((mask>>cnt&1) == 0) t = NONE;
            ++cnt;
        }
        if(t == OPEN) ++depth;
        if(t == CLOSE) --depth;
        if(depth < 0) return false;
    }
    return true;
}

bool solve2(const vector<parenthesis> &in){
    vector<parenthesis> A, B;
    repsz(i, in){
        if(i < sz(in)/2) A.pb(in[i]);
        else B.pb(-in[i]);
    }
    B = vector<parenthesis>(rall(B));
    int cntA = 0, cntB = 0;
    foreach(it, A) if(it->smilable) ++cntA;
    foreach(it, B) if(it->smilable) ++cntB;

    set<int> ok;
    rep(i, 1<<cntA){
        int t;
        if(chk(A, i, t)){
            ok.insert(t);
        }
    }
    rep(i, 1<<cntB){
        int t;
        if(chk(B, i, t)){
            if(ok.count(t)) return true;
        }
    }
    return false;
}

void solve(){
    string s;
    getline(cin, s);
    vector<parenthesis> in;
    repsz(i, s){
        if(s[i] == '('){
            in.pb(parenthesis(OPEN, i>0 && s[i-1] == ':'));
        }else if(s[i] == ')'){
            in.pb(parenthesis(CLOSE, i>0 && s[i-1] == ':'));
        }
    }
    if(solve2(in)){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return;
}

DP思いついて書いた.

bool solve2(vector<parenthesis> &in){
    vector<int> dp(sz(in)+10), qb(sz(in)+10);
    dp[0] = true;
    repsz(ptr, in){
        repsz(t, qb) qb[t] = false;
        repsz(i, dp) if(dp[i]){
            int d = (in[ptr].type == OPEN ? 1 : -1);
            if(in[ptr].smilable) qb[i] = true;
            if(i+d >= 0) qb[i+d] = true;
        }
        swap(dp, qb);
    }
    return dp[0];
}

QRみたいな時間に余裕あるときは, 適当にstructとか作って纏めると, 頭がこんがらがったりしなくてよいなぁとか思った.

Find the Min

数列は, しばらくすると0からkまでの数字しか使わなくなり, k+1周期で同じになる.

次の数を探すのは, range sum queryを処理出来るBITとかを使う.

直近k個で使っている数をカウントしておき, BITで, 使っている数には1, 使っていない数には0を割り当てる.

sum([0, n)) != nとなる最初のnを二分探索で探せば, 次の数になる.

あと, 最初のk個の生成をintでやってると多分死ぬ.

namespace BIT{
    static const int MAX = (int)(1E6);
    int bit[MAX] = {};
    inline void init(){
        memset(bit, 0, sizeof(bit));
    }
    inline int sum(int i){ // a <= i
        ++i;
        int s = 0;
        while(i > 0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    inline int sum(int a, int b){//a <= i < b
        return sum(b-1) - sum(a-1);
    }
    inline int get(int i){
        return sum(i, i+1);
    }
    inline void add(int i, ll x){
        ++i;
        while(i <= MAX){
            bit[i] += x;
            i += i & -i;
        }
    }
    inline void set(int i, int x){
        add(i, x - get(i));
    }
}; //namespace BIT

inline ll mulMod(ll a, ll b, ll m){
    ll res = 0;
    a %= m; b %= m;
    if(a < 0) a += m;
    if(b < 0) b += m;
    for(; b; b>>=1){
        if(b&1) res = (res + a) % m;
        a = (a<<1) % m;
    }
    return res;
}

deque<ll> make_seq(ll a, ll b, ll c, ll r, ll k){
    deque<ll> res;
    ll mm = a;
    rep(i, k){
        res.push_back(mm);
        mm = (mulMod(b, mm, r) + c) % r;
    }
    return res;
}
int search_next_value(){
    if(BIT::get(0) == 0) return 0;
    int res = 0, d = 1;
    while(true){
        if(BIT::MAX <= d || BIT::sum(d-1) != d) break;
        d <<= 1;
    }
    while(d){
        int t = res + d;
        if(t-1 < BIT::MAX && BIT::sum(t-1) == t) res = t;
        d >>= 1;
    }
    return res;
}
void solve(){
    BIT::init();
    ll n, k;
    cin >> n >> k;
    ll a, b, c, r;
    cin >> a >> b >> c >> r;

    int cnt[BIT::MAX] = {};
    deque<ll> seq = make_seq(a, b, c, r, k);

    repsz(i, seq) if(seq[i] < BIT::MAX){
        BIT::set(seq[i], 1);
        ++cnt[seq[i]];
    }

    vector<ll> res(k+20);
    rep(j, k+10){
        res[j] = search_next_value();
        ++cnt[res[j]];
        BIT::set(res[j], 1);
        seq.push_back(res[j]);

        ll t = seq.front(); seq.pop_front();
        if(t < BIT::MAX){
            --cnt[t];
            if(cnt[t] == 0) BIT::set(t, 0);
        }
    }
    cout << res[n%(k+1)] << endl;
}

ツイートする