Closed13

Go言語で初心者が競プロ的なのしながら作った関数

整数の絶対値

func abs64(v int64) int64 {
	y := v >> 63
	return (v ^ y) - y
}
func abs32(v int32) int32 {
	y := v >> 31
	return (v ^ y) - y
}

文字列を逆順にする

func reverse(s *string) {
	rs := []rune(*s)
	n := len(rs)
	for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
		rs[i], rs[j] = rs[j], rs[i]
	}
	*s = string(rs)
}

Map[K]Vのキーの数

d := make(map[K]V, n)
len(d)

フィボナッチ数列(メモ化)

一括で-1で初期化できないので、[]intでなく[]*intにする。

var memo []*int

func fib_(n int) int {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		v := memo[n]
		if v != nil {
			return *v
		}
		s := fib_(n-1) + fib_(n-2)
		memo[n] = &s
		return s
	}
}

func fib(n int) int {
	memo = make([]*int, n+1)
	return fib_(n)
}

部分和問題&動的計画法

関数ではないけどとりあえず

package main

import (
	"fmt"
)

func chmax(a *bool, b bool) {
	if b {
		*a = b
	}
}

func main() {
	var N, W int
	fmt.Scan(&N, &W)
	dp := make([][]bool, N+1)
	a := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&a[i])
		dp[i] = make([]bool, W+1)
		dp[i][0] = true
	}
	dp[N] = make([]bool, W+1)
	dp[N][0] = true
	for i := 0; i < N; i++ {
		for w := 0; w <= W; w++ {
			// a[i]を使う場合
			if w-a[i] >= 0 {
				chmax(&dp[i+1][w], dp[i][w-a[i]])
			}
			// a[i]を使わない場合
			chmax(&dp[i+1][w], dp[i][w])
		}
	}
	/*
		for i := 0; i <= N; i++ {
			for w := 0; w <= W; w++ {
				if dp[i][w] {
					fmt.Printf("1 ")
				} else {
					fmt.Printf("0 ")
				}
			}
			fmt.Println()
		}
	*/
	if dp[N][W] {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}

}

ペア和

package main

import (
	"fmt"
	"math"
	"sort"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	a := make([]int, n)
	b := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&b[i])
	}
	sort.Ints(b)
	var v int = math.MaxInt64
	for i := 0; i < n; i++ {
		x := a[i]
		j := sort.Search(n, func(j int) bool { return x+b[j] >= k })
		vv := x + b[j]
		if v > vv {
			v = vv
		}
	}
	fmt.Println(v)
}

int64の冪乗

import "math/big"

func powInt64(x, y int64) int64 {
	return new(big.Int).Exp(big.NewInt(x), big.NewInt(y), nil).Int64()
}

アルファベットの個数を数える

	var s string
	fmt.Scan(&s)
	a := make([]int, 26)
	n := len(s)
	bs := []byte(s)
	for i := 0; i < n; i++ {
		ch := int(bs[i])
		a[int(ch-'a')]++
	}

文字列の数字を数字としてソート

	sort.Slice(a, func(i, j int) bool {
		l, _ := strconv.Atoi(a[i])
		r, _ := strconv.Atoi(a[j])
		return l < r
	})

queue

type Queue []int

func NewQueue(cap int) *Queue {
	q := make(Queue, 0, cap)
	return &q
}
func (q *Queue) Push(x int) {
	*q = append(*q, x)
}
func (q *Queue) Pop() int {
	x := (*q)[0]
	*q = (*q)[1:]
	return x
}
func (q *Queue) Empty() bool {
	return len(*q) == 0
}

Stack

type Stack []int

func NewStack(cap int) *Stack {
	q := make(Stack, 0, cap)
	return &q
}
func (q *Stack) Push(x int) {
	*q = append(*q, x)
}
func (q *Stack) Pop() int {
	n := len(*q)
	x := (*q)[n-1]
	*q = (*q)[:n-1]
	return x
}
func (q *Stack) Empty() bool {
	return len(*q) == 0
}

Union Find

type UnionFind []int

func NewUnionFind(N int) *UnionFind {
	u := make(UnionFind, N)
	return &u
}

func (u *UnionFind) Root(x int) int {
	if (*u)[x]-1 < 0 {
		return x
	}
	(*u)[x] = u.Root((*u)[x])
	return (*u)[x]
}

func (u *UnionFind) Unite(x, y int) {
	xr := u.Root(x)
	yr := u.Root(y)
	if xr == yr {
		return
	}
	(*u)[yr] -= u.Size(xr)
	(*u)[xr] = yr
}

func (u *UnionFind) IsSame(x, y int) bool {
	return u.Root(x) == u.Root(y)
}

func (u *UnionFind) Size(x int) int {
	return -(*u)[u.Root(x)] + 1
}

トポロジカルソート

input.txt
8 12
0 5
1 3
1 6
2 5
2 7
3 0
3 7
4 1
4 2
4 6
6 7
7 0
package main

import (
	"fmt"
	"strconv"
	"strings"
)

var (
	seen  []bool
	order []int
)

func rec(gr [][]int, v int) {
	fmt.Printf("%d-in -> ", v)
	seen[v] = true
	for _, next_v := range gr[v] {
		if seen[next_v] {
			continue
		}
		rec(gr, next_v)
	}
	fmt.Printf("%d-out -> \n", v)
	order = append(order, v)
}

func Reverse(rs []int) []string {
	n := len(rs)
	ss := make([]string, n)
	for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
		ss[i], ss[j] = strconv.Itoa(rs[j]), strconv.Itoa(rs[i])
	}
	return ss
}

func main() {
	var n, m int /* n: 頂点, m: 辺 */
	fmt.Scan(&n, &m)
	gr := make([][]int, n)
	for i := 0; i < n; i++ {
		gr[i] = make([]int, 0, n-1)
	}
	for i := 0; i < m; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		gr[a] = append(gr[a], b)
	}
	seen = make([]bool, n)
	order = make([]int, 0, n)
	for v := 0; v < n; v++ {
		if seen[v] {
			continue
		}
		rec(gr, v)
	}
	fmt.Println(strings.Join(Reverse(order), " -> "))
}
0-in -> 5-in -> 5-out -> 
0-out -> 
1-in -> 3-in -> 7-in -> 7-out -> 
3-out -> 
6-in -> 6-out -> 
1-out -> 
2-in -> 2-out -> 
4-in -> 4-out -> 
4 -> 2 -> 1 -> 6 -> 3 -> 7 -> 0 -> 5
このスクラップは3ヶ月前にクローズされました
作成者以外のコメントは許可されていません