four-t practice 2019 #04

2019 年 3 月 2 日 (土) に 2014 Tehran Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

開始。今回は環境構築の練習も兼ねて rsk0315 にコンパイルや実行のショートカット？を色々書いてもらい、TAB は前から、自分は後ろから見ていった。前の方に簡単な問題が多かったらしく、TAB が A, B をすぐ通してくれた。その後 F も rsk0315 が通してくれた。文字列系はだいたい rsk0315 に投げると解いてくれるのでたすかる。その間自分は後ろの問題の読解に苦戦していたので焦っていた。

I から K まで読んで、これ簡単な問題ひとつもなくないかと思いながら問題概要をいろいろ説明していく。伝えあっているうちに D が放置されていたことに気づき、みたらわりとわかりやすい最短路だったので解く AC (これ時間的にもったいなかったなあ) その後少々つまりながらも C も通る。

G は問題設定がなんかおもしろい。グラフである必要なくないかと思ったけどよく考えたら連結でないときに壊れることを TAB が指摘してくれたので助かった。これはすんなり通ってくれた。

簡単枠が全部片付いたので残りを全員で考えてみる。J は DP っぽいけどどう考えても無理なのでフローで考えたら方針ガチャに成功 (？) して、少々時間がきつそうな解法を思いついたが信じて提出。1WA したけど (すいません) 通る

I は幾何っぽいが、直感的にこうすればいいんじゃないかなあと思った解法を TAB に説明して書いてもらう。YesNo 問題だしサンプルがよわよわなので怖かったが一発で通る。幾何の方針だけ説明して実装を任せる悪い人になってしまった。残り 1 時間 45 分残して 8 完で、あと 3 問。

ここからかなりつらくて、主に E と H を考察していて H を実装したけど WA になってしまってそのまま終了。たぶん考察に漏れがある系のミスな気がするけど、復習しないとわからないですね・・・。

反省

2 桁チームが AC している問題を取りこぼすことは少なくなってきた気がする。まあ日本のアジア地区に比べて出題傾向もレベルも違う気がするのでアレなんですが・・・不可能枠の復習わりと不可能だけどやるしかないのかなあ

環境構築したら問題読解係の連携がちょっと崩れてしまったので、やっぱりこの辺含めて練習したほうが良さそう。ペナルティをすくなくしていきたい

やっぱり最後 1 時間で何もできなくなってしまいがちなのでそもそももう少し強くなりたいですね、おわり

Educational Codeforces Round 2 E: Lomsat gelral

問題概要

原文 → Problem - E - Codeforces

頂点からなる根付き木が与えられる。根は頂点 であり、木の各頂点には色 がついている。

各頂点 について、 を根とする部分木に存在する頂点の中で、塗られている個数が最も多い色を求め (タイもすべて数えるため複数ある場合がある)、色 id の合計を出力せよ。

解説

データ構造をマージする一般的なテク、通称「マージテク」を使って解くことを考えます。

現在の頂点 の情報と子 の情報をマージする際に、必ず「サイズが小さい方を大きい方に向けてマージする」ようにします。こうすることでマージ全体にかかる時間がならし 時間になります。map の計算量も含めて、 で処理可能です。

ソースコード

using Graph = vector< vector<int> >;

int N, col[100010], res[100010];
map<int, int> exist[100010];
map<int, int> sum[100010];

void solve(Graph &G, int cur, int par=-1) {
    exist[cur][ col[cur] ] = 1;
    sum[cur][1] = col[cur];
    for(auto to : G[cur]) {
        if(to == par) continue;
        solve(G, to, cur);

        // サイズを比較して、小さい方を大きい方に向けてマージ
        if(exist[cur].size() < exist[to].size()) {
            swap(exist[cur], exist[to]);
            swap(sum[cur], sum[to]);
        }

        // to を cur にマージ
        for(auto e : exist[to]) {
            int id, cnt; tie(id, cnt) = e;
            if(exist[cur].count(id)) {
                int cnt_ = exist[cur][id];
                cnt += cnt_;
                exist[cur][id] = cnt;
                sum[cur][cnt_] -= id;
                sum[cur][cnt ] += id;
            }
            else {
                exist[cur][id] = cnt;
                sum[cur][cnt] += id;
            }
        }
    }
    int ans = (--sum[cur].end())->second;
    res[cur] = ans;
}

signed main() {
    scanf("%lld", &N);
    for(int i=0; i<N; i++) {
        scanf("%lld", &col[i]);
    }

    Graph G(N);
    for(int i=0; i<N-1; i++) {
        int u, v;
        scanf("%lld%lld", &u, &v);
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    solve(G, 0);
    for(int i=0; i<N; i++) {
        printf("%lld%c", res[i], " \n"[i+1 == N]);
    }
    return 0;
}

four-t practice 2019 #03

2019 年 2 月 24 日 (日) に 2013 Daejeon Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

開始。TAB が A〜D を、rsk0315 が E〜H を、自分が I〜L をざっと読んでいくことに。A はやるだけらしいので書いてもらう。通る。I は見た目がやばそうだったが冷静になると簡単だったので書く。通る。G もすぐわかったらしいので書いてもらう。通る。続けて K, L も通る。開始 1 時間で 5 問解けたのでけっこうよさげ。

J 問題は一回飛ばしていたけど TAB 君と一緒に考察したら実は行けそうみたいな気持ちになる。とりあえず書いて提出したけど TLE した。よく考えたら前計算の部分をテストケースごとにやる必要はなくて、while 文の外でやれば良いので直す。通る。このペナはもったいないね。

続けて F を書くも WA が出る。若干方針に自信がなかったし、方針ミスかも？と思って一旦放置してしまう。

しばらくして、rsk0315 がずっと取り組んでいた H 問題 (文字列) が通った。正答率低い問題を通せるのすごい。

ここで rsk0315 が F のソースコードをにらむと間違いを見つけてくれる (神か？) 直したら AC した。本当に申し訳ありませんでした

TAB がじっくりやっていた E の考察が終了して、実装してくれた。考察の一部をすでに聞いていたので、ペアプロしながら実装を直していくと通る！！これも正答率が低い問題だったので、すごくうれしい。

反省

序盤はほぼ理想的な動きだったと思う。1 時間であれだけ解けたのはとてもよかった。

中盤・終盤に関しても解くべき問題は解いた気がするのでそこまで悪くはなさそう。ただペナルティが多めで、今回は 7 ペナルティを負ってしまった。1 ペナ 20 分 (だっけ？) なので、1 回提出してペナルティを負うよりは 10 分考えてバグを直したほうが良いので、もう少し慎重になるべきかもしれない。

今後は環境構築含めた練習とかもしていきたいねという感じですね。