Set
使うよりも Array
を使った方が速かったです。 Set
だと 375 ms 、 Array
だと 354 ms 。 Set 版: https://atcoder.jp/contests/hhkb2020/submissions/17324446 Array 版: https://atcoder.jp/contests/hhkb2020/submissions/17324417%
つけないといけなくて面倒で、1 ≤ A, B, C ≤ 10^9
で、積の和を計算するので、とてもじゃないけど 64 bit じゃ収まらないです。%
前の値を出力させてみたら↓でした。 1858445835049782285757026664950217712384527500000000
%
の計算が必要になります。なので、あまり変わらないかなと。BigInt
が使えれば同じことができるんですが・・・。2 ** (2 ** (2 ** (2 ** 2)))
Decimal
で同じことできるかと思ったんですが、 pow
の第 2 引数に Decimal
を渡せないのでダメでした・・・。BigInt
↓これはあるんですが https://github.com/dankogai/swift-ponsBigInt
作るか・・・。BigInt
必要と感じたことはないんですよね。-Ounchecked
だから実行時エラーにならないのか。BigInt
よりも ModInt
を作りました。こっちで計算しておけば常に %
で余りとってくれるので問題ないです。 BigInt
では無理な桁数も扱ってくれるし。 https://github.com/koher/swift-atcoder-support/blob/main/Sources/AtCoderSupport/ModInt.swift998244353
この値はなんですか?なんか競技プログラミングではよく出てくる値みたいですけど。modulus
を書き換えて使うという荒業ですw1000000007
とかもよく使われるみたいです。%
だと結果が負になってしまうので、そこのケアも ModInt
でやってます。%+
とか %-
とか作ろうかと思ったんですが、型にしました。%+
とかの方が用途に合ってるかもしれません。print(D < V * T || V * S < D ? "Yes" : "No")
で算出しましたprint(!(v*t...v*s).contains(d) ? "Yes" : "No")
にしてみました!!
を付けることで消えていないときに "Yes"
を出しているのですねprint(aa.filter { $0 != X } .map { String($0) } .joined(separator: " "))
で算出しました// Paste a sample input here var stdinString: [String] = """ 42782.4720 31949.0192 99999.99 <- ここに標準入力の内容を貼り付ける """.split(separator: "\n").map(String.init).reversed() public func readLine() -> String? { stdinString.popLast() }
2...
でループするってやってないですね。 @swift-5.2.5
let n = 10000000000 var aa: Set<Int> = [] for a in 2... { if a * a > n { break } aa.insert(a) } print(aa.sorted().last!)
(edited)numbers.filter(\.isEven)
extension Int { var isEven: Bool { isMultiple(of: 2) } } print([2, 3, 5].filter(\.isEven))
let n = 5 var sumToCount: [Int: Int] = [:] for i in 1 ... n { for j in 1 ... n { for k in 1 ... n { let sum = i + j + k sumToCount[sum, default: 0] += 1 } } } for sum in sumToCount.keys.sorted() { print(sum, sumToCount[sum]!) }
3 1 4 3 5 6 6 10 7 15 8 18 9 19 10 18 11 15 12 10 13 6 14 3 15 1
let n = readInt1() let aa = readIntN() var aToCount: [Int: Int] = [:] for a in aa { aToCount[a % 200, default: 0] += 1 } var ans = 0 for count in aToCount.values { ans += count * (count - 1) / 2 } print(ans)
var a = true a.toggle() print(a)
pow((1-sqrt(5))/2, N)
が出てきますがこれって計算量どうなるんですっけimport Foundation func original(n: Int, x: Int, y: Int) -> Int { var (n, x, y) = (n, x, y) for _ in 2 ..< n { let t = (x + y) % 100 x = y y = t } return y } struct Mat { var m11: Double var m12: Double var m21: Double var m22: Double init(_ m11: Double, _ m12: Double, _ m21: Double, _ m22: Double) { self.m11 = m11 self.m12 = m12 self.m21 = m21 self.m22 = m22 } static func * (lhs: Mat, rhs: Mat) -> Mat { Mat( lhs.m11*rhs.m11 + lhs.m12*rhs.m21, lhs.m11*rhs.m12 + lhs.m12*rhs.m22, lhs.m21*rhs.m11 + lhs.m22*rhs.m21, lhs.m21*rhs.m12 + lhs.m22*rhs.m22 ) } } func mat(n: Int, x: Int, y: Int) -> Double { let S = Mat( -(1+sqrt(5))/2, -(1-sqrt(5))/2, 1, 1 ) let Jn = Mat( pow((1-sqrt(5))/2, Double(n-2)), 0, 0, pow((1+sqrt(5))/2, Double(n-2)) ) let St = Mat( -1 / sqrt(5), (5-sqrt(5)) / 10, 1 / sqrt(5), (5+sqrt(5)) / 10 ) let m = S * Jn * St let num = Double(x) * m.m12 + Double(y) * m.m22 return num - floor(num/100)*100 } print(original(n: 60, x: 2, y: 3), mat(n: 60, x: 2, y: 3)) print(original(n: 80, x: 2, y: 3), mat(n: 80, x: 2, y: 3))
81 81.00830078125 91 64.0
let aa = readLine()!.split(separator:" ").map { Int(String($0))! }
let aa = readLine()!.split(separator: " ").map { Int($0)! }
append()
するより init(repeating:count:)
で最初に確保するほうがパフォーマンスがいいのでしょうか?dp.last!
で強制アンラップしていますが、 dp[N - 1]
でインデックスを使えば !
は不要ですね、、動的計画法 1-2 について Xcode(Mac でしか動作しない IDE)のコンソールに入力例をコピペするとエラーになります。VSCode に貼ってからコピペし直すとうまくいくようなので、文字コードなどの問題かもしれません。 また、入力例を貼り付けたあとに自分で Enter キーを押下しないといけないのも地味に手間です。AtCoder では自動で Return まで入力されたので、同じ仕様だと嬉しいです。
append()
するより init(repeating:count:)
で最初に確保するほうがパフォーマンスがいいのでしょうか? append()
するより init(repeating:count:)
で最初に確保するほうがパフォーマンスがいいのでしょうか? dp.last!
で強制アンラップしていますが、 dp[N - 1]
でインデックスを使えば !
は不要ですね、、 !
不要ですが、 Array
に [i]
でアクセスするのは !
使ってるのと同じ( !
の nil
も [i]
の範囲外も Logic Failure )なので、どちらが良いかと言われると微妙ですね。append
でのバッファの確保は倍々に行われるので、バッファの allocate およびコピーの計算量がその長さに比例するとした場合、最終的に N 要素分の領域を確保するための計算量は reserveCapacity
してもしなくても O(N) になります。もちろんそれでも reserveCapacity
した方が定数倍速いんですが、競プロの問題は定数倍が原因で TLE になることは稀であり、成績を残すには速く解くことが重要なので、このようなケースでは reserveCapacity
はほぼ必要ないと考えています。cin >>
cout << hoge << endl;
みたいな書き方にもだんだん慣れてきましたwlet N = Int(readLine()!)!
を cpp で書くと int N; cin >> N;
std::scanf
std::printf
派もいるみたいです(こっちのほうが正統?) (edited)print(hoge)
は cout << hoge << endl
componentsSeparatedByString
とか、普通に英文として読めるstringByAddingPercentEncodingWithAllowedCharacters:
とかも > 長いのint main() { cout << "Hello" << "World!"; return 0; }
int main() { cout << "Hello" << "World!" << endl << "hahaha"; return 0; }
Fatal error: Range requires lowerBound <= upperBound
print("row: \(row), column: \(column), dp: \(dp)")
memo[rbg]
でキャッシュのディクショナリにアクセスしていますが、 memo
の要素を 1 つずつ取り出し、ヒット率が悪くなれば打ち切る、ということですね ヒット率のしきい値をきれいに求められれば有効そう…?memo
はメソッドが呼び出される度に使い捨ててるので、空間計算量のオーダーも変わってないですし特に問題なさそうですね(超巨大な画像で、メモリを数倍使ったらアウトとかいう状況でなければ)。