ABC120

UnionFindがわからないなら以下を見ると良いかもしれない。
UnionFindの解説 : B: Union Find - AtCoder Typical Contest 001 | AtCoder

A問題

方針

高橋くんが満足するほどお金を持っているなら C を出力
そうではないなら手持ちのお金 B を一回当たりの料金 A で割った値を出力
言い換えればこれはCとB//Aの小さい方が答え。
つまりmin(C, B//A)したらいい
pythonで書くと楽

#python3 
a, b, c = map( int, input().split() ) 
print( min(b//a,c) )

C++

//C++
#include<iostream>
#include<algorithm>

int main() {
    int a, b, c;
    std::cin >> a >> b >> c;
    std::cout << std::min(b/a ,c) << "\n";
    return 0;
}

B問題：

方針

forで回してi( 1<= i <=100)がAとBの両方を割り切れるならvector等に追加
最後に大きい方からK番目の要素を出力
forを降順で回す、vectorを降順ソートする、要素へのアクセスを調整のどれかをする
forを降順で回したりソートするのは何か違う気がするので、最後のアクセスで調整
何も考えないでfor書いてしまうとi = 0の時にゼロ除算になる
ちょっと問題文で迷った
（コード中の改行がおかしくなる。やたら広いかとか出てくる。）

python

#python 3
a, b, k = map(int,input().split())
ans = []

for i in range(1,min(a,b)+1):
    if a%i ==0 and b%i == 0:
        ans.append(i)

print(ans[-1*k])

C++

//cpp14
#include<iostream>
#include<vector>
#include<algorithm>

int main() {
    int a, b, k;
    std::cin >> a >> b >> k;

    std::vector<int> v;
    auto mv = std::min(a, b);

    for (int i{1}; i <= mv; ++i) {
        if (a%i == 0 &&; b%i == 0)
            v.emplace_back(i);
    }

    std::cout << *(v.rbegin() + k-1) << "\n";

    return 0;
}

C問題：

方針

ぷよぷよ的な落ちモノパズルゲームっぽい問題
文字列Sについてfor回す。文字Siを文字列Sのi番目の文字とする
stackが空か、stackのtopがSiと同じ文字なら、文字を積む
それ以外の場合（＝スタックに要素が1つ以上あり、topがSiと別の文字、つまりは隣合えば消える組み合わせ）
stackのtopとSiには消えてもらうstack.popとi+=1による要素飛ばしで実装
remで消えた文字数をカウント
ひどいコードだったのでpythonのコードを修正。提出してACを確認済み。

蛇足

多分removeのremなんだろうがremainと紛らわしい
countのが良いんじゃないか
ssは、多分lenでも十分早いと思うけれど、何度も関数呼ぶよりも早いのかな、くらいの気持ち
最適化は実測してからしたほうがいい
制約から文字列Sの長さNが10⁵以下だったので、とりあえず2重ループ書いたらそれがTLE
反省してきちんと考えた結果、stackか最小値取る方法を思いつく
最小値は証明とかできなかったのでstackで
解説見る限り、最小値でも良いらしいし、提出したら通った。

python

#python 3

s = input()
n = len(s)
stack = [ s[0] ]
rem = 0

ss = len(stack)

for i in range(1,n):

    if ss==0 or stack[-1] == s[i]:

        stack.append(s[i])
        ss += 1
        continue

    stack.pop()
    ss -= 1
    i+=1
    rem +=2

print(rem)

C++

//cpp14
#include<iostream>
#include<vector>
#include<string>

int main() {

    std::string s;
    std::cin >> s;

    std::vector<char> stack_;
    stack_.reserve(s.size());
    auto count = 0;

    for (const auto&amp;e : s) {
        if (stack_.empty()) {
            stack_.push_back(e);
            continue;
        }           
        if (stack_.back() != e) {
            stack_.pop_back();
            count += 2;
        }
        else {
            stack_.push_back(e);
        }
    }

    std::cout << count << "\n";
    return 0;
}

C++ 別解

//cpp14 別解
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

int main() {
    std::string s;
    std::cin >> s;

    decltype(s.size()) zeros = std::count(s.begin(), s.end(), '0');

    std::cout << 2*std::min(zeros, s.size() - zeros) << "\n";

    return 0;
}

D問題：

方針

グラフの辺を減らすのは難しい
反対から考えて辺を増やしていくことを考える
頂点をグループ化していくと考えるとUnionFindが使える
UnionFindでグループ化した任意のグループが含んでいる頂点の数がわかると答えが出せる

コンテスト中の考えとか

コンテスト中はグラフの分割なんてわからん！で諦めた。
解説によるとグラフから辺を削除するのは確かに難しいらしい。
私でなくてもそうなら、これはとても大事なこと。
最後の答えの値がn*(n-1)//2になることとUnionFindっぽい？とは思った。
入力を配列に入れて逆順でーは思いつかなかった残念。
解説見たら手を出して良い問題だった。多分WAするが
C++もpythonも人のコードを参考に書いたもの
size関数がいることは分かったけど内部に配列一つ持つだけで実装できるとは
全然思いつかないし、実装できる気がしないぞ。未だにちょっとわかってない。

実装概要、多分だけど

size：

任意の木の大きさはその根に入っている
根以外は親のindexを持っている
したがって木の大きさは-par[root(n)]
「-」するのは大きさが負の整数で表現されているため
大きさは常に負。初期値は-1で、増えるケースは大きさ同士の加算のみ
uniteされる2つの木の大きい方の根が大きさを持つ

root：

parの初期値が-1なので、値が負なら自身が根ということでnを返す
それ以外なら経路圧縮しつつ親の値を得て返す
~~再帰難しい~~

__link__：

引数のa,bはrootされていることを前提に実装。
aとbが等しいなら同じグループなのでreturn
size(a)とsize(b)を比較してどちらが根になるべきか判定
一度でも根ではなくなったものは二度と根になることはない
(辺が削除されず追加される一方ということはそういうことだろう)
つまりは根には-1か、それらが加算されてきた負の値が入っているはず
より大きい木が大きさの値を受け継いで、小さい木の根は親を指す

python

# python 3

class dset:
    def __init__(self,n):
        self.par = [-1]*n

    def size(self,n):
        return -self.par[self.root(n)]

    def root(self,n):
        if self.par[n]<0:
            return n
        else:
            self.par[n] = self.root(self.par[n])
            return self.par[n]

    def same(self, a, b):
        return self.root(a) == self.root(b)

    def __link__(self,a,b):
        if a == b:
            return 

        if self.size(a) < self.size(b):
            a, b = b, a
        self.par[a] += self.par[b]
        self.par[b] = a

    def unite(self,a,b):
        self.__link__(
            self.root(a)
            ,self.root(b)
            )

def main():
    n, m = map(int, input().split() ) 

    ins = [ list( map(int,input().split()) ) for i in range(m)  ]

    ds = dset(n)

    ans = [0]*m
    ans[-1] = n*(n-1)//2

    for i in range(m-1,0,-1):
        ans[i-1] = ans[i]
        a,b = ins[i]
        a -= 1
        b -= 1

#        print(ins[i])
       # print( (ds.root(a),ds.root(b)) ) 
        if not ds.same(a,b):
            x = ds.size(a)
            y = ds.size(b)
            #print((x,y))
            ans[i-1] -= x*y
            ds.unite(a,b)

    for e in ans:
        print(e)

if __name__ == '__main__':
    main()

C++

//cpp14

#include<iostream>
#include<vector>
#include<algorithm>

using sll = signed long long;
using ui =  long int;

class disjoint_set {
    std::vector<int> p;

    auto link(int x, int y) {
        //x = find(x);
        //y = find(y);

        if(x==y)
            return false;

        if ( size(x) < size(y) )
            std::swap(x, y);

        p[x] += p[y];
        p[y] = x;
        return true;
    }

public:
    disjoint_set():p{}{}

    disjoint_set(int size_) :
        p{}{
        p.resize(size_, int{-1});
    }

    auto find(int x)
        ->decltype(p)::value_type {
        
        return p[x] < 0 ? 
            x : p[x] = find(p[x]);
    }

    auto same(int x, int y) {
        return
            find(x) == find(y);
    }

    auto unite(int x, int y) {
        this->link(find(x), find(y));
    }

    auto size(int x)
        ->decltype(p)::value_type{
        return -p[ this->find(x) ];
    }

};

int main() {

    int n, m;
    std::cin >> n >> m;

    std::vector< std::pair<int, int> > vp;

    disjoint_set ds{ n };
    vp.resize(m);

    for (int i{}; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;

        vp[i] = std::make_pair(a-1, b-1);
    }

    auto it = std::rbegin(vp);
    auto end_ = std::rend(vp);

    auto ansi = sll{ n } *(n - 1) / 2;

    std::vector<sll> ans{};
    ans.resize(m, 0);
    ans[m - 1] = ansi;

    for (int i{m-1}; i > 0; --i) {
        
        auto a = it->first;
        auto b = it->second;

        ans[i-1] = ans[i];
//     std::cout << " ab " << a+1 << " " << b+1 << "\n";
        if (!ds.same(a, b)) {
            auto x = ds.size(a);
            auto y = ds.size(b);

            ans[i-1] -= x * y;
            ds.unite(a, b);
//         std::cout <<" xy "<< x << " " << y << "\n";
            if (ans[i-1] < 0 )
                ans[i-1] = 0;
        }
        ++it;
    }

    for (auto&amp;e : ans)
        std::cout << e << "\n";
    
    return 0;
}

感想

最近色々だれてきていて、やる気がなくなってきていた
でもやればわかることが増えて、それは面白いので今後もやっていきたい
とりあえず現在の限界は、今回のD問題が解けないくらい
これ以上レートを上げていくということが、このUnionFindを平然と実装できる人達と競争するということなら、現状の能力ではかなり厳しいと感じる

　
残念な失敗が多くて厳しい

DでWA->10^5^2はintでは扱えない
CでTLE->10^5^2は2secで全探索できない
Bは良くわからないがWAしたので別の書き方をしたら通った。良くない
UnionFindの実装に手間取るのが結構いたい

　UnionFindくらい難しいと何も考えずに書けるものでもない。
経路圧縮やランクによる効率化で処理が増えても複雑になっていくのを理解できるか、再帰を考えられるかが大事なんだろう。

　参考にしたUnionFindを書いた人は賢いやり方をしていてなかなかわからなかった。
今回はコンテスト後に復習をかねてもう一度、コンテスト時に用いた言語ではない言語で書きなおしたので、A-Dまでpython3とC++のコードがある。
　今更だけど載せるのってC以上の問題だけで良い気がする。
　書き方も色々試してみる。今回はmarkdown。
コード載せる時に気づいたけどこれは正規の挙動なのか。
コード内でマークダウン効いたり改行でspan出たり何とかならないのかね。
<details>tagの中にdivを入れるのは、展開後の文章にmarkdownを適用するとき。