naoya_t@hatenablog

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

CodeChef June LunchTime 2017

f:id:n4_t:20170625113108j:plain
6/24(土) 23:00JST〜(3時間)

230点152位。レーティング落ちると思ってたけど落ちてなかった。
(総合:2028→2077, LunchTime(初)→1602)

Two Numbers (TWONMS; 2065, 30.01%)

自分の番になったら自分の数を2倍する
max(a,b)/min(a,b) って大きい方/小さい方。max(a/b, b/a)。
1回1回gcd取って数を小さく抑えておく?とか一瞬考えたけど
両方が2倍ずつしたら最初と同じに戻るじゃん
(回数%2) でaを2倍するかしないかがあるだけだ
→AC

#include <iostream>
using namespace std;
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);++var)

ll solve(ll a, ll b, ll n) {
  if (n % 2) a *= 2;
  if (a>=b) return a/b;
  else return b/a;
}

int main(){
  int T; cin >> T;
  rep(t,T) {
    ll A,B,N; cin >> A >> B >> N;
    cout << solve(A,B,N) << endl;
  }
  return 0;
}

Maximum Unique Segment (MAXSEGM; 898, 18.22%)

尺取り
右端伸ばして行って重複が検知されたら(1つ戻って)、重複なしの範囲でスコアを(累積和しておいたやつで)求めて
次に何で重複するか知ってるのでそれが現れる次まで左端を動かして。
→AC

// いろいろ略
typedef long long ll;

ll solve(int n, vector<int>& C, vector<int>& W) {
    vector<ll> wac(n+1);
    wac[0] = 0;
    rep(i,n) wac[i+1] = wac[i] + (ll)W[i];

    ll best = 0LL;

    vector<int> stat(n, 0);
    int i=0, j=0; // [i, j)
    int dbl = -1;
    for (i=0; i<n;) {
        for ( ; j<n; ++j) {
            int c = C[j];
            assert(0<=c && c<n);
            if (stat[c] == 1) {
                dbl = c;
                break;
            }
            else ++stat[c];
        }
        // jはdblの位置
        // [i, j)
        assert(i<n && j<=n);
        ll score = wac[j] - wac[i];
        best = max(best, score);

        for ( ; i<n; ) {
            int c = C[i++];
            assert(0<=c && c<n);
            --stat[c];
            if (c == dbl) { dbl = -1; break; }
        }
    }
    return best;
}

int main(){
  int T = loadint();
  rep(t,T) {
    int N = loadint();
    vector<int> C(N), W(N);
    loadvec(C, N);
    loadvec(W, N);
    rep(i,N) assert(0<=C[i] && C[i]<N);
    rep(i,N) assert(0<=W[i] && W[i]<1000000000);
    ll ans = solve(N, C, W);
    printf("%lld\n", ans);
  }
  return 0;
}

Company and Club Hierarchies (COMPCLUB; 64, 7.52%)

問題読んだだけで飛ばして次

Company Club Membership (SHDWCMP; 3, 0.56%)

問題読んだ
ルートから(DFSで)見ていって
ルートからそこに至るまでに、どのクラブに何人所属しているかを持った配列をinc/decするトラックバック
自分と同じクラブの人間が上に2人以上いれば、その中から選んだ2人+自分、の組み合わせの数が、そのノードで新たに発生する
とりあえずの実装で部分点30貰って
部分点もう1つほしいなと思ったけど計算量減らせなくて
COMPCLUBに戻る

// 30点解法
int N, Q;
vector<int> P, C;
vector<vector<int>> children;

vector<int> above;
ll total;

void sub(int node) {
    int cl = C[node];
    int ab = above[cl];
    if (ab >= 2) {
        total += (ab * (ab-1) / 2);
    }
    ++above[cl];
    for (int ch : children[node]) {
        sub(ch);
    }
    --above[cl];
}

int main(){
    vector<int> tmp(2);
    loadvec(tmp, 2);
    N=tmp[0];
    Q=tmp[1];
    P.resize(N-1); C.resize(N);
    loadvec(P, N-1);
    loadvec(C, N);
    children.resize(N);
    rep(i, N-1){
        int parent = P[i], me = i+1;
        children[parent].push_back(me);
    }

    above.assign(N, 0);
    total = 0;
    sub(0);

    //
    printf("%lld\n", total);
    ll ans = total;

    rep(i,Q) {
        int xi = loadint();
        int pers = i % N;
        int newclub = (xi + ans) % N;

        C[pers] = newclub;

        above.assign(N, 0);
        total = 0;
        sub(0);
        printf("%lld\n", total);
        ans = total;
    }
    return 0;
}

Company and Club Hierarchies (COMPCLUB) 再訪

なんかSEGV出るの止められなくて
(上からメモ化再帰してたけどこれはDPで書けるのでは)