2月の目標

最近闇雲に精進していて良くないなと感じたので目標を立てる

2月はグラフ問題を徹底的に行うことにする

カテゴリー別に分類している以下のページの問題を増やしていきたい
ozikot.github.io

No.583 鉄道同好会

問題

No.583 鉄道同好会

解法

オイラーグラフというらしい
UnionFindで特急列車でいける駅の連結を判定
駅から直接いける駅数が奇数の駅が2以下ならYES(一筆書きの始点と終端)

コード

#include <bits/stdc++.h>
using namespace std;

struct UnionFind{
    vector<int> par;
    UnionFind(int N) : par(N){
        for(int i = 0; i < N; i++){
            par[i] = -1;
        }
    }
    int root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry) return;
        else{
            if(par[rx] > par[ry]) swap(rx, ry);
            par[rx] += par[ry];
            par[ry] = rx;
       }
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    void check(){
        for(auto x : par){
            cout << x << " ";
        }
        cout << endl;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    UnionFind UF(n);
    unordered_set<int> st;
    vector<int> G[n];

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        UF.unite(a, b);
        G[a].push_back(b);
        G[b].push_back(a);

        st.insert(a);
        st.insert(b);
    }

    int p = 1e9;
    bool f = true;
    for(auto x : st){
        if(f){
            p = UF.root(x);
            f = false;
        }else{
            if(p == UF.root(x));
            else{
                cout << "NO" << endl;
                return 0;
            }
        }
    }

    int odd_cnt = 0;
    for(int i = 0; i < n; i++){
        if(G[i].size() % 2) odd_cnt += 1;
    }

    if(odd_cnt <= 2){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }

    return 0;
}

おわりに

今日ずっと考えてた
時間が溶けた
もっとすっきり書けそう

dfsの疑問点

経緯

敬遠していた，グラフ問題に対する有効的で基礎的なアルゴリズムであるdfs(depth-first-search)の苦手意識の払拭のため練習を行うことにした

解いた問題

• ABC054 C - One-stroke Path
  頂点1を始点とした全頂点経由経路の数を求める
• ABC075 C - Bridge
  連結なグラフが渡され，辺を消すとグラフ全体が非連結になる辺の数を求める

疑問点

先人のコードを見ながら書いていたら通過済みの頂点の扱いについて悩んだ
以下にACしたコードを載せる

• One-stroke Path

#include <bits/stdc++.h>
using namespace std;

int n, m, ans, vc;
int G[10][10];
bool used[10];

void dfs(int now){
    used[now] = true;
    vc++;
    if(vc == n){
        ans++;
    }
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
    used[now] = false;
    vc--;
    return;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a][b] = true;
        G[b][a] = true;
    }

    dfs(0);

    cout << ans << endl;

    return 0;
}

• Bridge

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int MAX = 55;
int A[MAX], B[MAX];
bool G[MAX][MAX], used[MAX];

void dfs(int now){
    used[now] = true;
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
        G[A[i]][B[i]] = true;
        G[B[i]][A[i]] = true;
    }

    int ans = 0;
    for(int i = 0; i < m; i++){
        G[A[i]][B[i]] = false;
        G[B[i]][A[i]] = false;

        for(int j = 0; j < n; j++){
            used[j] = false;
        }

        dfs(0);

        bool bridge = false;
        for(int j = 0; j < n; j++){
            if(used[j] == false) bridge = true; 
        }
        if(bridge) ans++;

        G[A[i]][B[i]] = true;
        G[B[i]][A[i]] = true;
    }

    cout << ans << endl;

    return 0;
}

疑問が浮かんだのは以下の部分

• One-stroke Path

void dfs(int now){
    used[now] = true;
    vc++;
    if(vc == n){
        ans++;
    }
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
    used[now] = false;
    vc--;
    return;
}

• Bridge

void dfs(int now){
    used[now] = true;
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
}

疑問点はBridgeのdfs関数内で頂点の通過状態をfalseにしないこと
Bridgeはm本の辺をそれぞれ抜いた状態でdfsをする
なんとなくは分かるが言語化ができない…

おわりに

謎が謎を呼ぶ

日記

研究のこと

今自分が担当してる部分が全体のうちのかなりの大部分を占めており，
自分なりに勉強して試行錯誤していたところ，完全上位互換の方がバックに控えてると知り，
あんまり信用されてないのかなと色々推察してしまいました
もう少し頑張ってみようと思います

競プロのこと

全国統一プログラミング王決定戦予選 が先日行われました
可能な限りコンテストに参加することを信条としているので参加したのですが，A問題から躓いてしまいふて寝してしまいました…
何から手をつけていいか分からなくなってしまったので昨日からグラフ問題を勉強しています

おわりに

気分の浮き沈みが激しいので何とかしたいところです

ABC114

所感

再帰関数に手こずった

解法・コード

github.com

おわりに

練習量を増やす

ABC115

結果

コンテストは2018-12-08(土)に開催

3完

所感

コンテスト時はDが異様に難しく感じて解けなかったが今日解説を見て解いた
細分化して問題を解くことに慣れたい

解法・コード

github.com

おわりに

今日は誕生日だった
進路はもう院進で固まってきた
今はまだ弱いけど今年中に水色になりたいな

最近読んだ本

読んだ本

右上から時計回りに

• 余命10年 [小坂流加] 358ページ
• 終電の神様 [阿川大樹] 320ページ
• あした世界が終わるとしても [櫻木優平] 176ページ
• 私は存在が空気 [中田永一] 291ページ

読書を始めたきっかけ

Twitterにてツイートの文章を考えるときに、自分の語彙力不足を痛感したから

感想

余命10年

余命10年と宣告された主人公の恋愛模様が描かれた物語
自分は生涯独身なのでこういう話は分からないと思ったが、父親の立場になって考えると涙が止まらなかった
娘が余命10年と知ったら，親としてどのように接すれば良いのだろうか

終電の神様

終電を逃した人々の物語　短編集
読みやすかった

あした世界が終わるとしても

SF
短い、読みやすかった

私は存在が空気

様々な能力者の物語　短編集
ジャンプしたら自分が行ったことのある地点に瞬間移動できる能力者が出てくる　羨ましい

おわりに

本読むのタノシイ！！！