アルゴリズムとデータ構造の練習問題ログ




# <a id="index" href="#index">目次</a>
* [1.はじめに](#section1)
  - 自己紹介
  - 今回のテーマ
* [2.サイトで何問かアルゴリズム系の実装の練習をしました](#section2)
* [3.感想](#section3)

## <a id="section1" href="#section1">1.はじめに</a>  

### 自己紹介
こんにちは。sgswといいます。

今大学生で、好きな言語はPythonです。
![Python](https://www.python.org/static/img/python-logo@2x.png)
[公式サイトはこちら(外部サイトに飛びます)](https://www.python.org)

### 今回のテーマ
今日は、最近のところ[こちらのサイト](https://cp-algorithms.com)に書かれている内容を理解し、内容をPythonに翻訳したりして、アルゴリズムとデータ構造の勉強＆復習をしていましたが、~~読むだけで飽きてきたので~~実際に問題を解きたくなったのでサイトで練習をしました。
その時にやったもののうち、特に面白かった問題のコードの記録を残しておきたいと思います。

## <a id="section2" href="#section2">2.サイトで何問かアルゴリズム系の実装の練習をしました</a>  

問題は、CodeForcesというサイトから適当に見つけてきました。

####(1) D. Firecrackers

C++だと実装が簡単ですね。Pythonにはmultisetに対応するものがないので、どうやってやるのか?

```C++

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define rep(i,n) for (int (i) = 0; (i) < n; (i)++)
using P = pair<int,int>;
void slv(){
    int n,m,rob,cop;
    cin>>n>>m>>rob>>cop;
    multiset<int> S;
    rep(i,m){int x;cin>>x;S.insert(x);}
    int ans = 0;
    if (rob > cop){
        int new_rob = n + 1 - rob;
        int new_cop = n + 1 - cop;
        rob = new_rob;
        cop = new_cop;
    }
    assert(1 <=rob && rob < cop && cop <= n);
    int chance = min(cop - rob - 1,m);
    vector<int> V(chance);
    rep(i,chance){V[i] = cop - 1 - i;}
    reverse(V.begin(),V.end());
    for (auto e: V){
        if  (S.lower_bound(e) == S.begin()){continue;}
        auto itr = S.lower_bound(e);
        itr--;
        ans++;
        S.erase(itr);
    }
    cout << ans << endl;
    return;

}
signed main(){
    int t;cin>>t;
    while(t--)slv();
    return 0;
}

```

####(2)F. Full Turn

平行で同じ向きでないベクトルペアの個数を数える、ということは分かりましたが、そこからの実装が迷走して苦労しました。

```C++

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define rep(i,n) for (int (i) = 0; (i) < n; (i)++)

using P = pair<int,int>;


int gcd(int a, int b){return (b == 0) ? a : gcd(b, a % b);}

template<class T>
class dict{
    public:
        map<T,int> memo;
    void add(T obj){
        if (memo.find(obj) == memo.end()){memo[obj]++;}
        else{memo[obj]++;}
        return;
    }
    int get(T obj){
        if (memo.find(obj) == memo.end()){return 0;}
        return memo[obj];
    }

    map<T,int> & data(){
        return memo;
    }
};


void slv(){
    int n;cin>>n;
    dict<P> V;
    rep(i,n)
    {int x,y,u,v;
    cin>>x>>y>>u>>v;
    int a,b;
    a = u - x,b = v - y;
    int g = gcd(a,b);
    if (g < 0){g *= -1;}
    a /= g;b /= g;
    P key = P{a,b};
    V.add(key);
    }
    int res = 0;
    for (auto [elem,v] :V.data()){
        auto [a,b] = elem;
        P opp_elem = P{-a,-b};
        res += V.get(elem)*V.get(opp_elem);
    }
    res /= 2;
    cout << res << endl;
    return;

}

signed main(){
    int t;cin>>t;
    while(t--) {slv();}
    return 0;
}
```
####(3) D.program

インデックスの操作で混乱して大変でした。

```python


INF = 1 << 64


def slv():
    n, m = map(int, input().split())
    s = input()
    querys = [tuple(map(int, input().split())) for i in range(m)]
    dpr = [(0, 0) for i in range(n + 1)]
    dpl = [(0, 0) for i in range(n + 1)]
    dps = [0 for i in range(n + 1)]
    for i in range(n - 1, -1, -1):
        M, m = dpr[i + 1]
        if s[i] == "+":
            dpr[i] = (M + 1, min(m + 1, 0))
        else:
            dpr[i] = (max(M - 1, 0), m - 1)

    tot = 0

    for i in range(1, n + 1):
        if s[i - 1] == "+":
            tot += 1
        else:
            tot -= 1
        tmpM, tmpm = max(dpl[i - 1][0], tot), min(dpl[i - 1][1], tot)
        dpl[i] = (tmpM, tmpm)
        dps[i] = tot

    for l, r in querys:
        lM, lm = dpl[l - 1]
        rM, rm = dpr[r]

        m = min(lm, dps[l - 1] + rm)
        M = max(lM, dps[l - 1] + rM)
        # print((lM,lm),dps[l - 1],(rM,rm))
        # print(l, r, (m, M))
        if m <= 0 <= M:
            print(M - m + 1)
        else:
            print(M - m + 2)
    return


def main():
    T = int(input())
    for _ in range(T):
        slv()
    return


if __name__ == "__main__":
    main()

```

####(4) C.Fence Repainting

面白かったです！でも少し実装がめんどくさかった。

```python

from collections import defaultdict
T = int(input())


def array(f):
    return list(map(f, input().split()))


def solver():
    n, m = map(int, input().split())  # plank = n,painter = m
    bef = array(int)
    aft = array(int)
    painter = array(int)
    painter_color = defaultdict(list)
    painter_left = [0]*(n + 1)

    for i, c in enumerate(painter):
        painter_left[c] += 1

    #differ_array = []

    for i in range(n):
        if bef[i] != aft[i]:
            if painter_left[aft[i]] == 0:
                print("NO")
                return
            painter_left[aft[i]] -= 1
            painter_color[aft[i]].append(i)
            #differ_array.append((i,bef[i],aft[i]))

    if all(painter[-1] != elem for elem in aft):
        print("NO")
        return

    print("YES")

    const_idx = -1
    res_array = []
    for i in range(1, m + 1):
        color = painter[-i]
        if i == 1:
            for j in range(n):
                if bef[j] != aft[j] and aft[j] == color:
                    const_idx = j
                    break
            if const_idx < 0:
                for j in range(n):
                    if bef[j] == aft[j] and aft[j] == color:
                        const_idx = j
                        break
                    
            assert const_idx >= 0
            res_array.append(const_idx + 1)

            if const_idx in painter_color[color]:
                painter_color[color].remove(const_idx)
            continue

        if painter_color[color]:
            v = painter_color[color].pop()
            res_array.append(v + 1)
            continue

        else:
            res_array.append(const_idx + 1)
    print(*res_array[::-1])
    return


for _ in range(T):
    solver()

```


####(5). Floor and Mod

これは特に面白かったです。

最終的に sum floor(N/i) i = 1...Nを数えることに帰着したのですが、

そのままやるとO(N)で終わらないので、O(N**0.5)に工夫しました。


```python

#import random



def array(f):
    return list(map(f, input().split()))


def floor_sum(X, N):
    #return X//1 + .... X//N
    res = 0
    for i in range(X//N, X + 1):
        if i * i > X:
            for j in range(1, N + 1):
                if X//j >= i:
                    res += X//j
                else:
                    break
            break       
        if i == 0:
            continue
        n = min(X//i, N) - X//(i + 1)
        res += n * i

    return res


# def naive_floor_sum(X, N):
#     return sum(X//i for i in range(1, N + 1))


# def random_checker(T=100):
#     for _ in range(T):
#         x, n = random.randint(1, 100000), random.randint(1, 100000)
#         a = floor_sum(x, n)
#         b = naive_floor_sum(x, n)
#         assert a == b
#     print("OKOK")
#     return


def slv():
    x, y = map(int, input().split())
    ans = 0
    for b in range(1, y + 1):
        if x//(b + 1) >= b - 1:
            ans += b - 1
        else:
            ans += floor_sum(x, y + 1) - floor_sum(x, b)
            break
    print(ans)
    return


def main():
    T = int(input())
    # random_checker()
    for _ in range(T):
        slv()


main()


```
## <a id="section3" href="#section3">3.感想</a>  
何となくこれでいけそうと思っても、そこからの実装方針が立たなかったり、アイデアが浮かんでからの実装力のなさを痛感させられました。
[こちらのサイト](https://cp-algorithms.com)の勉強と合わせて、これからも進めて行きたい感じです。