[計算量をざっくり理解] アルゴリズムの実行時間
アルゴリズムの計算量を考える時、主なオーダーのグラフは以下のようになります。 wikipedia より \( O(1) \) 定数 Constant、\( O ( \log n) \) 対数 Logarithmic、\( O (n) \) 線形 ...
[計算量をざっくり理解] Big Ω Big Θ
Big Ω 記法 Big O 記法では、\(f(x) = O(g(x)) \)は，関数\( g(x) \)が関数\( f(x) \)の上界であることを表しました。 Big Ω 記法では、 \(f(x) = \Omega (g(x)) \)は，関...
[計算量をざっくり理解] Big O 記法
ランダウの記号 ランダウの記号（ランダウのきごう、英:Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 出典: フリー百科事典『ウィキペディア（Wikipedia）』 "Big O ...
[計算量をざっくり理解] 計算複雑性理論
計算複雑性理論 計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学...
[Python] ABC020 C 全探索 40点
問題 C - 壁抜け 回答 スライドの方針に従って、深さ優先探索により全ての経路を探索し、最初にゴールに到達できた x を解答にします。 AtCoder Beginner Contest 020 解説 from AtCoder Inc. ...
[Python] ABC020 B
問題 B - 足し算 回答 A, B = input().split() AB = A + B ans = 2 * int(AB) print(ans)
[Python] ABC020 A
問題 A - クイズ 回答 条件分岐 Q = int(input()) if Q == 1: print('ABC') else: print('chokudai') 三項演算子 Q = int(input()) a...
[Python] ABC019 D
問題 D - 高橋くんと木の直径 回答 20点回答 全て探索します。 AtCoder Beginner Contest 019 解説 from AtCoder Inc. import sys N = int(input())...
[Python] ABC019 C
問題 C - 高橋くんと魔法の箱 回答 スライドに従い、50点回答を求めます。 AtCoder Beginner Contest 019 解説 from AtCoder Inc. N = int(input()) a = list(...
[Python] ABC019 B
問題 B - 高橋くんと文字列圧縮 回答 s = input() s_compressed = '' cnt = 1 for i, ch in enumerate(s): if i == 0: ch_pre = ch ...