予鈴

競プロとか備忘録とか…

【随時更新】 最近解いた復習(復讐)したい問題まとめ

完全備忘録です。

C. Eugene and an array

難しいし、嫌いなジャンル。ちゃんと定義した変数通りに従ってやるべき。 提出

 

C. Dreamoon Likes Coloring

構築の貪欲。まず判定問題に帰着したあとに条件を絞って、後ろから貪欲に取る。 提出

A - Sorted Arrays

初見で解けなかった。これきらい。きちんと証明をして書きましょう。

A - 梱包できるかな?

これ と これ は別物です。

英論をコピペするときに改行を取り除くAppを作った

英語の論文を読むとき、よくGoogle翻訳やみらい翻訳を利用するんですが、改行コードのせいでうまく翻訳できないことがあります。

f:id:yebityon:20200307154102p:plain

改行を取り除かずに翻訳

f:id:yebityon:20200307154109p:plain

改行を取り除いて翻訳した場合

これぐらい精度が変わります。

毎回手動で改行を取り除くのは手間なので、Clip Boardにコピーしたとき自動で改行を取り除くmenu bar Appを作りました。

github.com

機能

menu bar のアイコンが🍝のときは、自動で改行コードを取り除きます。

menu bar のアイコンが🍽のときは、何も行いません。

Pasterが起動できるかどうかは、menu barのアイコンをクリックすることでも確認できます。

ダウンロード 

上記のページから、zip形式でダウンロードしてください。Paster/App内にあります。

githubreleaseのページに公開しました.

(おそらく正しい配布方法ではないのでよりわかりやすい形式での配布を検討中です)

これからやること

まともな制作物をgithubで公開することが初めて&Cocoa App 初心者なので、かなり不安があります。

例えば以下の点です。

・テストをしていない。

・RxSwiftを使って実装していますが、理解が100%ではありません。実装に不備や問題があるかもしれません。

・(一般的に)正しい配布の方法なのかわかりません。

・ハイフネーションの削除機能の追加、改行コードを取り除くアルゴの改良

 

どのようなご意見でも構いません。お気づきの点があればissueでもPRでおどのよう形でも構いませんので、ブログまたは Twitter @yebis7sまでお願いします。

 

【随時更新】EDPCまとめ

概要

解いたEDPCの問題を一言のコメントとともに貼っていきます。

感想+解答

A - Frog 1

典型。類題がたくさんある気がする。解答

B - Frog 2

これ好き。 最短経路問題。 解答

C - Vacation

典型。いつものやつ。 解答

D - Knapsack 1

典型。いつものやつ。工夫すれば一次元で解けます。 解答

E - Knapsack 2

典型。いつものやつ。 解答

F - LCS

学びがありました。復元の方法は定期的に忘れるので復習していきたい。 解答

G-Longest Path

これ好き。有向辺に着目すると解ける。今度解き直したい。 解答

H - Grid 1

典型。高校数学で解こうとすると重複するので工夫 解答

I - Coins

epsで挟んだらWA出たけどなんで… 解答 

N-Slimes

かなり好き。mergeしていくのは辛いのでsplitしていく。 解答

P-Independent Set

典型。木なので好き 解答

Q-Flowers

これどこがDPなのわからない。 解答

S-Digit Sum

桁DP. 基本的な問題だが手こずった, 解答

V-Subtree

全方位木DP。 難しかった。解説記事を後で書きます 解答

X-Towers

優先順位付きDPというらしい。もう一度解き直したい。学びがありました。 解答

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;
}