Closed13

# 整数の絶対値

``````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)
``````

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

``````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ヶ月前にクローズされました