Skip to content

Instantly share code, notes, and snippets.

@halllllll
Last active March 4, 2021 00:21
Show Gist options
  • Save halllllll/853ab587fd82ee3ffe6f7fb7fb499695 to your computer and use it in GitHub Desktop.
Save halllllll/853ab587fd82ee3ffe6f7fb7fb499695 to your computer and use it in GitHub Desktop.
go utilities for competitive programming
package main
import (
"bufio"
"fmt"
"os"
"reflect"
"strconv"
)
var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
func main() {
buf := make([]byte, 1024*1024)
sc.Buffer(buf, bufio.MaxScanTokenSize)
sc.Split(bufio.ScanWords)
defer out.Flush() // !!!!caution!!!! you must use Fprint(out, ) not Print()
/* --- code --- */
a, b := nextInt(), nextInt()
fmt.Fprintln(out, a, b)
}
// -*-*-*-*-*-*-*-*-
// * I/O utilities *
// -*-*-*-*-*-*-*-*-
func next() string {
sc.Scan()
return sc.Text()
}
func nextInt() int {
a, _ := strconv.Atoi(next())
return a
}
func nextFloat64() float64 {
a, _ := strconv.ParseFloat(next(), 64)
return a
}
func nextInts(n int) []int {
ret := make([]int, n)
for i := 0; i < n; i++ {
ret[i] = nextInt()
}
return ret
}
func nextFloats(n int) []float64 {
ret := make([]float64, n)
for i := 0; i < n; i++ {
ret[i] = nextFloat64()
}
return ret
}
func nextStrings(n int) []string {
ret := make([]string, n)
for i := 0; i < n; i++ {
ret[i] = next()
}
return ret
}
func chars(s string) []string {
ret := make([]string, len([]rune(s)))
for i, v := range []rune(s) {
ret[i] = string(v)
}
return ret
}
// PrintOut with util device
func PrintOut(src interface{}, joinner string) {
switch reflect.TypeOf(src).Kind() {
case reflect.Slice:
s := reflect.ValueOf(src)
for idx := 0; idx < s.Len(); idx++ {
fmt.Fprintf(out, "%v", s.Index(idx))
if idx < s.Len()-1 {
fmt.Fprintf(out, "%s", joinner)
} else {
fmt.Fprintln(out)
}
}
default:
fmt.Fprintln(out, "fuck")
}
}
// -*-*-*-*-*-*-*-
// * Structures *
// -*-*-*-*-*-*-*-
// Queue ... only for integers
type Queue struct {
queue []int
}
// Enqueue ... the so-called enqueue
func (q *Queue) Enqueue(x int) {
q.queue = append(q.queue, x)
}
// Dequeue ... the so-called dequeue
func (q *Queue) Dequeue() (ret int) {
ret, q.queue = q.queue[0], q.queue[1:]
return
}
// Len ... return length of queue
func (q *Queue) Len() (ret int) {
return len(q.queue)
}
// reverse any type of slice
func reverseAny(slice interface{}) {
n := reflect.ValueOf(slice).Len()
swap := reflect.Swapper(slice)
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
swap(i, j)
}
}
// -*-*-*-*-*-*-*-*-
// * tool snippets *
// -*-*-*-*-*-*-*-*-
func duplicate2Int(base [][]int) (ret [][]int) {
ret = make([][]int, len(base))
for i, v := range base {
ret[i] = append([]int{}, v...)
}
return
}
func min(a, b int) int {
x, y := toFloat64(a), toFloat64(b)
if x < y {
return a
}
return b
}
func max(a, b int) int {
x, y := toFloat64(a), toFloat64(b)
if x > y {
return a
}
return b
}
func toFloat64(v interface{}) float64 {
r := reflect.ValueOf(v)
if r.IsValid() {
switch r.Kind() {
case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64,
reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64,
reflect.Float32, reflect.Float64:
var x float64
return r.Convert(reflect.TypeOf(x)).Interface().(float64)
default:
return 0
}
}
return 0
}
// -*-*-*-*-*-*-*-*-*-*-*-*-*-
// * Algorithms Utility Zone *
// -*-*-*-*-*-*-*-*-*-*-*-*-*-
// -*-*-*-*-*-*-*-
// * 1. nibutan *
// -*-*-*-*-*-*-*-
func lowerBound(arr []int, target int) int {
l, r := 0, len(arr)
for l < r {
mid := (l + r) / 2
if arr[mid] < target {
l = mid + 1
} else {
r = mid
}
}
return l
}
func upperBound(arr []int, target int) int {
l, r := 0, len(arr)
for l < r {
mid := (l + r) / 2
if target < arr[mid] {
r = mid
} else {
l = mid + 1
}
}
return l
}
// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
// * math flavor typical theories *
// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
func gcd(a, b int) int {
if a > b {
return gcd(b, a)
}
for a != 0 {
a, b = b%a, a
}
return b
}
func pow(a, b int) (ret int) {
ret = a
// 10^2 = 100ってことは10に10を1回掛けることだね
// なので初期値を含めると上限b-1未満
for i := 0; i < b-1; i++ {
ret *= a
}
return
}
func powMod(n, m, mod int) (ret int) {
ret = 1
for m > 0 {
if m&1 == 1 {
ret *= n
ret %= mod
}
n *= n
n %= mod
m >>= 1
}
return ret
}
func ncr(n, r int) int {
// せいぜいn<10^2くらいの精度しかなくない?
res := 1
for i := 1; i <= r; i++ {
res = res * (n - i + 1) / i
}
return res
}
func ncrMod(n, r, mod int) int {
// 呼び出すたびにテーブルを作るのは愚です(どうしようかね)
_n := 1000000
g1 := make([]int, _n+1)
g1[0], g1[1] = 1, 1
g2 := make([]int, _n+1)
g2[0], g2[1] = 1, 1
inverse := make([]int, _n+1)
inverse[0], inverse[1] = 0, 1
for i := 2; i <= _n; i++ {
g1[i] = (g1[i-1] * i) % mod
inverse[i] = mod - inverse[mod%i]*(mod/i)%mod
g2[i] = (g2[i-1] * inverse[i]) % mod
}
return g1[n] * (g2[r] * g2[n-r] % mod) % mod
}
// たくさん使う場合は↑より↓のほうが1000倍くらい早い
func combMod(n, m, MOD int) int {
return factorial(n, n-m+1, MOD) * _pow(factorial(m, 2, MOD), MOD-2, MOD) % MOD
}
func _pow(x, n, MOD int) int {
r := 1
for ; n > 0; n /= 2 {
if n%2 == 1 {
r = r * x % MOD
}
x = x * x % MOD
}
return r
}
func factorial(n, m, MOD int) int {
r := 1
for i := m; i <= n; i++ {
r = r * i % MOD
}
return r
}
func nextPerm(arr []int) func() []int {
/*
how to use it:
this is a generator, so should be invoked such as below example.
"""code"""
np := nextPermutation(arr)
for{
lis := np()
if len(lis) == 0{
break
}
fmt.Println(lis)
}
"""code end"""
*/
first := true
ret := append([]int{}, arr...)
_nextPerm := func() []int {
if first {
first = false
return arr
}
n := len(ret)
for i := n - 2; i >= 0; i-- {
if ret[i] < ret[i+1] {
j := n
for {
j--
if ret[i] < ret[j] {
break
}
}
ret[i], ret[j] = ret[j], ret[i]
for k := n - 1; i < k; i, k = i+1, k-1 {
ret[i+1], ret[k] = ret[k], ret[i+1]
}
return ret
}
}
return []int{}
}
return _nextPerm
}
// Enumerate all the divisors.
func enumDiv(x int) (ret []int) {
ret = []int{}
for i := 1; i*i <= x; i++ {
if x%i == 0 {
ret = append(ret, i)
if i != 1 && i*i != x {
ret = append(ret, x/i)
}
}
}
return
}
// 素因数分解
func primeFactorization(x int) map[int]int {
ret := make(map[int]int)
for i := 2; i*i <= x; i++ {
for x%i == 0 {
x /= i
ret[i] += 1
}
}
if x > 1 {
ret[x] += 1
}
return ret
}
@halllllll
Copy link
Author

あと追加したいもの

  • ソート

@halllllll
Copy link
Author

その前にRound追加した。小数点n桁で丸めるやつ

@halllllll
Copy link
Author

出力をバッファして最後にflushするやつ追加した

@halllllll
Copy link
Author

出力をバッファするやつ間違えてるので書き直す

@halllllll
Copy link
Author

任意のスライス(基本型のみ)を任意の文字列区切りで出力するやつ追加した

@halllllll
Copy link
Author

packageがわかりにくくなってきたのでmain含む全部足したったわ

@halllllll
Copy link
Author

halllllll commented Jan 15, 2018

map[interface{}]interface{}をkeyとvalueのスライスにわけて返すやつ足した。なんでmap[interface{}]interface{}のみしか使えないのかは一切不明。 ↓参照

@halllllll
Copy link
Author

↑のやつちょっと使いづらいというかmap[interface{}]interface{}で帰ってきたやつをどう使えばいいのかまったくわからんのだが・・?保留にするわ

@halllllll
Copy link
Author

変更点三箇所

  • maxminがinterfaceを受け取ってinterfaceで返すやつにしたが、これだとどうせ呼び出し側でinterfaceをよしなに変換してやらねばならず使いにくい。いっそintのみとした
  • bufio.Bufferを追加。1行が長すぎて受け取れない問題サンプルがあったのでデフォルト値(2^16)ではなく決め打ちで設定
  • Structureを追加。とりあえずintのみのQueueを作ったがあんまり必要無い気がする。Enqueue, Dequeue, Lenが使える

@halllllll
Copy link
Author

  • 名前をgoに則ってキャメルケースにした
  • アルゴリズム的に優れたcombModを追加(ncrModより早い)
  • 素因数分解
  • スライス反転

@halllllll
Copy link
Author

* スライス反転

reflect.SwapperとかいうやつはGoのなんだっけ1.14とかそのへんから入ったらしい

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment