|
<head> |
|
<script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script> |
|
<style> |
|
pre { |
|
margin: 3px; |
|
padding: 2px; |
|
background-color: #DDDDDD; |
|
} |
|
</style> |
|
</head> |
|
|
|
<body> |
|
<h1 id="-">目次</h1> |
|
<ol> |
|
<li>関数など<ul> |
|
<li><a href="#gcd">最小公倍数、最大公約数</a> </li> |
|
<li><a href="#iter">組み合わせ、階乗</a></li> |
|
<li><a href="#math">mathモジュール</a></li> |
|
<li><a href="#sort">sort, max, min</a></li> |
|
<li><a href="#slice">スライス</a></li> |
|
<li><a href="#input">入力</a></li> |
|
<li><a href="#output">出力</a></li> |
|
</ul> |
|
</li> |
|
<li>典型の実装<ul> |
|
<li><a href="#half">二分探索</a></li> |
|
<li><a href="#sum">累積和</a></li> |
|
</ul> |
|
</li> |
|
</ol> |
|
<h1 id="-a-id-gcd-a-"><a id="gcd">最小公倍数、最大公約数</a></h1> |
|
<pre><code class="lang-python"><span class="hljs-keyword">import</span> fractions |
|
<span class="hljs-comment"># Python3.5以降はmathモジュールに統合された</span> |
|
|
|
<span class="hljs-comment"># 最大公約数</span> |
|
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">gcd</span><span class="hljs-params">(a, b)</span>:</span> |
|
<span class="hljs-keyword">return</span> fractions.gcd(a, b) |
|
|
|
<span class="hljs-comment"># 最小公倍数</span> |
|
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">lcm</span><span class="hljs-params">(a, b)</span>:</span> |
|
<span class="hljs-keyword">return</span> a * b // gcd(a, b) |
|
|
|
<span class="hljs-comment"># 何度も使う場合は自前で素因数分解した方が早い</span> |
|
</code></pre> |
|
<h1 id="-a-id-iter-a-"><a id="iter">組み合わせ、階乗</a></h1> |
|
<pre><code class="lang-python">import itertools |
|
import math |
|
s = <span class="hljs-string">"ABCD"</span> # 配列、タプル、集合でもよい |
|
|
|
<span class="hljs-meta"># 重複なしのあらゆる並び(順列)</span> |
|
itertools.permutations(s, <span class="hljs-number">2</span>) |
|
<span class="hljs-meta"># => (AB AC AD BA BC BD CA CB CD DA DB DC) (タプル)</span> |
|
|
|
<span class="hljs-meta"># 重複なしのソートされた並び(組み合わせ)</span> |
|
itertools.combinations(s, <span class="hljs-number">2</span>) |
|
<span class="hljs-meta"># => (AB AC AD BC BD CD)</span> |
|
|
|
<span class="hljs-meta"># 階乗 O(N)であることに注意</span> |
|
math.factorial(<span class="hljs-number">3</span>) |
|
<span class="hljs-meta"># => 1 * 2 * 3 = 6</span> |
|
</code></pre> |
|
<h1 id="-a-id-math-math-a-"><a id="math">mathモジュール</a></h1> |
|
<pre><code class="lang-python">import math |
|
|
|
# 切り捨て、切り上げ、四捨五入 |
|
math.floor(<span class="hljs-number">1.9</span>) # <span class="hljs-number">1</span> |
|
math.ceil(<span class="hljs-number">1.1</span>) # <span class="hljs-number">2</span> |
|
round(<span class="hljs-number">1.5</span>) # <span class="hljs-number">2</span> |
|
|
|
# 三角関数 入力がラジアン(弧度)であることに注意 |
|
# math.radiansで変換もできる (逆はmath.degrees()) |
|
<span class="hljs-literal">PI</span> = math.pi |
|
math.sin(<span class="hljs-literal">PI</span>/<span class="hljs-number">4</span>) # <span class="hljs-number">1.4142</span>.../<span class="hljs-number">2</span> |
|
math.cos(<span class="hljs-literal">PI</span>/<span class="hljs-number">4</span>) # <span class="hljs-number">1.4142</span>.../<span class="hljs-number">2</span> |
|
math.tan(math.radians(<span class="hljs-number">45</span>)) # <span class="hljs-number">1</span> |
|
|
|
# 平方根 <span class="hljs-number">1</span>/<span class="hljs-number">2</span>乗でも可能 |
|
math.sqrt(<span class="hljs-number">2</span>) # <span class="hljs-number">1.4142</span>... |
|
<span class="hljs-number">2</span>**(<span class="hljs-number">1</span>/<span class="hljs-number">2</span>) # <span class="hljs-number">1.4142</span>... |
|
|
|
# 対数 |
|
math.log(<span class="hljs-number">9</span>, <span class="hljs-number">3</span>) # log3(<span class="hljs-number">9</span>) = <span class="hljs-number">2</span> |
|
</code></pre> |
|
<h1 id="-a-id-sort-sort-max-min-a-"><a id="sort">sort, max, min</a></h1> |
|
<pre><code class="lang-python">lst = [<span class="hljs-comment">(1, 2)</span>, <span class="hljs-comment">(2, 4)</span>, <span class="hljs-comment">(3, 1)</span>] |
|
|
|
<span class="hljs-attr"># lst.sort()は破壊的、sorted(lst)は非破壊的 |
|
|
|
# sortは通常は一つ目の要素を優先してソートする |
|
sorted(lst) # (1</span> <span class="hljs-number">2</span>) <span class="hljs-comment">(2 4)</span> <span class="hljs-comment">(3 1)</span> |
|
|
|
<span class="hljs-attr"># keyに無名関数を渡すと、その要素で評価してくれる |
|
# この場合だとx[1</span>]、つまり二つ目の要素でソートされる。 |
|
sorted<span class="hljs-comment">(lst, key=lambda x:x[1])</span> <span class="hljs-attr"># (3</span> <span class="hljs-number">1</span>) <span class="hljs-comment">(1 2)</span> <span class="hljs-comment">(2 4)</span> |
|
|
|
<span class="hljs-attr"># max()、min()関数にも同じような使い方ができる |
|
max(lst) # (3</span>, <span class="hljs-number">1</span>) 一つ目の要素で評価される |
|
max<span class="hljs-comment">(lst, key=lambda x:x[1])</span> <span class="hljs-attr"># (2</span>, <span class="hljs-number">4</span>) 二つ目の要素で評価される |
|
</code></pre> |
|
<h1 id="-a-id-slice-a-"><a id="slice">スライス</a></h1> |
|
<pre><code class="lang-python">lst = <span class="hljs-string">[1, 2, 3, 4, 5, 6]</span> |
|
# lst<span class="hljs-string">[start:end:step]</span> |
|
lst<span class="hljs-string">[2:]</span> # <span class="hljs-string">[3, 4, 5, 6]</span> |
|
lst<span class="hljs-string">[:4]</span> # <span class="hljs-string">[1, 2, 3, 4]</span> |
|
lst<span class="hljs-string">[2:4]</span> # <span class="hljs-string">[3, 4]</span> |
|
lst<span class="hljs-string">[::2]</span> # <span class="hljs-string">[1, 3, 5]</span> |
|
lst<span class="hljs-string">[1::2]</span> # <span class="hljs-string">[2, 4,]</span> |
|
lst<span class="hljs-string">[2:4:2]</span> # <span class="hljs-string">[3]</span> |
|
</code></pre> |
|
<h1 id="-a-id-input-a-"><a id="input">入力</a></h1> |
|
<pre><code class="lang-python"><span class="hljs-meta"># N</span> |
|
N = <span class="hljs-keyword">int</span>(input()) |
|
|
|
<span class="hljs-meta"># A B</span> |
|
A, B = map(<span class="hljs-keyword">int</span>, input().split()) |
|
|
|
<span class="hljs-meta"># A_1 ... A_n</span> |
|
A = list(map(<span class="hljs-keyword">int</span>, input().split())) |
|
|
|
<span class="hljs-meta"># A_1 B_1</span> |
|
<span class="hljs-meta"># A_2 B_2</span> |
|
<span class="hljs-meta"># ...</span> |
|
<span class="hljs-meta"># A_n B_n</span> |
|
A = [] |
|
B = [] |
|
<span class="hljs-keyword">for</span> i in range(n): |
|
Ai, Bi = map(<span class="hljs-keyword">int</span>, input().split()) |
|
A.append(Ai) |
|
B.append(Bi) |
|
|
|
<span class="hljs-meta"># N A_1 ... A_n</span> |
|
N, *A = map(<span class="hljs-keyword">int</span>, input().split()) |
|
|
|
<span class="hljs-meta"># a_11 a_12 ... a_1w</span> |
|
<span class="hljs-meta"># a_21 a_22 ... a_2w</span> |
|
<span class="hljs-meta"># ..................</span> |
|
<span class="hljs-meta"># a_h1 a_h2 ... a_hw</span> |
|
a = [list(map(<span class="hljs-keyword">int</span>, input().split())) <span class="hljs-keyword">for</span> i in range(h)] |
|
<span class="hljs-meta"># a[y][x]となることに注意</span> |
|
</code></pre> |
|
<h1 id="-a-id-output-a-"><a id="output">出力</a></h1> |
|
<pre><code class="lang-python"><span class="hljs-meta"># 通常のものは省略</span> |
|
<span class="hljs-meta"># /を使ったときにfloor型になる。整数出力でないとWAになる問題があるので注意。</span> |
|
|
|
<span class="hljs-meta"># A_1 ... A_n</span> |
|
print(*A) # アスタリスクをつけると空白区切りで出力される |
|
</code></pre> |
|
<h1 id="-a-id-half-a-"><a id="half">二分探索</a></h1> |
|
<pre><code class="lang-python"><span class="hljs-meta"># めぐる式二分探索を採用</span> |
|
<span class="hljs-meta"># lst[index] >= key という条件を満たす最小の index を返す</span> |
|
|
|
def lower_case(lst, <span class="hljs-built_in">key</span>): |
|
ng = <span class="hljs-number">-1</span> |
|
ok = len(lst) |
|
<span class="hljs-keyword">while</span> <span class="hljs-built_in">abs</span>(ok - ng) > <span class="hljs-number">1</span>: |
|
mid = (ok + ng) <span class="hljs-comment">// 2</span> |
|
<span class="hljs-keyword">if</span> lst[mid] >= <span class="hljs-built_in">key</span>: |
|
ok = mid |
|
<span class="hljs-keyword">else</span>: |
|
ng = mid |
|
<span class="hljs-keyword">return</span> ok |
|
|
|
lst = [<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">5</span>, <span class="hljs-number">5</span>, <span class="hljs-number">9</span>] |
|
lower_case(lst, <span class="hljs-number">3</span>) <span class="hljs-meta"># 2 [1, 2, (2<n<=3), 3, 5] なので3を入れられる最小のindexは2</span> |
|
lower_case(lst, <span class="hljs-number">4</span>) <span class="hljs-meta"># 3</span> |
|
lower_case(lst, <span class="hljs-number">5</span>) <span class="hljs-meta"># 3</span> |
|
lower_case(lst, <span class="hljs-number">10</span>) <span class="hljs-meta"># 6</span> |
|
|
|
def upper_case(lst, <span class="hljs-built_in">key</span>): |
|
ng = <span class="hljs-number">-1</span> |
|
ok = len(lst) |
|
<span class="hljs-keyword">while</span> <span class="hljs-built_in">abs</span>(ok - ng) > <span class="hljs-number">1</span>: |
|
mid = (ok + ng) <span class="hljs-comment">// 2</span> |
|
<span class="hljs-keyword">if</span> lst[mid] > <span class="hljs-built_in">key</span>: |
|
ok = mid |
|
<span class="hljs-keyword">else</span>: |
|
ng = mid |
|
<span class="hljs-keyword">return</span> ok |
|
|
|
lower_case(lst, <span class="hljs-number">5</span>) <span class="hljs-meta"># 3</span> |
|
upper_case(lst, <span class="hljs-number">5</span>) <span class="hljs-meta"># 5</span> |
|
[<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, (lower_case), <span class="hljs-number">5</span>, <span class="hljs-number">5</span>, (upper_case), <span class="hljs-number">9</span>] この違い |
|
</code></pre> |
|
<h1 id="-a-id-sum-a-"><a id="sum">累積和</a></h1> |
|
<pre><code class="lang-python"><span class="hljs-comment"># 区間の総和を高速に求められる</span> |
|
|
|
<span class="hljs-comment"># [1, 2, 3, 4, 5]っていう配列があるとする</span> |
|
<span class="hljs-comment"># indexがlからrの区間の総和を求めるとき、配列を切り出してsum()する方法では大きい配列ではO(N(l-r))で遅い</span> |
|
<span class="hljs-comment"># なので累積和を使ってO(2*N)で求める</span> |
|
|
|
<span class="hljs-comment"># a = i番目までの配列の総和</span> |
|
lst = [<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">5</span>] |
|
<span class="hljs-keyword">a</span> = [] |
|
sumlst = <span class="hljs-number">0</span> |
|
<span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-built_in">len</span>(lst)): |
|
sumlst += lst[i] |
|
<span class="hljs-keyword">a</span>.append(sumlst) |
|
<span class="hljs-comment"># a => [1, 3, 6, 10, 15]</span> |
|
<span class="hljs-comment"># こうした前処理をすることで、lからrまでの総和をa[r] - a[l]で求められる</span> |
|
<span class="hljs-comment"># もちろん1から始まるindexなら-1をしておく</span> |
|
</code></pre> |
|
</body> |
スライスの仕方とかって書いたりはしませんか…?