ABC248-Gの包除原理を用いた解き方について

書くためのネタがあまりなかったのですが、更新できてない方が問題なので、とりあえず書きました。

ABC248-Gの包除原理を用いた解答

「以下の自然数における約数の個数の最大値」としたとき、

包除原理による時間計算量/空間計算量の解答例を紹介する。

---

] 相違なる点間のパスの の値がとなるようなパスに含まれる頂点数の総和

と定義する。

すると、答えは以下の式で表せることがわかる。

ここで包除原理を用いると、 を「異なる点間のパスのの値が の倍数となるようなパスに含まれる頂点数の総和」とし

である。

これより、任意の に対して上記で定めた の値を求めることができれば十分。

---

上記の課題を全体でで解決することを考える。

を固定して考える。

このとき、 は「元々のグラフのうち、辺の両端の持つ値がともに で割り切れる辺だけを結合して得られる森において、同一の木に所属する相違なる点間のパス上に存在する点の個数の総和」

と言い換えることができる。

いま、木のうち頂点がつだけから構成されるものは答えに影響を与えないため無視することにすれば、を「元々のグラフのうち辺の両端の持つ値がともにで割り切れる辺の個数」としてABC220F - Distance Sums 2の応用でで求めることができる。

また、の合計は「各辺の両端の持つ値の最大公約数の約数の個数の総和」として抑えることができるため、 前計算によりそれぞれのに対して両端が共にで割り切れる辺の情報を配列に保管しておくことで、全体を通し更新はで行える。

---

これらを整理し、適切な実装を行うと、時間計算量・空間計算量ともにで解くことができる。

[C++による実装例]

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")


#include<bits/stdc++.h>

#define ll long long
#define endl '\n'


/*
    math/DS Template
*/
template <class T = int>T gcd(T a, T b){return (b == 0) ? a : gcd(b, a % b);}
template <class T = int>T extgcd(T a,T b,T &x,T &y){T g = a;x = 1;y = 0;if (b != 0) {g = extgcd(b, a % b, y, x), y -= (a / b) * x;}return g;}
template<class T = int> T invMod(T a,T m){T x,y;if (extgcd(a, m, x, y) == 1) {return (x + m) % m;}else{return -1;}}


const int maxn = 1e5 + 10;
constexpr ll mod = 998244353;
using Pii  = std::pair<int,int>;
using namespace std;


//global variables
vector<vector<int>> divisors(maxn), graph(maxn);
vector<ll> subsize(maxn,1), dist(maxn), total_weights(maxn);
vector<bool> visited(maxn, false);
vector<vector<Pii>> connected_edges(maxn);


void divisor_init(){
    // divisor setup
    for (int d = 1; d < maxn; d++){
        for (int j = d; j < maxn; j += d){
            divisors[j].emplace_back(d);
        }
    }
    return;
}


ll distance_sums(const vector<vector<int>> & g, const vector<int> & possible_roots){
    //ref: https://atcoder.jp/contests/abc220/editorial/2693
    ll total_distance = 0;
    //first dfs
    for (auto & root : possible_roots){
        if (visited[root]){continue;}
        function<void(int, int, int)> dfs = [&](int p, int u, int d){
            visited[u] = true;
            dist[root] += (d == 0 ? d : d + 1);
            for (auto v : g[u]){
                if (v == p){continue;}
                dfs(u, v, d + 1);
                subsize[u] += subsize[v];
            }
        }; 
        dfs(-1, root, 0);
    }
    //second dfs
    for (auto & root : possible_roots){
        if (!visited[root]){continue;}
        int subsizetree_size = subsize[root];
        function<void(int, int)> dfs1 = [&](int p, int u){
            total_distance += dist[u];
            for (auto v : g[u]){
                if (v == p){continue;}
             dist[v] = dist[u] - 2 * subsize[v] + subsizetree_size;
                dfs1(u, v);
            }
            //reset all trace to reuse global variables
            subsize[u] = 1; dist[u] = 0;
            visited[u] = false;
        };
        dfs1(-1, root);
    }
    // counted twice
    return (total_distance / 2) % mod;
}


void slv(){
    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++){cin >> A[i];}
    for (int i = 0; i < N - 1; i++){
        int u,v;
        cin >> u >> v;
        u--; v--;
        int gcdval = gcd(A[u], A[v]);
        for (auto d : divisors[gcdval]){
            connected_edges[d].emplace_back(make_pair(u, v));
        }
    }

    ll answer = 0;

    for (int i = maxn - 1; i > 0; i--){
        ll total_weight = 0;
        vector<int> roots_candidates;
        for (auto & [u, v] : connected_edges[i]){
            graph[u].emplace_back(v);
            graph[v].emplace_back(u);
            roots_candidates.emplace_back(u);
            roots_candidates.emplace_back(v);
        }
        //graph dynamically changes
        total_weight = distance_sums(graph, roots_candidates);
        //reset graph
        for (auto & root : roots_candidates){
            graph[root].clear();
        }
        // inclusion-exclusion principle
        for (int j = 2 * i; j < maxn; j += i){
            total_weight = (total_weight - total_weights[j]) % mod;
        }
        total_weights[i] = total_weight;
        answer += 1ll * i * total_weight; 
        answer %= mod;
    }

    if  (answer < 0){
        answer += mod;
    }

    cout << answer << endl;
    return;
}


signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    divisor_init();
    int testcase = 1;
    while(testcase--){
        slv();
    }
    return 0;
}

---

感想

あまり書くことがなく、ビミョーな内容になってしまった...。

あとはてなブログmarkdown書きづらすぎる！

GoにおけるCLIの勉強

GoにおけるCLIの勉強

今回は,GoにおいてのCLIの基本的な事項のまとめと練習を行った.

cobraライブラリの導入

CLIを作る上で必須とも言えるライブラリが「cobra」というものらしい. いろいろ賢い処理を自動でやってくれてとても助かるらしいので,とりあえずgithubから取ってくる.

早速ライブラリのドキュメントを見てみよう.

pkg.go.dev

できることをまとめると以下のような感じ.

• サブコマンドを容易に追加

• コマンドフラグ,インテリジェンス,ヘルプ等の機能提供

etc...

みようみまねでコマンドラインを一つ作成してみた. 構成は以下の通り

mycommand
├── cmd
│   └── cmd.go
└── main.go

メイン実行ファイル

package main

import (
    "log"

    "./cmd"
)

func main() {
    err := cmd.RootCmd.Execute()
    if err != nil {
        log.Fatal(err)
    }
}

コマンドを記述したファイル

package cmd

import (
    "fmt"
    "log"
    "strconv"

    "github.com/spf13/cobra"
)

func init() {
    cobra.OnInitialize()
    RootCmd.AddCommand(SumCmd())
}

var RootCmd = &cobra.Command{
    // 関数名
    Use: "mycmd",

    // 「ヘルプ」出力に表示される短い説明
    Short: "very simple command",

    // 'help <this-command>'出力に表示される長いメッセージ
    Long: `This command is made for learning how to make commands
  with cobra.`,

    // 実行用の関数
    Run: func(cmd *cobra.Command, args []string) {
        fmt.Printf("command [%s] has called!\n", cmd.Use)
    },
}

func SumCmd() *cobra.Command {
    cmd := &cobra.Command{
        Use:   "sum",
        Short: "sum calc",
        Long: `this command calculate the summations of all argument params.
      `,
        RunE: func(cmd *cobra.Command, args []string) error {
            if len(args) == 0 {
                return nil
            }
            var ans int
            for _, arg := range args {
                item, err := strconv.Atoi(arg)
                if err != nil {
                    log.Fatal(err)
                    return err
                }
                ans += item
            }
            fmt.Printf("summation : %d\n", ans)
            return nil
        },
    }

    return cmd
}

ビルドして得られた実行ファイルに対して出力を確認してみよう.

$./mycommand sum 1 2 3 4 5
summation : 15

$./mycommand sum 

$./mycommand sum 1
summation : 1

$./mycommand undefined 
Error: unknown command "undefined" for "mycmd"
Run 'mycmd --help' for usage.
2022/04/07 22:34:06 unknown command "undefined" for "mycmd"

$./mycommand sum 1.0 2 3 
2022/04/07 22:35:43 strconv.Atoi: parsing "1.0": invalid syntax

とりあえずは基本的な部分は良さそう?

****感想

cobra便利ですね.

相変わらず知らんことばっかりなので大変です.

Goにおけるバッファを用いた入出力高速化

初めに

これはGoLang初心者が勉強メモ用に残しているものなので、多少不正確なところがある可能性がある。悪しからず

GoLangにおける入出力

GoLangを用いて競技プログラミングをする際に、最初に直面する壁はおそらく

入出力に関するものだろう。

ただ標準入力から受け取るだけならそれほど困らないだろうが、競技プログラミングにおける、与えられた課題に対して指定された実行制限時間・メモリ範囲内で正しいプログラムを記述するという競技の特性上、場合によってはその標準入力の速度が原因で実行時間制限に間に合わないということが多々ある。

では、プログラムの処理以前に入出力の時点で効率の悪い処理をおこなってしまうことを避けるにはどうすればよいか。

fmt.Scanとbufio.Scanner

GoLangを用いて標準入力を受け取る方法は主に以下の二つがある。

• fmt.Scan()

• bufio.Scanner()/Reader()/Writer()

いずれも標準入力を受け取ることができるという点では共通だが、その行われ方という点では大きく異なる。

• 前者はいちいちio.Readerにアクセスを行い、読み込む。

• 後者はバッファにあらかじめまとめて複数読み込んだ後、アクセスを行い読み込む。

こういった性質上、複数の入力を処理する際、前者と後者で結構な数のシステムコールの回数の差分が発生し処理時間にも影響が出てくる。

具体的には、読み込みの回数が回くらいになってくると前者の方法は使い物にならない。初めの方の簡単な問題を除けば、大体の問題ではこれくらいのオーダーの入出力の回数が要求されることが多い。よって必然的に後者の方法を採用せざるを得ない。

早速GoLangの練習も兼ねて高速化をスマートに行うための構造体クラスの作成を行うことにした。

作成した構造体クラス

実際に作成した構造体クラスは以下の通り。

import (
    "bufio"
    "fmt"
    "io"
    "strconv"
    "strings"
)

const (
    MaxBufSize = int(1e4)
)

type CustomIO struct {
    //This structure can increase the speed of a program by reducing the number of system calls, which are typically slow operations.
    reader bufio.Reader
    writer bufio.Writer
    cache  []string
}

func MakeCustomIO(in io.Reader, out io.Writer, bufsize int) (*CustomIO, error) {
    if bufsize > MaxBufSize {
        return nil, fmt.Errorf("bufsize is too large")
    }
    io := &CustomIO{
        reader: *bufio.NewReaderSize(in, bufsize),
        writer: *bufio.NewWriterSize(out, bufsize),
        cache:  []string{},
    }
    return io, nil
}

func (io *CustomIO) NextLine() string {
    for len(io.cache) == 0 {
        text, err := io.reader.ReadString('\n')
        if err != nil {
            panic(err)
        }
        arr := strings.Split(strings.TrimRight(text, "\n"), " ")
        for i := len(arr) - 1; i >= 0; i-- {
            io.cache = append(io.cache, arr[i])
        }
    }
    res := io.cache[len(io.cache)-1]
    io.cache = io.cache[:len(io.cache)-1]
    return res
}

func (io *CustomIO) NextInt() int {
    res, err := strconv.Atoi(io.NextLine())
    if err != nil {
        panic(err)
    }
    return res
}

func (io *CustomIO) NextFloat(sep byte) float64 {
    res, err := strconv.ParseFloat(io.NextLine(), 64)
    if err != nil {
        panic(err)
    }
    return res
}

func (io *CustomIO) Print(objects ...interface{}) {
    _, err := fmt.Fprintln(&io.writer, objects...)
    if err != nil {
        panic(err)
    }
}

func (io *CustomIO) Printf(format string, objects ...interface{}) {
    _, err := fmt.Fprintf(&io.writer, format, objects...)
    if err != nil {
        panic(err)
    }
}

func (io *CustomIO) Flush() {
    err := io.writer.Flush()
    if err != nil {
        panic(err)
    }
}

使い方は主に以下の通り。

// 標準入力から受け取り,標準出力に返すように設定.
io, _ := MakeCustomIO(file_in, file_out, MaxBufSize)
 
//全てを書き込み終えてから終了.    
defer io.Flush()

a, b, c := io.NextInt(), io.NextInt(), io.NextInt()

io.Printf("%d %d %d\n", a, b, c)

実際の使用例

atcoder.jp

感想

特に問題ないように思えた。

以前まではbufioについてあまり理解しないで使用していたので、反省。

GoLangで競技プログラミングは難しいですね。