ゆるふわ競技プログラミングオンサイト at FORCIA #3 writer料は初任給に含まれます

forcia.connpass.com
2/29(日) 13:30-19:00

バルト9で劇場版SHIROBAKO（公開初日）を観てから徒歩でフォルシアへ。（近いので）
コロナウィルス対策で各種イベント等が中止になり始めた時期で、会場に入る前にうがい手洗いを求められた。

FORCIAのゆるふわオンサイトは今回が第3回。
第1回から参加しているのだけれど（第2回は出張先から参加）、競プロerが順調に吸い込まれていく様子が楽しい。
（ゴリの人とか第1回では一般参加者でしたよね）

これまで同様HackerRankのシステムを利用してのコンテストで、今回はDiv.1とDiv.2に分かれていた。

（青以上の人はDiv.1に参加するようにとの事）

面白い問題揃いだったけれど時間が足りなかったかな…
懇親会でFORCIAの皆さん、writerのNoiminさんtempuraさん等ともお話できて良かった。

New Comers (300)

第1回・第2回の参加者をsetに入れておいて
第3回の参加者のうち、setに含まれない人名を数える

→AC

int main() {
  int a,b,c; cin>>a>>b>>c;
  set<string> st;
  rep(i,a) { string s; cin >>s; st.insert(s); }
  rep(i,b) { string s; cin >>s; st.insert(s); }
  int cnt=0;
  rep(i,c) { string s; cin >>s; 
      if (!found(st,s)) ++cnt;
      }
      cout<< cnt << endl;
    return 0;
}

Median Permutation (400)

逆順に決めて行けそうなのは見えた
場合分けをしながらパターンを考えてたけどパス

解説解

逆順に決めて行けるのはその通り
Nが奇数の場合：

まず右端は全体の中央値なので1つに決まる
その左隣りは任意に選べる。それを選ぶとその左は一意に決まる
同様に左端まで詰めていくので (N-1)!(N-3)!(N-5)!・…・6!4!2! 通り

Nが偶数の場合：

右端は任意に選べる。
その左隣りは残りの全体の中央値なので1つに決まる
その左隣りは任意に選べる。それを選ぶとその左は一意に決まる
同様に左端まで詰めていくので N!(N-2)!(N-4)!(N-6)!・…・5!3!1! 通り

Bananas Multiplier (Easy) (300)

制約がゆるいのでWFで相互間の距離（というか倍率）を求めておいて（ $O(N^3)$ ）
クエリに答える（ $O(1)$ ）

→AC

int N, Q;
vi u, v, c;
vi m, p, x;

vector<vector<ii>> d;

#define INFTY 9999

void prep(){
    d.assign(N, vii(N, ii(INFTY,0)));
    rep(i,N) d[i][i] = ii(0,0);
    rep(i,N-1){
        d[ u[i] ][ v[i] ] = d[ v[i] ][ u[i] ] = ii(1, c[i]);
    }
    rep(k,N) rep(i,N) rep(j,N) {
        int d_ikj = d[i][k].first + d[k][j].first;
        if (d[i][j].first > d_ikj){
            int v_ikj = MUL(d[i][k].second, d[k][j].second);
            d[i][j] = ii(d_ikj, v_ikj);
        }
        // d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
    }
}

ll solve(int m, int p, ll x){
    return MUL(x, d[m][p].second);
}

int main() {
    scanf("%d%*c", &N);
    u.resize(N-1);
    v.resize(N-1);
    c.resize(N-1);
    rep(i,N-1){
        scanf("%d %d %d%*c", &u[i], &v[i], &c[i]);
        --u[i]; --v[i];
    }
    scanf("%d%*c", &Q);
    m.resize(Q);
    p.resize(Q);
    x.resize(Q);
    rep(i,Q){
        scanf("%d %d %d%*c", &m[i], &p[i], &x[i]);
        --m[i]; --p[i];
    }

    prep();
    rep(i,Q){
        ll ans = solve(m[i],p[i],x[i]);
        printf("%lld\n", ans);
    }
    return 0;
}

Bananas Multiplier (Hard) (200)

制約がきついけど LCAすればよさそう
ダブリングで実装し始めたけど計算あわなくて終了＞＜

Banana Game (600)

Sweets Distribution(Easy) (400)

前半の2人と後半の2人の境目を全探索
前半（後半）2人の分担をどこにするのが良いか：Bで取った場合とAで取った場合の差分の最大がどこに来るかをRMQで解く

→AC

template <typename T1, typename T2>
vector<T2> accum(vector<T1>& a, T2 init);

template <typename T>
T accumed(vector<T>& acc, int from, int to);

template <typename T>
class SegmentTree;

ll solve(int N, vi& a,vi& b,vi& c,vi& d) {
    vll acc = accum(a, 0LL);
    vll bcc = accum(b, 0LL);

    reverse(ALL(c));
    reverse(ALL(d));
    vll ccc = accum(c, 0LL);
    vll dcc = accum(d, 0LL);

    SegmentTree<ll> sta(N+2, MAXIMUM), stb(N+2, MAXIMUM);
    for(int i=1; i<=N; ++i){
        sta.update(i, accumed(acc,1,i) - accumed(bcc,1,i));
        stb.update(i, accumed(dcc,1,i) - accumed(ccc,1,i));
    }

    auto abmax = [&](int x) -> ll {
        ll r = a[0] + accumed(bcc, 1, x) + max(0LL,sta.query(1, x+1)) + b[x];
        return r;
    };
    auto cdmax = [&](int x) -> ll {
        ll r = d[0] + accumed(ccc, 1, x) + max(0LL,stb.query(1, x+1)) + c[x];
        return r;
    };

    ll best = 0;
    for (int b=1; b<=N-3; ++b){
        int c = (N-1) - (b+1);
        amax(best, abmax(b) + cdmax(c));
    }
    return best;
}

int main() {
    int N; scanf("%d%*c", &N);
    vi a(N),b(N),c(N),d(N);
    loadvec(a,N);
    loadvec(b,N);
    loadvec(c,N);
    loadvec(d,N);
    cout << solve(N,a,b,c,d) << endl;
    return 0;
}

naoya_t@hatenablog

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