予鈴

競プロとか備忘録とか…

D - Shortest Path on a Line

問題

atcoder.jp

考えたこと

・愚直に辺をつなぐと間違いなくTLE. 辺を追加するクエリを頂点とみなすか、実は全部辺を考慮する必要がないかのどちらかだと思った。
・任意のL_{i} \leq s < t \leq R_{i}の2頂点s,t間は C_{i}で接続することができる。
・したがって、「辺を追加する」という区間とコストを辞書順かつ昇順にソート済みのクエリについて、以下のように言い換えることができる。

 i番目のQueryに対し、 t \in [L_{i},R_{i}]について
頂点1からのt の最短距離を d_{t}とする。
d_{t} =  min(d_{t}, lb + c_{i}) に更新する。ただし、lb区間内の最小値で、
 lb \leq \forall d_{j} \land j \in[ L_{i} ,R_{i}] を満たす。

・必要になるデータ構造は、区間の最小値取得 + 区間を最小値で更新
・SegmentTreeBeatsというらしいです。すごい。コピーしてきてAC

想定解

想定解のほうが鮮やか(当社比)なのでそれも書きます
・実はすべての (s,t)の辺について考える必要はなく、隣接する2頂点(t,t + 1)間をコスト0で結ぶ辺と, (L_{i},R_{i})を考えるとよい。
・無向辺で接続すると、最短経路問題に帰着できない・・・辺に関わらず出力が常に0になる。
・隣接する2頂点の辺の張り方を工夫する。具体的には v_{i + 1}から v_{i}の有向辺を貼る。すると, C_{i}をうまくすべての区間に伝搬することができる。
・具体的に考える。まず頂点1のコストは0であり、これは明らかに最短経路である。 [1,r]を満たすQueryのうち, Cが最小のものを Q_{m}とする。
・頂点1の最短経路はすでに求まっているため、 [1,r_{m}]内の最短経路は間違いなく  C_{m}または0 になる。
・↑を繰り返すと求まる。これはDIjkstra法と同じ。おそらく、このグラフの最短経路は1に近い方から順に求まっていく。したがって、Queryの区間内に最小値が存在することは無い(多分)
・間違ってそう。問題があればリプください。

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
    Int N,M;
    cin >> N >> M;
    using tp = tuple<Int,Int>;
    vector<vector<tp>>edge(N);
    for(Int v = 0; v + 1 < N; ++v){
        edge[v + 1].emplace_back(v,0LL);
    }
    for(int i = 0; i < M; ++i){
        Int u,v,c;
        cin >> u >> v >> c; --u; --v;
        edge[u].emplace_back(v,c);
    }
    constexpr Int inf = (1LL << 60);
    vector<Int>d(N,inf);

    priority_queue<tp,vector<tp>,greater<>>que;
    que.emplace(0,0);
    d[0] = 0;
    while(not que.empty()) {
        auto p = que.top(); que.pop();
        Int crt,v;
        tie(crt,v) = p;
        if(crt > d[v]) continue;
        for(auto tup : edge[v]){
            Int nv,cost;
            tie(nv,cost) = tup;
            if(cost + crt >= d[nv]) continue;
            d[nv] = cost + crt;
            que.emplace(d[nv],nv);
        }
    }
    cout << (d.back() == inf ? -1 : d.back()) << endl;
}

CF #597 (Div. 2) D. Shichikuji and Power Grid

Solution

・Excluding the building power plant, it is clear that getting MST is answer.
・finding that which power plant is efficient is difficult. (e.g. greedy algo is not correct.like this) also, if we build power plants on  v_aand  v_b, these are not needed to connect each other .
To solve this problem, Let's consider new vertex as building power plant.

 v_{n+1} is new vertex, connecting  v_{n+1} to  v means build power plants at  v with cost  c_{v}.
・Note that we have to build power plants at least one. therefor, getting MST which include new vertex is answer.
・Time complexity is  O(N^2).

#include<bits/stdc++.h>
using namespace std;
using ll = long long
#define int ll
class unionfind {
    vector<int> par, rank, size_;
public:
    unionfind(int n) :par(n), rank(n), size_(n, 1) {
        iota(par.begin(),par.end(), 0);
    }
    int find(int x) {
        if (par[x] == x)return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)return;
        if (rank[x] < rank[y])swap(x, y);
        par[y] = x;
        size_[x] += size_[y];
        if (rank[x] == rank[y])rank[x]++;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return size_[find(x)];
    }
};
auto dis(pair<int,int> t, pair<int,int> u){
    return abs(t.first - u.first) + abs(t.second - u.second);
}
signed main(){
    int N; cin >> N;
    vector<pair<int, int>>pos(N);
    for(auto&  p : pos)
        cin >> p.first  >> p.second;
    vector<int>c(N), k(N);
    for(auto& e : c)  cin >> e;
    for(auto& e : k)  cin >> e;
    vector<vector<pair<int,int>>>edge(N);
    using tp = tuple<int,int,int>;
    vector<tp>g;
    for(int i = 0; i < edge.size(); ++i){
        auto t = pos[i];
        for(int j = 0; j < N; ++j){
            if(i == j)continue;
            auto u = pos[j];
            int cost = dis(t,u)*(k[i] + k[j]);
            edge[i].emplace_back(j,cost);
            g.emplace_back(cost,i,j);
        }
    }
    int over_v = N + 1;
    for(int i = 0; i < N; ++i)
        g.emplace_back(c[i], over_v, i);
    
    sort(g.begin(),g.end());
    auto uf = unionfind((int)g.size() + 10);
    int ans = 0;
    vector<bool>build(N,false);
    vector<pair<int,int>>used_edge;
    for(auto p : g){
        int cost, t,u;
        tie(cost,t,u) = p;
        if(uf.same(t,u)) continue;
        ans += cost;
        uf.unite(t,u);
        if(t == over_v or u == over_v){
            build[(t == over_v ? u : t)] = true;
        } else{
            used_edge.emplace_back(t,u);
        }
    }
    cout << ans << endl;
    cout << count_if(build.begin(),build.end(),[](bool e){ return e;}) << endl;;
    int cb = 0;
    for(int i = 0; i < build.size(); ++i){
        if(build[i]){
            if(cb++) cout << " ";
            cout << i + 1;
        }
    }
    cout << endl;
    cout << used_edge.size() << endl;
    for(auto p : used_edge)
        cout << p.first + 1 << " " << p.second + 1 << endl;

D - 連結 / Connectivity

解き直したら解けなかったので、ここで供養します

問題文

atcoder.jp

解法

頂点 iについて考える. iと鉄道で連結な頂点集合 T,高速道路で連結な頂点集合をHとする.
求めるべき答えは  v  \in T  \cap Hを満たすvの個数である.
頂点集合を構築するにはunionfindを用いればよい.
vの個数を愚直に数え上げるとTLEするので工夫する.
具体的には、頂点 iが属する頂点集合 T Hは一意に定まる.
したがって、これらのT,H をkeyとする連想配列を用いて、数え上げると良い.
ちなみに、下記unionfindはfindで親(集合のID)を返すので、それで管理している.


#include<bits/stdc++.h>
using namespace std;
class unionfind {
    vector<int> par, rank, size_;
public:
    unionfind(int n) :par(n), rank(n), size_(n, 1) {
        iota(par.begin(),par.end(), 0);
    }
    int find(int x) {
        if (par[x] == x)return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)return;
        if (rank[x] < rank[y])swap(x, y);
        par[y] = x;
        size_[x] += size_[y];
        if (rank[x] == rank[y])rank[x]++;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return size_[find(x)];
    }
};

signed main(){
    int N,K,L;
    cin >> N >> K >> L;
    auto t = unionfind(N);
    auto c = unionfind(N);
    for(int i = 0; i < K; ++i){
        int a,b; cin >> a >> b;
        --a,--b;
        t.unite(a,b);
    }
    for(int j = 0; j < L; ++j){
        int a,b; cin >> a >> b;
        --a,--b;
        c.unite(a,b);
    }
    map<pair<int,int>,int>cnt;
    for(int i = 0; i < N; ++i){
        cnt[make_pair(t.find(i), c.find(i))] += 1;
    }
    for(int i = 0; i < N; ++i)
        cout << cnt[make_pair(t.find(i),c.find(i))]<< endl;
}

B - Sports Festival

問題

atcoder.jp
かなり考察したのに解けなかった。悔しいのでここで供養します。

考察

 A_{ij}を使いたいとすると、用いることができるスポーツはj < kを満たすような A_{ik}
ただし、その他の行で何が一番になるか比較するのは計算量的に怪しい(と思う)
・ある A_{ij}に着目してから実験するのはかなり難しい。

正解

最も参加人数の多いスポーツがスポーツ P で、その参加人数が Q 人だとします。当
り前ですが、この段階で、参加人数の最大値が Q の解が得られています。よって、あと考えるべき
は、参加人数の最大値が Q 未満の解です。そして、そのような解において、スポーツ P は必ず実
施されません。なので、Q 未満の解を求めるには、スポーツ P を候補から外した上で、もう一度
同じ問題を解きなおせばよいです

悔しすぎる。単純に、参加者が多いスポーツを候補から外せばいいという事がわかる。
できないと感じながら実装したのが間違いだった & そうなったときに新しい切り口を見つけるのが今後の課題かも。

解答

#include<bits/stdc++.h>
using namespace std;
set<int>S;
int ans = 1e8;
void simulate(vector<vector<int>>&g){
    map<int,int>cnt;
    for(int i = 0; i < g.size(); ++i){
        for(int j = 0; j < g[i].size(); ++j){
            auto crt = g[i][j];
            if(S.find(crt) == S.end()){continue;}
            cnt[crt]++;
            break;
        }
    }
    int maxim = -1, num = -1;
    for(auto itr : cnt)
        if(maxim < itr.second)
            maxim = itr.second, num = itr.first;
    ans = min(ans,maxim);
    S.erase(num);
    if(not S.empty()) simulate(g);
}
int main(){
    int N,M; cin >> N >> M;
    vector<vector<int>>g(N,vector<int>(M));
    for(auto& v : g)
        for(auto&  e: v) cin >> e;
    for(int i = 1; i <= M; ++i){
        S.insert(i);
    }
    simulate(g);
    cout << ans << endl;
}

D - Digits Parade

問題

atcoder.jp
以下では、最も大きな桁を1番目として考えてます。あとこの記事はかなり備忘録寄りになってます

考察

・ひと目みて桁DPだと気づいたよ。すっかり忘れていたのでこのサイトで復習した。
・余りが5である必要があるので、各桁について余りを管理する必要がある。大きい桁から計算するメモ化再帰を考えた。
・メモ配列  memo[ digit ] [ num ] [ mod]digit目の数字をnumにしたとき、13で割った余りが modである場合の数と定義する。このとき、 nmod \,を  nmod + \, 桁の重みの余り \, * \, num \, = mod となる数とすると、更新式は以下の通り。

 memo[ digit ] [ num ] [ mod] +=  \,memo[ digit + 1 ] [ 次の桁の数字  ] [ nmod]

・イメージは、digit桁目にnumを使って余りがmodになるためには、次の桁以降の余りが nmod になっていなければならない。

digit + 1が?ならば0~9を試せば良い。桁の余りの重みも簡単に求めることができる。 10^u = 9 * 10^{u-1} + 10^{u-1}なので、順番に余りを求めていけば良い。コード中のbaseがそれに該当する
提出したコードはこれ
atcoder.jp

・実際は2次元でできる。必要なのは桁とmodだけの情報で良い。上記の提出でもnumはnmodを求める場合のみ用いている。
・上記のコードは関数呼び出し時に桁の数字を決める、下のコードは関数内でいま見ている桁をどうするか決める。
・感覚的にはdigit目の文字が'?'であれば、より多くのnmodを取る事ができる。例えば、digit桁目がn,uでもcmodの値がおなじ場合があるので。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
constexpr int MOD = 1000000007;

signed main(){
    string s; cin >> s;
    int N = s.size();
    auto memo = vectors( N + 2,13,-1LL);
    // 0-index
    vector<int>base(s.size() + 1,0LL);
    base[ N - 1] = 1;
    
    for(int i = N - 2; i >= 0; --i)
        base[i] = (9 * base[i + 1] + base[i + 1]) % 13;
    
    for(int i = 0; i < 13; ++i)
        memo[s.size() - 1][i] = (i <= 9 and (s.back() == '?' or s.back() - '0' == i) ? 1 : 0);
    
    
    function<int(int,int)>solver = [&](int digit,int cmod){
        if( memo[digit][cmod] != -1LL) return memo[digit][cmod];
        memo[digit][cmod] = 0;
        // digit桁目でcmodとなる場合の数を求める。 関数内で次の数字を決める。
        int idx = digit;
        //今見ている桁が'?'のとき、0~9をすべて試す
        if(s[idx] == '?'){
            for(int num = 0; num < 10; ++num){
                int temp =  ( base[digit] * num ) % 13;
                int nmod =  (cmod - temp <= 0 ? cmod - temp + 13 : cmod - temp) % 13;
                memo[digit][cmod] += solver(digit + 1,nmod);
                memo[digit][cmod] %= MOD;
            }
        } else {
            int num = s[idx] - '0';
            int temp =  ( base[digit] * num ) % 13;
            int nmod =  (cmod - temp <= 0 ? cmod - temp + 13 : cmod - temp) % 13;
            memo[digit][cmod] += solver(digit + 1, nmod);
            memo[digit][cmod] %= MOD;
        }
        return (memo[digit][cmod]) % MOD;
    };
    cout << (solver(0,5)) << endl;
}

E - Strings of Impurity

問題

長いので、リンクを踏んでください
atcoder.jp

考察

 sにない文字が tに含まれる場合は明らかに-1
・部分列で構成しなければいけないので、単にtに使う文字が出てくるまでsを増やすのはダメ
・1時間ぐらい考えて二分探索が生える。ここから4時間ぐらい溶かす。

反省点

二分探索で得るべき値は、一つ前の文字より真に大きいindexを持つ c.これは、 cをkeyとする配列で達成することができる。
間違ったアプローチのコードがこれ
各文字ごとに最後に使ったindexを記録しておいて、その値を元に二分探索の範囲を限定する。
そもそも異なる文字のindexが最後に記録したindexより先に来る場合がある。間違ったアプローチは最小値にならない。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
signed main(){
    string s; cin >> s;
    string t; cin >> t;
    vector<vector<int>> pos(26);
    for(int i = 0; i <  s.size(); ++i)
        pos[s[i] - 'a'].push_back(i);
    for(auto c : t)
        if(pos[c-'a'].empty())  return puts("-1") * 0;
    int ans = 0;
    int prevIndex = -1;
    int ssize = s.size();
    for(auto c : t){
        char key = c - 'a';
        auto itr = (upper_bound(pos[key].begin(),pos[key].end(),prevIndex));
        if(itr != pos[key].end()){
            ans +=  *itr - prevIndex;
        } else {
            itr = pos[key].begin();
            ans += ssize - prevIndex + *itr;
        }
        prevIndex = *itr;
    }
    cout << ans << endl;
}

C - Time Gap

問題文

 N都市についての数列 Dが与えられ、これらは都市T_{0}の0時との時差である。
都市T_iT_{j}の時刻の差の最小値をsとするとき、sの最大値を求めよ。
※日本語が崩壊してる気がするので問題文を読むことをおすすめします。

atcoder.jp

解く前に考えていたこと

・読解に少し手間取った。要するに時差が3というのは、0時から考えると3時と21の二つがあるので、どちらを取るべきですか、みたいな問題。

 N\leq 50なので、すべての配置を試すことはできない。D_{i} \leq 12であることに着目する。
2^{23}の全探索を考えたけど間に合わない。(各時差に該当する都市があるかどうか)
Dの中に同じ数がいくつ有るか(0か1か2)のみが重要であることがわかる。
(なぜなら、同一の時差を持つ都市が3つ以上ある場合、同じ時間に属する都市が少なくとも1つ存在する。これらの時差は常に0である。)

・配置の状態を12bitの3進数で表すような方針を立てた。要するにibit目が0,1,2ならiの時差を持つ都市が0,1,2個ある。
2個の場合は i時と i+12時とすれば良い。1つのときは...…結局わかりません?

解説

・↑の方針でも十分に解けた。まず3進数である必要はない。なぜなら、同じ数が2つ以上ある場合、i時i+12時に一つずつ配置するのが必ず最適になる。
・つまり、一つの時間帯の状態は0または1である。さらに、時差 jの数字は決まっているので、2^{23}も状態は必要なく2^{12}個で十分。
ibit目が1ならiに配置し、ibit目が0なら i + 12番目に配置すれば良い。
・0時は高橋くんが使うらしいので初期値1。また,時差12の場合の配置は一通りに決まる。

#include<bits/stdc++.h>
using namespace std;
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
signed main(){
    int N; cin >> N;
    vector<int>v(N);
    for(auto & e : v) cin >> e;
    array<short,13> cnt = {0};
    cnt[0]++;
    for(auto  e : v)cnt[e]++;
    for(auto  e : cnt) if(e >= 3) return puts("0") * 0;
    if(cnt[0] >= 2 or cnt[12] >= 2) return puts("0")* 0;
    int ans = -INF;
    
    for(int bit = 0; bit < (1LL << 12); ++bit){
        vector<int>pos(25,0LL);
        pos[0] = cnt[0];
        pos[12] = cnt[12];
        int tans = INF;
        for(int i = 1; i <= 12; ++i){
            if(cnt[i] == 0) continue;
            if(cnt[i] == 2) pos[i] = pos[24 - i] = 1;
            if(cnt[i] == 1){
                ((bit & (1LL << (i - 1))) >= 1 ? pos[i] : pos[24 - i]) = 1;
            }
        }
        for(int i = 0; i < pos.size(); ++i){
            for(int j = 0; j < pos.size(); ++j){
                if(i != j and pos[i] == 1 and pos[j] == 1)
                    cmin(tans, min(abs(i-j),24 - abs(i-j)));
            }
        }
        if(tans == INF)continue;
        cmax(ans, tans);
    }
    cout << ans << endl;
}