Codeforces Good Bye 2016 C. New Year and Rating

問題

codeforces.com

考察

折れ線グラフを書いてみるとわかりやすいです。
なるべくレートを高くしたいので、div2の一番高い状態でのレートが1899になると良さそうです。
その状態で、div1では1900を下回らないようにする必要があります。

これを実現するためには、初期値を決定してゆく(狭めてゆく)方法が簡単です。

Impossible、Infinityなケースとして、

  • div1のレートがdiv2のレートを下回っている
  • div1の変動しかない

という2種類があるので、初期値は[-INF, +INF]とし、以下のような更新を行います。
(最初と比較しx変わった後に)

  • div1である: 左端をmax(左端, 1900 - x)
  • div2である: 右端をmin(右端, 1899 - x)

このような更新をし、「左端 <= 右端」であり、かつ「右端 != INF」であれば題意を満たします。

最後に右端に変動を加え、最終的なレートを出力すればACです。

サンプル

最初のサンプルで見てみると、以下のように範囲が狭まります。

[-INF, INF]
[1900, INF] ... acc:0, 最初はdiv1である
[1900, 1906] ... acc:-7, div2になった
[1900, 1901] ... acc:-2, div2
[1900, 1901] ... acc:+6, 最終的なdivはわからないので放置

1901が右端なので、これに+6をし、1907が答えです。

コード

int main() {
    int n;
    cin >> n;

    int acc = 0;
    int mi = -INF, mx = INF;
    rep(i, n) {
        int c, d;
        cin >> c >> d;

        if(d == 1)
            chmax(mi, 1900 - acc);
        else
            chmin(mx, 1899 - acc);

        acc += c;
    }

    if(mi > mx)
        cout << "Impossible" << endl;
    else if(mx == INF)
        cout << "Infinity" << endl;
    else
        cout << mx + acc << endl;
    
    return 0;
}

感想

最終的にかなりシンプルになる、考察重視な問題でした。
パッと浮かぶようになりたいです。

Codeforces Round #389 (Div. 2) D. Santa Claus and a Palindrome

問題

codeforces.com

考察

スコアが付いている幾つかの文字列を組み合わせ、回文となる文字列の中で最大のスコアを算出する問題です。

全ての文字列は同じ長さなので、これらで回文を作るのは以下の2パターンに分けられます。

  • ABA'型
  • AA'型

ここで、AとA'は鏡写しの関係です。
また、Bはそれ自身が回文です。
要は真ん中があるかどうかです。

これらをはじめとし、左右に1つずつ鏡写しのペアをくっつけていけば回文が出来上がります。

スコアを最大にする

各文字列は真ん中以外は必ず2つペアで用いるので、「2つの文字列のスコアを足して正なら答えに加え、それ以外なら無視する」という貪欲で最大のスコアが求まります。
また、小さなスコアの文字列を温存する必要もないため、大きい順に使うことができます。

たとえば、aabのスコア群が[5, 3, -5]、bbaのスコア群が[1, -2, -3, -3]であれば、[5, 1], [3, -2]の2つを答えに組み込むことができます。

真ん中

ただし、真ん中がある場合は、真ん中に置く場合と置かない場合で分岐をする必要があります。
たとえば、aaaのスコア群が[5, 3, 1, -4, -5]という場合、以下の2つの可能性があります。

真ん中あり: 5 + [3, 1]
真ん中なし: [5, 3]

スコアの計算

「今までに真ん中に置いたことがあるか?」ということをメモしておくDPで計算できます。
今回の場合は単純な貪欲なので、「真ん中に置いていない状態での最大スコア」「真ん中に置いたことのある状態での最大スコア」をそれぞれ記録し、「真ん中なし->真ん中なし」「真ん中なし->真ん中あり」「真ん中あり->真ん中あり」の3パターンで最大を順次記録してゆけば良いです。

実装上の注意点

「aaa」と「abb・bba」は区別する必要があるため、それぞれの文字列で回文かどうかを判定し、適したスコアの算出方法を使う必要があります。
また、普通にループをすると「abbでも処理をし、bbaでも処理をした」ということになるので、「abbを処理した後はbbaをスキップする」というような対処が必要です。

コード

int main() {
    int k, n;
    cin >> k >> n;
    unordered_map<string, vi> nums;
    rep(i, k) {
        string s1;
        int a;
        cin >> s1 >> a;
        nums[s1].push_back(a);
    }

    unordered_map<string, bool> used;
    int ans_no_center = 0;
    int ans_center = 0;

    tr(it, nums) {
        string s = it->first;
        vi que = it->second;
        sort(all(que), greater<int>());

        if(used[s])
            continue;

        // check - palindrome
        bool palin = true;
        rep(i, n / 2) {
            if(s[i] != s[n-1-i]) {
                palin = false;
                break;
            }
        }

        // whether centerize
        int nc = 0, c = 0;
        if(palin) {
            rep(i, que.size()-1) {
                if(que[i] + que[i+1] > 0)
                    nc += que[i] + que[i+1];
                i++;
            }

            c = que[0];
            REP(i, 1, que.size()-1) {
                if(que[i] + que[i+1] > 0)
                    c += que[i] + que[i+1];
                i++;
            }
        }
        else {
            string pal = s;
            reverse(all(pal));
            if(!nums[pal].empty()) {
                used[pal] = true;

                vi que2 = nums[pal];
                sort(all(que2), greater<int>());

                int que_size = min(que.size(), que2.size());
                rep(i, que_size) {
                    if(que[i] + que2[i] > 0)
                        nc += que[i] + que2[i];
                }
            }
        }

        chmax(ans_center,
              max(ans_no_center + c, ans_center + nc)
        );
        ans_no_center += nc;
        used[s] = true;
    }

    cout << max(ans_center, ans_no_center) << endl;
    
    return 0;
}

感想

vectorなのに名前がqueになっているのはご愛嬌(priority_queueを使おうかと思っていましたが、vectorを逐次ソートした方が楽だったため)

Codeforces Round #388 (Div. 2) D. Leaving Auction

問題

codeforces.com

考察

人が消えるオークションをする問題です。
注意点として、間の人が消えてある人が連続したら、その場合は圧縮されて落札可能な最も安い値段になります。

参加者の数もクエリの数も 2 * 10^{5}と多いですが、 除外する参加者の数が最大 2 * 10^{5}なので、比較的シンプルな方法で間に合います。

条件

  • 人が指定された時、まとめて除外できる
  • 残っている人の中で、最大の落札価格を出した人がわかる
  • 最大の落札価格を出した人の価格一覧と、その次の人の価格一覧がわかる
    • これは間の人が消えていた場合に対処するためです

これらを満たせば良いので、([その人の最大価格], [その人の価格一覧]) を登場した人の分だけ持ち、二分木で大きい方が上に来るように持てばよいです。
C++だと、mapのソート順を変えるとうまくいきます。

また、同じ価格を出す人はいないので、価格から人を決定することができます。

手順

  • 前述のデータを作る( O(n)
  • クエリの処理( O(q)
    • 指定された人を消す( O(k * logn)
    • 最大の落札価格の人(A)、次の人(B)を取り出す( O(1)
    • Bの最大価格を上回るAの価格を二分探索して決める( O(logn)
    • 出力
    • 消された人を戻す( O(k * logn)

残っている人がいない場合や1人しか残っていない場合は分ける必要がありますが、 簡単に処理できます。

全体として O(q * logn+ k * logn)程度で処理ができ、間に合わせることができます。

注意

方針としては上記で良いですが、これだとTLEを食らって間に合いませんでした。

そこで、
set<([その人の最大価格], [その人の番号])> (大きい順)
vector[その人の番号] = [その人の価格一覧]
とデータを分けると上手く行ってくれました。
復元処理で時間がかかったのでしょうか。

また、cin/coutでも通りましたが、危ういのでscanf/printfにした方が無難です。

コード

int main() {
    int n;
    cin >> n;

    unordered_map<int, int> bid_num;
    vi mx_bid(n, 0);
    vvi tmp(n);
    set<pii, greater<pii>> member;
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        --a;
        tmp[a].push_back(b);
        bid_num[b] = a;
        chmax(mx_bid[a], b);
    }

    rep(i, n) {
        if (!tmp[i].empty()){
            member.insert(mp(mx_bid[i], i));
        }
    }

    int q;
    cin >> q;
    while(q--) {
        int k;
        cin >> k;

        vi remove_list(k);
        rep(i, k) {
            int l;
            cin >> l;
            --l;
            remove_list[i] = l;
        }

        // remove
        tr(it, remove_list) {
            int bid = mx_bid[*it];
            member.erase(mp(bid, *it));
        }

        // check
        if(member.empty()) {
            cout << "0 0" << endl;
        }
        else if(member.size() == 1) {
            pii res = *member.begin();
            cout << res.second + 1 << " " << tmp[res.second][0] << endl;
        }
        else {
            auto res1 = *member.begin();
            auto res2 = *(++member.begin());
            int mx = tmp[res2.second].back();
            int t = *lower_bound(all(tmp[res1.second]), mx);
            cout << res1.second + 1 << " " << t << endl;
        }

        // back
        tr(it, remove_list) {
            if(!tmp[*it].empty())
                member.insert(mp(mx_bid[*it], *it));
        }
    }

    return 0;
}

感想

コードが汚くてゴリ押しした感がありますが、通ったので良しとします。

Codeforces Round #383 (Div. 2) D. Arpa's weak amphitheater and Mehrdad's valuable Hoses

問題

Problem - D - Codeforces

考察

問題を要約すると、「あるグループから"全員"・"1人"・"0人"のいずれかを選んでいったとき、重さがwを超えないbの合計値の最大を求めよ」となります。

まず、グループを判定するのはUnionFindで行えます(rootが同じなら同じグループ)。
各グループの合計重さ・美しさや構成員が判明したら、それを使って「グループごとに」DPを回せば答えが求まります。

DP票は2つ用意して交互に埋めてゆきます。
グループごとに回して交互に使うことで、同じグループの人が最大1回しか使われないようにすることができます。
また、合計は特殊な値として更新処理に加えてあげます。

コード

struct UnionFind {
    vector<int> data;

    UnionFind(int size) : data(size, -1) {}

    bool unionSet(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }

    bool findSet(int x, int y) {
        return root(x) == root(y);
    }

    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }

    int size(int x) {
        return -data[root(x)];
    }
};

int main() {
    int n, m, mxw;
    cin >> n >> m >> mxw;

    vi w(n), b(n);
    rep(i, n)
        cin >> w[i];
    rep(i, n)
        cin >> b[i];

    UnionFind uf(n);
    rep(i, m) {
        int t1, t2;
        cin >> t1 >> t2;
        t1--;
        t2--;
        uf.unionSet(t1, t2);
    }

    vi dpw(n, 0), dpb(n, 0);
    map<int, vi> _group;
    rep(i, n) {
        int r = uf.root(i);
        dpw[r] += w[i];
        dpb[r] += b[i];
        _group[r].push_back(i);
    }
    vvi group;
    vector<pii> grp;
    tr(it, _group) {
        group.push_back(it->second);
        grp.push_back(mp(dpw[it->first], dpb[it->first]));
    }

    vvi memow(2, vi(mxw + 10, 0));
    vi* now = &memow[0];
    vi* next = &memow[1];
    rep(i, group.size()) {
        fill(all(*next), -1);
        rep(j, mxw + 5) {
            chmax((*next)[j], (*now)[j]);

            int no = (*now)[j];
            if(j + grp[i].first <= mxw) {
                chmax((*next)[j + grp[i].first], no + grp[i].second);
            }
            tr(it, group[i]) {
                if(j + w[*it] <= mxw) {
                    chmax((*next)[j + w[*it]], no + b[*it]);
                }
            }
        }
        swap(now, next);
    }

    int ans = 0;
    rep(i, mxw+1)
        chmax(ans, (*now)[i]);
    cout << ans << endl;
    
    return 0;
}

感想

グループ化の前処理をすることで(ほぼ)普通のDPとして扱えるようになるのは面白いなと思いました。あとタイトルが長いです。

Codeforces Round #383 (Div. 2) C. Arpa's loud Owf and Mehrdad's evil plan

問題

Problem - C - Codeforces

考察

色々と試して見ると、まず「輪っかにならない長さ2以上の数列」ができるとアウトになることがわかります。
また、輪っかの長さが偶数ならその半分の長さで済み、奇数ならその長さが必要なこともわかります。

1つの問題中に複数の輪っかが同時に出るので、それらを全て満たす長さ(それぞれ必要な長さのlcm)を取れば良いです。

輪っかになっているかどうかはdfsを2周すると求めることができます。
また、輪っかの長さはUnionFindを使うと簡単に求まります(dfsでまとめてやってもOKだと思います)。

コード

struct UnionFind {
    vector<int> data;

    UnionFind(int size) : data(size, -1) {}

    bool unionSet(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }

    bool findSet(int x, int y) {
        return root(x) == root(y);
    }

    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }

    int size(int x) {
        return -data[root(x)];
    }
};

vi d(110, -1);
vvi graph;

void dfs(int v) {
    if (d[v] == -1) {
        d[v] = 0;
    } else if (d[v] == 0) {
        d[v] = 1;
    } else if (d[v] == 1) {
        return;
    }

    tr(it, graph[v]) {
        dfs(*it);
    }
}

ll gcd(ll a, ll b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll m, ll n) {
    if ((0 == m) || (0 == n))
        return 0;

    return ((m / gcd(m, n)) * n);
}

int main() {
    int n;
    cin >> n;

    graph.resize(n);
    d.resize(n);

    UnionFind uf(n);
    rep(i, n) {
        int t;
        cin >> t;
        t--;
        uf.unionSet(i, t);
        graph[i].push_back(t);
    }

    rep(i, n) {
        fill(all(d), -1);
        dfs(i);
        rep(j, n) {
            if (d[j] == 0) {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    ll ans = 1;
    rep(i, n) {
        int t = uf.size(i);
        if (t == 1 || t == 2) {
        } else {
            if (t % 2 == 0)
                ans = lcm(ans, t / 2);
            else
                ans = lcm(ans, t);
        }
    }

    cout << ans << endl;

    return 0;
}

感想

罠は無いですがタイトルが長いです。

Codeforces Round #383 (Div. 2) B. Arpa’s obvious problem and Mehrdad’s terrible solution

問題

Problem - B - Codeforces

考察

xorを各ペアに対して取っていく問題ですが、普通にやると間に合いません。
そこで、A xor A = 0であることを利用し、 A xor B = xの両辺にxor BをかけるとA = B xor xにすることができます。

事前にそれぞれ値の個数を算出しておくことで、前から順番に計算することができO(n)で答えが求まります。
処理方法は色々ありますが、私の場合は全てのペアで求めて最後に2で割りました。

が、底意地の悪いことにx=0が制約に入っているので、この時だけ「自分自身とのペア」を除いてあげないといけません。
また、答えはintに収まらないのでlong longにする必要があります。

↓のコードではx=0は完全に別処理にしていますが、x=0なら(a-1)*aとして逐次処理をすることでn=1の分岐も要らず、もっと綺麗に書けます。

コード

int main() {
    int n, x;
    cin >> n >> x;

    if(n == 1) {
        cout << 0 << endl;
        return 0;
    }

    map<int, int> s_nums;
    rep(i, n) {
        int t;
        cin >> t;
        s_nums[t]++;
    }

    if(x == 0) {
        ll a = 0;
        tr(it, s_nums)
            a += (ll)it->second * (it->second-1);
        cout << a / 2 << endl;
        return 0;
    }

    ll ans = 0;
    tr(it, s_nums) {
        int t = x ^ it->first;
        ans += (ll)it->second * s_nums[t];
    }

    cout << ans / 2 << endl;
    return 0;
}

感想

罠が多い……。あとタイトルが長い……。

Codeforces Round #383 (Div. 2) A. Arpa’s hard exam and Mehrdad’s naive cheat

問題

Problem - A - Codeforces

考察

 1378^{n}というトンデモ数字が出てきて面食らいますが、 結局一番下の桁だけが必要なことに着目します。

...8 * ...8 * ...8 という繰り返しなので、最後の桁はn=1で8、n=2で88=64なので4、n=3で84=32なので2、n=4で6、n=5で8...となって循環します。

というわけで、n mod 4を取って対応するものを出力すれば良いです。

が、底意地の悪いことにn=0もケースに入っているので、この時だけ1を出してあげないとHackされます。

コード

int main() {
    int n;
    cin >> n;
    if(n == 0) {
        cout << 1 << endl;
        return 0;
    }

    int t = n % 4;
    int res = 0;
    if(t == 1)
        res = 8;
    else if(t == 2)
        res = 4;
    else if(t == 3)
        res = 2;
    else
        res = 6;

    cout << res << endl;

    return 0;
}

感想

A問題は制約を読み飛ばしちゃいますよね。