AtCoder ABC315 C - Flavors: 解き方あれこれ(C, Python)

良く分からない解き方(sparse table)をしたついでに思いついた解法と実装と実装練習。

解説解法

• 各味毎で一番おいしい数値を取り出し、それらをソートしてパターン1の最大のおいしさを得ます
• 各味内で降順ソートして[0] + [1]//2で最大のおいしさを得ます

時間計算量はソートがネックになり$O(NlogN)$です。

実装(Python)

from collections import defaultdict
ans = -1
n = int(input())
taste = defaultdict(list) # taste[i] = 味iのおいしさリスト
for _ in range(n):
    f, s = map(int, input().split())
    taste[f].append(s)
maxs = []
for key in taste.keys():
    taste[key].sort(reverse=True) # 各味をソート
    maxs.append(taste[key][0]) # 各味の最大のおいしさを入れる
# パターン1:異なる味
maxs.sort(reverse=True)
if len(maxs) >= 2: ans = max(ans, maxs[0] + maxs[1])
# パターン2:同じ味
for key in taste.keys():
    if len(taste[key]) < 2: continue # 1つしかないならNG
    ans = max(ans, taste[key][0] + taste[key][1] // 2)
print(ans)

ソートしてi-1,iを比較

$(f,s)$で読み込んだリストをソートすると味毎にかたまり、各味は昇順に並びます。そこで、今と違う味の最大のおいしさを覚えておきます。また、今の味の最大のおいしさを覚えておきます。

• 味変した場合、今と違う味の最大のおいしさを更新します。
• 味変していない場合、1つ前の要素と比較すれば同じ味の式です。各味の最後で、f[i-1]//2 + f[i]はその味の最大のおいしさの組み合わせになります。
• いずれにしても、今のおいしさ + 今と違う味の最大のおいしさは最大のおいしさになる候補です。

時間計算量はソートがネックになり$O(NlogN)$です。

実装(Python)

ans = -1
n = int(input())
dat = []
for _ in range(n): dat.append(list(map(int, input().split()))) # [f,s]の配列
dat.sort() # 各味毎に固まり、各味内は昇順のおいしさ
lastF = lastS = 0
maxSOtherF = 0 # そのほかの味で最大のおいしさ
maxSCurrentF = 0 # 今の味で最大のおいしさ
for f, s in dat:
    if lastF != f: # 味が変化した
        maxSOtherF = max(maxSCurrentF, maxSOtherF)
        maxSCurrentF = s # "今の味の最大のおいしさ"をreset
    else: # 味が変化していない場合
        ans = max(ans, lastS // 2 + s) # 同じ味を取る
    ans = max(ans, s + maxSOtherF) # 違う味
    lastF, lastS = f, s
    maxSCurrentF = max(maxSCurrentF, s)
print(ans)

味の数を数えておき、ソートして区間max(segtree)

先にソートをして味毎に連続した状態にします。ある味の長さとある味の開始位置が分かれば、その味の範囲及び、その味以外の範囲が分かります。

区間maxが取れるデータ構造で区間maxクエリを行えば$O(NlogN)$です。

実装(C++)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
pair<int, int> op(pair<int, int> a, pair<int, int> b) { return pair<int, int>{-1, max(a.second, b.second)}; }
pair<int, int> e() { return pair<int, int>{0,0}; }
int main() {
    int ans = -1;
    int n; cin >> n;
    vector<pair<int, int>> dat;
    map<int, int> tasteLen;
    REP(i,n){
        int f, s; cin >> f >> s;
        ++tasteLen[f];
        dat.push_back(pair<int, int>{f, s});
    }
    sort(dat.begin(), dat.end());
    segtree<pair<int, int>, op, e> seg(dat);
    int lastTaste = -1;
    int thisTasteFirst = -1;
    REP(i, n){
        auto &elem = dat.at(i);
        if(elem.first != lastTaste){
            thisTasteFirst = i;
            lastTaste = elem.first;
        }
        // 違う味とのmax
        ans = max(ans, elem.second + seg.prod(0, thisTasteFirst).second);
        ans = max(ans, elem.second + seg.prod(thisTasteFirst + tasteLen.at(elem.first), n).second);
        // 同じ味
        ans = max(ans, elem.second/2 + seg.prod(thisTasteFirst, i).second);
        ans = max(ans, elem.second/2 + seg.prod(i+1, thisTasteFirst + tasteLen.at(elem.first)).second);
    }
    cout << ans << endl;

}

味の数を数えておき、ソートして区間max(sparse table)

区間maxをsprase tableで各クエリを$O(1)$とします。が、sortが必要なので$O(NlogN)$で変わりません。

実装(c++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

template<typename T>
class SparseTable {
    vector<vector<T>> table;
    vector<int> lookup;
    function<T(T, T)> operation;
    function<T()> empty;
public:
    SparseTable(const vector<T> &v, function<T(T, T)> ope, function<T()> e): operation(ope), empty(e) {
        int log_len = 0;
        while((1 << log_len) <= (int)v.size()) ++log_len;
        table = vector<vector<T>>(log_len, vector<T>(1 << log_len));
        lookup = vector<int>((int)v.size() + 1);
        for(int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
        for(int i = 1; i < log_len; i++) {
            for(int j = 0; j + (1 << i) <= (1 << log_len); j++) {
                table[i][j] = operation(table[i-1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
        for(int i = 2; i < (int)lookup.size(); i++) lookup[i] = lookup[i >> 1] + 1;
    }

    inline T queryCloseOpen(const int l, const int r) {
        assert(r-l >= 0);
        if(r-l == 0) return empty();
        int b = lookup[r - l];
        return operation(table[b][l], table[b][r - (1 << b)]);
    }
};

int main() {
    auto op = [] (pair<int, int> a, pair<int, int> b) {return pair<int, int>{-1, max(a.second,b.second)};};
    auto e = [](){return pair<int, int>{0,0};};
    int ans = -1;
    int n; cin >> n;
    vector<pair<int, int>> dat;
    map<int, int> tasteLen;
    REP(i,n){
        int f, s; cin >> f >> s;
        ++tasteLen[f];
        dat.push_back(pair<int, int>{f, s});
    }
    sort(dat.begin(), dat.end());
    SparseTable<pair<int, int>> seg(dat, op, e);
    int lastTaste = -1;
    int thisTasteFirst = -1;
    REP(i, n){
        auto &elem = dat.at(i);
        if(elem.first != lastTaste){
            thisTasteFirst = i;
            lastTaste = elem.first;
        }
        // 違う味とのmax
        ans = max(ans, elem.second + seg.queryCloseOpen(0, thisTasteFirst).second);
        ans = max(ans, elem.second + seg.queryCloseOpen(thisTasteFirst + tasteLen.at(elem.first), n).second);
        // 同じ味
        ans = max(ans, elem.second/2 + seg.queryCloseOpen(thisTasteFirst, i).second);
        ans = max(ans, elem.second/2 + seg.queryCloseOpen(i+1, thisTasteFirst + tasteLen.at(elem.first)).second);
    }
    cout << ans << endl;

}