🤔
コーディングテストとか競技プログラミングとかで役立ちそうな関数
はじめに
競技プログラミングやプログラミングテストのために作った関数を載せていきます．言語はSwiftです．「こっちの方が早いよ！」，「一般化できるよ！」，「命名センスなさすぎ！」等あれば教えてください．
なお，関数の中で別の関数を使っているため，単独で使えない場合があります．
最大公約数を求める関数
func gcd(_ num1: Int, _ num2: Int) -> Int {
let r = num1 % num2
if r != 0 {
return gcd(num2, r)
} else {
return num2
}
}
３つ以上の数の最大公約数を求める関数
上の関数を一般化
func gcdArr(_ numArr: [Int]) -> Int {
var ans: Int = numArr[0]
for i in numArr {
ans = gcd(ans, i)
}
return ans
}
最小公倍数を求める関数
func lcm(_ num1: Int, _ num2: Int) -> Int {
var gcdNum = gcd(num1, num2)
return num1*num2/gcdNum
}
３つ以上の最大公約数を求める関数
func lcmArr(_ numArr: [Int]) -> Int {
var ans: Int = 1
for i in numArr {
ans = lcm(ans, i)
}
return ans
}
各桁の和を求める関数
func sumEachDigit(num:String) -> Int {
return num.compactMap{ Int(String($0)) }.reduce(0, +)
}
一次不定方程式 ax+by=gcd(a,b)を満たすa,bを求める関数
func solveIdentifyEquasion(_ a: Int,_ b: Int) -> [Int]{
var (d,d_): (Int,Int) = (a,b)
var (x,x_) = (1,0)
var (y,y_) = (0,1)
var q: Int
while d_ != 0 {
q = d/d_
(d,d_) = (d_,d%d_)
(x,x_) = (x_,x-q*x_)
(y,y_) = (y_,y-q*y_)
}
return [x,y]
}
素数判定する関数
ex:) primeJudge(32) -> false
func primeJudge(_ num: Int) -> Bool {
var i = 2
if num == 1 {
return false
}
if num == 2 || num == 3{
return true
}
for i in 2 ... Int(sqrt(Double(num))) {
if num%i == 0 {
return false
}
}
return true
}
約数列挙する関数
ex:) multiple(32) -> [1,2,4,8,16,32]
func factors(_ num: Int) -> [Int] {
var factorsArr = [Int]()
for i in 1 ... Int(sqrt(Double(num))) {
if num.isMultiple(of: i) {
factorsArr.append(i)
if num/i != i {
factorsArr.append(num/i)
}
}
}
var ans = factorsArr.sorted()
return ans
}
指数を求める関数
ex:) exponents(32,2) -> 5
func exponents(_ num1: Int, _ num2: Int) -> Int {
if num2 == 1 {
return 1
}
var count = 0
var num1 = num1
while num1.isMultiple(of: num2) {
num1 /= num2
count += 1
}
return count
}
素因数分解する関数
約数と指数を連続で格納します．
ex:)primeFactorization(120)->[[2, 3], [3, 1], [5, 1]]
func primeFactorization(_ num: Int) -> [[Int]] {
var primeFactArr = [[Int]]()
for i in 2 ... Int(sqrt(Double(num))) {
if num.isMultiple(of: i) {
if primeJudge(i) {
primeFactArr.append([i,exponents(num, i)])
}
}
}
return primeFactArr
}
###桁数を返す関数
ex:)numberOfDigits(1221)->4
func numberOfDigits(_ num: Int) -> Int {
var digits = 1
var num = num
while num >= 10 {
num /= 10
digits += 1
}
return digits
}
階乗を求める関数
15くらいが限界．おそらく他にもっといい書き方あります．
func factrials(_ num: Int) -> Int {
if num == 0 {
return 1
}
var num = num
var i = num-1
while i > 1 {
num *= i
i -= 1
}
return num
}
与えられた数字以下の素数が格納された配列を返す関数
実用性は低い．何かの問題だった気がする．
func primeArr (_ num: Int) -> [Int] {
var primeArr = [Int]()
for_i: for i in 2 ... num {
for j in primeArr {
if i.isMultiple(of: j) {
break
}
}
if primeJudge(i){
primeArr.append(i)
}
}
return primeArr
}
与えられた2つの数字の間に含まれる素数が格納された配列を返す関数
func primeArrRange (_ num1: Int, _ num2: Int) -> [Int] {
var primeArr = [Int]()
for_i: for i in num1 ..< num2 {
for j in primeArr {
if i.isMultiple(of: j) {
break
}
}
if primeJudge(i){
primeArr.append(i)
}
}
return primeArr
}
整数の累乗を返す関数
func powInt (_ num1: Int, num2: Int) -> Int {
let ans = pow(Double(num1), Double(num2))
return Int(ans)
}
配列から同じ要素を削除する関数
func uniq<S : Sequence, T : Hashable>(source: S) -> [T] where S.Iterator.Element == T {
var buffer = [T]()
var added = Set<T>()
for elem in source {
if !added.contains(elem) {
buffer.append(elem)
added.insert(elem)
}
}
return buffer
}
10/29 更新
[Character]をString型にする処理
これはここでまとめるほどではないかもしれませんが．
joined()はStrig型にしか使えません．
let a:[Character] = ["a","b","c"]
a.map{String($0)}.joined()
print(a.map{String($0)}.joined()) //abc
文字列に使われているアルファベットの数を返す関数
func wordAlph(word: String) -> [Int] {
var countArr = [Int](repeatElement(0, count: 26))
let lowChaArr = (97...122).map{String(Character(UnicodeScalar($0)!))}//a,b,c,d,e,f,...
for i in word {
//print(lowChaArr.index(of: String(i))!)
countArr[lowChaArr.index(of: String(i))!] += 1
}
return countArr
}
辞書型をkey,valueのみ取り出す
let dic:[String:Int] = ["one":1,"two":2,"three":3,"four":4,"five":5]
let keyArr = dic.keys.map({String($0)})
let valueArr = dic.values.map({Int($0)})
print(keyArr)
print(valueArr)
文字列を配列に格納する
var arr = Array(rd).compactMap { Int(String($0)) }.sorted()
文字列から特定の文字までの部分文字列を取得する
let str = "aiueo/kakikukeko"
let index = str.index(of: "/")
str[..<index!]//aiueo
let index2 = str.index(after: index!)
str[index2...]//kakikukeko
包除原理
100以下の自然数のうち3または5の倍数はいくつ含まれているか？といった問いに対する関数
func inclusionExclusion2(num: Int, nums: [Int]) -> Int {
var answer = 0
var index = 1
while nums[0]*index <= num {
answer += 1
index += 1
}
index = 1
while nums[1]*index <= num {
answer += 1
index += 1
}
index = 1
while nums[0]*nums[1]*index <= num {
answer -= 1
index += 1
}
return answer
}
少し一般化したもの
func inclusionExclusion2better(num: Int, nums: [Int]) -> Int {
var answer = 0
var index = 1
for i in 0..<nums.count {
while nums[i]*index <= num {
answer += 1
index += 1
}
index = 1
for j in i+1..<nums.count {
print("テスト")
while nums[i]*nums[j]*index <= num {
answer -= 1
index += 1
}
}
index = 1
}
return answer
}
累乗の余り
func modPow(_ base: Int, _ power: Int, _ module: Int) -> Int {
var a = base
var b = power
let m = module
if a == 0 {
return 0
}
var result = 1
a %= m
while(b != 0) {
if b%2 == 1 {
result = (result*a)%m
}
a = (a*a)%m
b /= 2
}
return result
}
自然数環
class Z {
let mod: Int
let factors: [Int]
init(_ mod: Int) {
var factors: [Int] = []
self.mod = mod
for i in 0 ... mod-1 {
factors.append(i)
}
self.factors = factors
}
var 零因子: [Int] {
factors.filter({!可逆元.contains($0)})
}
var 可逆元: [Int] {
factors.filter({gcd($0, mod) == 1})
}
var ベキ零元: [Int] {
let prodOfPrimeFactor = mod.primeFactors.reduce(1, *)
return factors.filter({$0%prodOfPrimeFactor == 0})
}
}
let z12 = Z(12)
z12.可逆元
z12.零因子
z12.ベキ零元
これはどこで使えるかは微妙だが、ちょっと面白いので書いた。
Discussion