2020年 7月 7~9日

まえがき

3日間ぐらいブログ書くのさぼってましたにゃにゃんのにゃん

透過した pic.twitter.com/MC5BuhS7VJ
— 瑞々しぃにぼし＠信号を渡るときは手をあげる (@niboshi_wakai) 2020年7月9日

Vim透過しました（簡単)

ふでぺんもぐもぐ！！

健康管理

炭酸おいしい！！おいしい！！もぐもぐ！！

何した

バブみをモグモグした

具体的に

=w=

今日解いた問題

この3日間ぐらいで解いた問題を書くぞ！！書くぞ…

ABC131 E-Friendships

[グラフ,ウニ]

ウニグラフを作った時最短距離が2であるような頂点対は最大化出来る。
それ以下のKは達成出来る

ABC130 E-Common Subsequence

[最長共通部分列的な,動的計画法,DP]

DP[i+1][j+1] := sのi番目までとtのj番目まで見た時の等しい組の数として行けば解けるんじゃないかなって思って、やりました。
ほぼ自力ACです。 modの世界での引き算でバグらせていて悲しかったです。

漸化式は

for(ll si = 0; si <= n; si++){
    for(ll ti = 0; ti <= m; ti++){
        if(ti == 0 || si == 0) {
            dp[si][ti] = 1;
            continue;
        }
        if(s[si-1] == t[ti-1]){
            dp[si][ti] = (dp[si-1][ti] + dp[si][ti-1]);
        } else {
            dp[si][ti] = (dp[si-1][ti] + dp[si][ti-1] - dp[si-1][ti-1]);
        }
    }
}

証明は不明だがこれで行けた
ちな提出コード

ABC131 F- Must Be Rectangular!

[連結,グラフ,数え上げ]

ようは、最終的に点が何個になったかを求めて、それ引く元々の点の数（すなわちn)をすればいい。
ただ、最終的に点がいくつになるのかが難しすぎる。
（さすがは青diffと言ったところか)

一つの点に対して一つの辺を作る。というところが何だそれ。って感じな新しい発想だった。
つながる頂点の組を見つけたら、使うXの座標,Yの座標の数の積を答えに足していく。むずすぎだろ。、

#include <bits/stdc++.h>

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}

//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;
const int V = 100100;
vector<int> to[2*V];
bool seen[2*V];
vector<int> cnt(2);
void dfs(int v){
    if(seen[v]) return;
    if(v < V) cnt[0]++;
    else cnt[1]++;
    seen[v] = true;
    for(int u: to[v]){
        dfs(u);
    }
    return ;
}
int main()
{
    int n;
    cin >> n;
    rep(i,n){
        int x, y;
        cin >> x >> y;
        y += V;
        to[x].push_back(y);
        to[y].push_back(x);
    }
    ll ans = 0;
    rep(i,2*V){
        if(seen[i]) continue;
        cnt = vector<int> (2,0);
        dfs(i);
        ans +=(ll) cnt[0] * cnt[1];
    }
    ans -= n;
    cout << ans << endl;

}

あとがき

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)

草体にぼ日記

だらだらと

2020年7月9日　日記