CodilityのLessonをやってみる（9-16）
前回の続き。
今回はLesson 9〜16までのeasyをやって行きます。
リポジトリ
Lesson 9 Maximum slice problem
最大スライス問題
MaxProfit
問題
配列AにはN個の整数が含まれている。これには連続したN日分の株価が収められている。
0<=P<Q<Nの時、P日に買ってQ日に売ったとして。A[Q]>=A[P]の場合、利益はA[Q]-A[P]となり、逆の場合はA[P]-A[Q]の損となる。
与えられたAの中で最大の利益はいくらか？
利益が出ない場合は0とする。
例
A[0] = 23171
A[1] = 21011
A[2] = 21123
A[3] = 21366
A[4] = 21013
A[5] = 21367
0日に買って2日に売った場合2048の損となる。なぜならA[2]-A[0]=21123-23171=-2048。
もし4日に買って5日売ったら354の利益となる。なぜならA[5]-A[4]=21367-21013=354。
考えられる最大の利益は356になる。これは1日に買って5日に売った場合である。
考え方
単純に考えれば、一番安い値段で買って一番高い値段で売れば良い。
日付の順なのでそのままの順番で比較する。
日付が移る毎に安い値段の確認と最高の利益の確認をする。
こんな感じになる。
def solution(A: [int]) -> int:
max_revenue = 0
min_value = 200000
for v in A:
if min_value > v:
min_value = v
else:
revenue = v - min_value
if revenue > max_revenue:
max_revenue = revenue
return max_revenue
これで一応100%。
計算量 O(N)
MaxSliceSum
問題
配列AにはN個の整数が含まれている。0<=P<=Q<Nの時、整数のペア(P,Q)は配列Aのスライスと呼ぶ。スライス(P,Q)の合計はA[P]+A[P+1]+...+A[Q]である。
Aの最大となるスライスは幾つか？
例
A[0] = 3 A[1] = 2 A[2] = -6
A[3] = 4 A[4] = 0
この場合答えは5になる。
- (3,4)は4
- (2,2)は-6
- (0,1)は5
- 他に(0,1)より大きくなるスライスはない
考え方
配列の中に負の数が入っていなければ問題は簡単。全部足せば良い。
負の数が入っているので、負にならない部分を足すことにする。
左（添字の0）から順番に足していき最大値を記憶しておく、合計が負になってしまったらその次からまた順番に足していく。
3, 2, -6, 4, 0 max: 3
5, -6, 4, 0 max: 5
-1, 4, 0 max: 5
4, 0 max: 5
4 max: 5
コードにするとこんな感じ。
def solution(A: [int]) -> int:
max_value = -1000000
sum_value = 0
for i in A:
sum_value += i
if sum_value > max_value:
max_value = sum_value
if sum_value < 0:
sum_value = 0
return max_value
これで一応100%。
計算量 O(N)
Prime and composit numbers
素数と合成数
CountFactors
問題
正の整数NにN=DxMとなる正の整数Mがある場合、DはNの因数である。
与えられた正の整数Nの因数の数を求めよ。
例
24が与えられた場合答えは8である。
なぜなら24の因数は1, 2, 3, 4, 6, 8, 12, 24の8つあるから。
考え方
因数を求める。
例だと 1, 2, 3, 4, 6, 8, 12, 24で、これは 1x24, 2x12, 3x8, 4x6になる。
で、因数は片方がわかればもう片方もわかる。例だと1, 2, 3, 4がわかれば残りの4つもわかる。
ここで、因数の（1x24や2x12などの）組みの小さい方は、Nの平方根よりも小さくなる。
例えば36の場合は1, 2, 3, 4, 6が因数の小さい方で、この中で一番大きな6はちょうど36の平方根になる。
と言うわけで、あとは力技のループでNが割り切れるかどうかを確認する。
こんな感じになる。
平方根（sqrt）のためにmathをインポートしてる。
import math
def solution(N: int) -> int:
factors = {1, N}
s = math.sqrt(N)
for i in range(2, int(s) + 1):
if N % i == 0:
factors.add(i)
factors.add(int(N / i))
return len(factors)
これで一応100%。
計算量 O(sqrt(N))
感想
少し考えてもわからなかったので、とりあえず力技でやってみたら100%になった…
何か数学的に解ける気がするのだけど、本当はどうやって解くのだろう？
MinPerimeterRectangle
問題
与えられる整数Nはある四角形の面積を表している。
四角形の面積は辺の長をAとBとするとAxBであり、周囲の長さは2x(A+B)である。
面積Nの四角形の最小の周囲の長さを求めよ。四角形の辺は整数とする。
例
Nが30の場合、辺と周囲の長さは下記の通り
- (1, 30)の時周囲の長さは62
- (2, 15)の時周囲の長さは34
- (3, 10)の時周囲の長さは26
- (5, 6)の時周囲の長さは22
なので面積30の四角形の最小の周囲の長さは22。
考え方
四角形が正方形になる時が一番周囲の長さが短くなる。
Nの平方根をとって、そこに一番近いNを割り切れる整数を探す。
こんな感じになる。
import math
def solution(N: int) -> int:
s = int(math.sqrt(N))
for i in reversed(range(1, s + 1)):
if N % i == 0:
return (i + int(N / i)) * 2
return (1 + N) * 2
これで一応100%。
計算量 O(sqrt(N))
Lesson 12 Euclidean algorithm
ユークリッドの互助法
ChocolatesByNumbers
問題
正の整数NとMが与えられる。整数Nは円に入ったチョコレートを表し0からN-1の番号が振られている。あなたはチョコレートを食べ始める。チョコレートを食べたらは包み紙を残す。
あなたは0番のチョコレートから食べ始める。そして円の中にあるM-1個のチョコレートもしくは包み紙を飛ばして次のチョコレートを食べる。
もっと正確に言うと、もしX番のチョコレートを食べたら次は(X+M)%N番のチョコレートを食べる。
空の包み紙にぶつかったら食べるのを止める。
食べられるチョコレートはいくつか？
例
Nが10でMが4の場合、0, 4, 8, 2, 6の順にチョコレートを食べる。（その次は0に戻って包み紙なのでストップ）
この場合食べるチョコレートは5個。
考え方
まず10個のチョコレートを並べて行く。
そしてそれをM-1だけ進めながら食べる時、下記の図の下の段（M）の0の時が食べる時。
食べられるチョコレートの番号は上。
012345678901234567890123456789
01230123012301230123012301230123
Mを見ていくと0の時にチョコの番号は0, 4, 8, 2, 6, 0...
と言うわけで、チョコも飛ばす数もどっちも20の時に包み紙（2回目）になる。
これでNとMの最小公倍数が最初に包み紙にあうタイミングだとわかる。
それまでに食べたチョコの数は最小公倍数をMで割った数。
で、最小公倍数はN*M/最大公約数で求められる。
今回は10と4の最大公約数が2なので10x4/2で20。
これをMの4で割って答えは5。
最大公約数はLesson12の題名のユークリッドの互助法で求められる。
こんな感じになる。
def solution(N: int, M: int) -> int:
a = M * N
m = M
if N > M:
M, N = N, M
while N != 0:
M, N = N, M % N
return int(a / M / m)
これで一応100%。
計算量 O(log(N + M))
感想
レッスン12がEuclidean algorithmとなっていたのがほぼ解答を教えてくれている。
なんとなく読んだりしていたアルゴリズムの本とかが助けになった。
スワップ見難いかな？とも思うけどtempとか使うよりは綺麗に感じる。
Lesson 15 Caterpillar method
キャタピラ
無限軌道？
AbsDistinct
問題
N個の数が入った配列Aがある。配列は昇順に整列されている。この配列の絶対値の独立した数字の数を求める。
例
A[0] = -5
A[1] = -3
A[2] = -1
A[3] = 0
A[4] = 3
A[5] = 6
絶対値の独立した数字の数は5になる。
なぜなら配列Aの要素の絶対値は5, 3, 1, 0, 6の5種類だから。
考え方
Lesson 15はキャタピラなのでそれっぽく解くのが良いのだろうけど、集合型を使うと物凄く簡単に解ける。
こんな感じ。
def solution(A: [int]) -> int:
pool = set()
for i in A:
pool.add(abs(i))
return len(pool)
これで一応100%。
計算量 O(N) or O(N*log(N))
一応それっぽい考え方も。
ソートされていて、絶対値が同じかどうか？が問題になる。
と言うわけで、両端から比較しつつ真ん中に向けて走査して新しい数字ならカウントを増やす。同じならカウントしない。で、どんどん走査して両端が交わったら終了。
凄くややこしくなってしまったけど、こんな感じ。
def solution(A: [int]) -> int:
if len(A) == 1:
return len(A)
number_count = 1
last_value = abs(A[0]) if abs(A[0]) > abs(A[-1]) else abs(A[-1])
min_index = 0
max_index = len(A) - 1
while min_index <= max_index:
min_index_value = abs(A[min_index])
max_index_value = abs(A[max_index])
if min_index_value == max_index_value:
if min_index_value != last_value:
number_count += 1
last_value = min_index_value
min_index += 1
max_index -= 1
else:
if min_index_value > max_index_value:
if min_index_value != last_value:
number_count += 1
last_value = min_index_value
min_index += 1
else:
if max_index_value != last_value:
number_count += 1
last_value = max_index_value
max_index -= 1
return number_count
これで一応100%。
計算量 O(N) or O(N*log(N))
感想
わざわざ長く書いてみたコードも結局はキャタピラとは言い難い。
キャタピラなコードとは？
CountDistinctSlices
問題
整数MとN個の正の整数を含む配列Aがある。配列Aの全ての整数はMと同じか小さい。
整数のペア(P,Q)は0<=P<=Q<Nの場合、 配列Aのスライスと呼ばれる。スライスは要素A[P], A[P+1],...,A[Q]を含む。独立したスライスは他と違う数字のみを含むスライスである。これはスライスに含まれる数は一度きりしか出現しないと言うことである。
例
M=6
A[0] = 3
A[1] = 4
A[2] = 5
A[3] = 5
A[4] = 2
この場合、下記の9つの独立したスライスがある。
(0,0),(0,1),(0,2),(1,1),(1,2),(2,2),(3,3),(3,4),(4,4)
考え方
同じ数字が出てくるところまで走査して、出てきたら前に出てきた（添字が小さい方の）数字の後からまたカウントを始める。
イメージ的にはキャタピラと言うより尺取り虫。
- 端から同じ数に合うまでスライスの数を増やしながら進む。
- 読んだ数はプールに保存しておく。
- スライスの数は長さが増える毎に長さの数だけ増える。
1 1 slices: 1
2 1 + 2 slices: 3
3 1 + 2 + 3 slices: 6
4 1 + 2 + 3 + 4 slices: 10
- 同じ数に出会ったら、最初からその添字の場所までに読んだ数をプールから取り除く。
- 同じかずの場所を最初の場所として再度進む。
こんな感じになる。
def solution(M: int, A: [int]) -> int:
count = 0
index = 0
base = 0
pool = set()
while index < len(A):
while index < len(A) and A[index] not in pool:
count += index - base + 1
pool.add(A[index])
index += 1
while index < len(A) and A[base] != A[index]:
pool.remove(A[base])
base += 1
pool.remove(A[base])
base += 1
return min(count, 1000000000)
これで一応100%。
計算量 O(N)
感想
Mを使わずに解いている。
多分Mは集合型が使えない場合に配列をpool=[false]*Mとして集合型の代わりに使うのだろう。
CountTriangles
問題
N個の整数からなる配列Aがある。
下記の条件を満たす時、3つの組み合わせは三角形？である。
- 0 <= P < Q < R < N
- A[P] + A[Q] > A[R]
- A[Q] + A[R] > A[P]
- A[R] + A[P] > A[Q]
配列Aから三角形は幾つ作ることができるか。
例
A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 12
この場合三角形の条件を満たすのは(0,2,4),(0,2,5),(0,4,5),(2,4,5)の4つである。
考え方
ソートしてP<Q<Rの場合、A[P]+A[Q]>A[R]であれば三角形。
配列一番右のA[R]に対して、その左隣のA[Q]と一番左端のA[P]で比較を始めて、PをQに近づけていく。
P,Qが条件を満たしたらそれ以上のPは全て条件を満たすのでカウントして、Qを左にずらしてPは一番左から。
P,Qが条件を満たさずにRに届いたらQを左に動かす必要はなくRを左に移動して、QはRの左でPは一番左から。
イメージとしてはこんな感じ。
1, 2, 5, 8, 10, 12
P Q R
P Q R
P Q R +2
P Q R
P Q R
P Q R +1
P Q R
P Q R
P Q R
P Q R
P Q R +1
P Q R
P Q R
P Q R
P Q R
P Q R
コードに直すとこんな感じ。
sorted_a = sorted(A)
count = 0
for i in reversed(range(len(A))):
min_index = 0
max_index = i - 1
while min_index < max_index:
if sorted_a[min_index] + sorted_a[max_index] > sorted_a[i]:
count += max_index - min_index
max_index -= 1
else:
min_index += 1
return count
これで一応100%。
計算量 O(N**2)
感想
最初総当たりを試してみたら見事にパフォーマンスが20%だった…
結局いらない部分を計算しないようにしてみたけど何かもっと簡単にする方法がありそうな気がする。
Lesson 16 Greedy algorithms
貪欲法
MaxNonoverlappingSegments
問題
配列AとBを位置とした0からN-1の番号付けがされたN個のセグメントが線上に置かれている。
それぞれのI（0<=I<Nとする）はA[I]からB[I]へのセグメントIの位置である。
セグメントは終わりの値でソートされている。これは0<=K<N-1とするとB[K]<=B[K+1]になると言うことである。
2つのセグメントIとJ（I!=J）がもし同じ場所を共有する（A[I]<=A[J]<=B[I]もしくはA[J]<=A[I]<=B[J]）場合オーバラップすると言う。
2つのセグメントがオーバーラップする場所を持たない場合オーバーラップしないと言う。
オーバーラップしないで置ける最大のセグメントの数は？
例
A[0] = 1 B[0] = 5
A[1] = 3 B[1] = 6
A[2] = 7 B[2] = 8
A[3] = 9 B[3] = 9
A[4] = 9 B[4] = 10
線は(1,5), (3,6), (7,8), (9,9), (9,10)の5本。(9,9)は長さが0の線。
これらが重ならずに置けるのは(0,2,3), (0,2,4), (1,2,3), (1,2,4)の4通り。どれも置ける最大の数は3。
考え方
難しく考えずに順番に置いた場合に次が置けるかどうか確認する。
こんな感じになる。
def solution(A: [int], B: [int]) -> int:
if len(A) < 2:
return len(A)
count = 1
end_number = B[0]
for i in range(len(A)):
if A[i] > end_number:
count += 1
end_number = B[i]
return count
これで一応100%。
計算量 O(N)
TieRopes
問題
0からN-1の番号を付けられた配列Aで長さを与えられたロープがあり床に線上に並べられている。Iが0<=I<Nの場合、ロープIの長さはA[I]となる。
2本のロープIとI+1は隣同士になる。2本の隣同士のロープは互いに結ぶことができ、結ばれたロープの長さは両方のロープの長さの合計値である。結んだロープは更に他のロープと結ぶことができる。
与えられた整数Kと同じかより長くなるロープを上記のように結んで作成する場合に最大のロープの数を求める。
例
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 1
A[5] = 1
A[6] = 3
- A[1] + A[2] = 5
- A[4] + A[5] + A[6] = 5
3が答え。
考え方
これも難しく考えずに順番に紐の長さを足していきKを超えたらカウントする。
こんな感じになる。
def solution(K: int, A: [int]) -> int:
count = 0
index = 0
v_sum = 0
while index < len(A):
v_sum += A[index]
if v_sum >= K:
count += 1
v_sum = 0
index += 1
return count
これで一応100%。
計算量 O(N)
感想
これは問題の意味がわかっていない気がする。
例でA[0]+A[1]+A[2]が最初に出てくるK=4を超える長さのロープではないのか？
最後に
以上、レッスン9から16までのメモ。
難易度easyしかやっていないので幾つか飛ばしている問題がある。
easyでもパフォーマンスを100%にしようとすると結構大変。いくつかの問題はもっとスマートな解法がありそうな気もする。ただググってしまうと勿体無いのでもう少しシャワーやトイレで考えてみるつもり。
Discussion