CodilityのLessonをやってみる（1-4）
CodilityのLessonをやり始めたのでメモ。
今回は取り敢えずLesson 1〜4までのeasyで。
リポジトリ
Lesson 1 Iterations
各レッスンに大枠の表題があるのだけど、微妙に理解できないものもある。
レッスン1はイテレーション。
BinaryGap
問題
与えられた整数Nを2進表記して1に挟まれた連続する0の数が一番多いものを返す。
例
9の場合。これは1001なので1に挟まれた連続する0は2個。
529の場合。これは1000010001なので1に挟まれた連続する0は左側の4つと右側の3つ。大きい方を選ぶので答えは4。
20は10100なので1に挟まれている0は左側の1つだけ。（右側の00は1に挟まれてはいない。）なので答えは1。
15は1111で0はなし。
32は100000で1に挟まれていないので0。
考え方
まずは与えられた数を2進数に直した場合のビット列を求める。与えられる数が[1..2,147,483,647]なので31ビットで表される。このことから2^0から2^30までの数でANDすればそのビットが0か1かが分かる。それを配列にするコードが以下。
n_bit_flags = [1 if N & 2**i else 0 for i in range(31)]
後は配列を順番に見ていって0が続く間はカウントして1が来たらそれまでの最大のカウントと比べて大きい方を最大値として控えておく。
気をつけるのは最初から0が来る場合。この場合の0は1で挟まれていないのでカウントしてはいけない。そのためにカウントしているかしていないかのフラグを用意して最初に1が来たところからカウントを始める。
最終的にこんな感じ。
def solution(N: int) -> int:
n_bit_flags = [1 if N & 2**i else 0 for i in range(31)]
max_count = 0
counting = False
count = 0
for bit in n_bit_flags:
if bit:
counting = True
if count > 0:
if max_count < count:
max_count = count
count = 0
else:
if counting:
count += 1
return max_count
これで100%の解答になった。
感想
フラグが気持ち悪い。
index(1)で最初の1が出るところまで飛ばすのもアリかと思ったけどなんか綺麗じゃない。
Lesson 2 Arrays
レッスン2は配列。問題は2つある。
CyclicRotation
問題
与えられた配列Aを与えられた数Kだけ右にシフトして、はみ出した分は左側から入れる。（右ローテート）
例
A = [3, 8, 9, 7, 6]
K = 3
の場合、一回づつローテートすると下記のようになる。
[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]
[9, 7, 6, 3, 8]が答えになる。
考え方
例を見てもわかるように、右シフトした時に右にはみ出したものを左側にくっ付ければ答えになる。
[x, x, x, 3, 8] | [9, 7, 6] -> [9, 7, 6][3, 8]
pythonだと配列はスライスで簡単に切って貼ってできるのでそのまま行う。
Kだけ右シフトして配列に残るのは配列の左側len(A)-K個。これがローテート後の配列の右側になる。
そして配列から押し出されるのは配列の右側のK個。これがローテート後の左側になる。
これをコードにしたのが以下。
right_array = A[:len(A) - K]
left_array = A[-K:]
answer = left_array + right_array
後は諸条件の対応。
配列の長さNもローテートの数Kも[0..100]なので0の場合の対応が必要。どちらも何もせずにAを返せば良い。
KがNよりも大きい場合はスライスの範囲が正しくなくなるので余計なローテートをなくすために剰余を使ってローテート数を求める。
最終的にはこんな感じ
a_length = len(A)
if a_length == 0 or K == 0:
return A
k = K % a_length
if k == 0:
return A
right_array = A[:a_length - k]
left_array = A[-k:]
return left_array + right_array
これで100%になる。
感想
pythonの配列のスライス、マイナスで逆向きに延びるのが好き。
OddOccurrencesInArray
問題
与えられた配列AにはN個の数字が入ってる。配列は奇数個の要素を含んでいて含まれている要素は1つを除いて同じ数字でペアを組む。ペアを組めない仲間外れの数字は何か？
例
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
という配列Aがあって、中の数字は9が0,2,4,6の4ヶ所、3が1,3の2ヶ所にある。7が5番目に1つしかないので7が答えになる。
考え方
配列を順番に見て、出てきた数字に「出て来た」「また出たので消えた」のフラグを与える。今回は集合（set）を使ってみる。
最初に何もない集合を作って、出て来た数字が集合になければ「出て来た」の動作としてそれを加える。出て来た数字が集合に既にあれば「また出て来たので消えた」の動作としてそれを集合から取り去る。
これを繰り返して最後に残っているのが奇数回現れた数字になる。
最終的にこんな感じ。
def solution(A: [int]) -> int:
pool = set()
for i in A:
if i in pool:
pool.remove(i)
else:
pool.add(i)
return pool.pop()
これで100%になる。
感想
集合型ありがとう！
ない場合はどうするか？配列を用意するのは力技過ぎる気がする。
Lesson 3 Time Complexity
レッスン3はややこしい時間？
問題は3つある。
FrogJmp
問題
カエルが道の向こう側へ渡ろうとしている。カエルは現在X地点にいてY地点丁度かそれよりも大きな値の場所へ行きたい。カエルは常に固定値Dだけジャンプする。
カエルが目的地へ到達するために必要な最小のジャンプの回数は何回か？
考え方
考え方も何も…という気もするが、移動に必要な距離を求めてそれをジャンプできる距離で割れば目的地へのジャンプ回数が求められる。小数点以下のジャンプが必要な場合はそれ以上先に進むということで整数へ切り上げれば良い。
pythonのintは切り捨てになるので必要な距離をジャンプの距離で割り切れなかった場合にジャンプ回数に1を加えるようにした。
最終的にこんな感じ。
def solution(X: int, Y: int, D: int) -> int:
distance = Y - X
jump = int(distance / D)
return jump + 1 if distance % D else jump
これで100%になる。
計算量 O(1)
PermMissingElem
問題
与えられた長さNの配列Aには範囲が[1..(N+1)]の整数が入っている。長さNに1からN+1の数なので1つ入り切らない。その配列に入っていない数を見つける問題。
例
A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
この場合長さは4で入っている数は[1..5]の範囲。
というわけで入っていない数は4が正解。
考え方
ソートしてしまう。
後は最初から順番に数が正しいかどうか確認する。
Nの範囲が[0..100,000]なので0の時に注意。
最終的にこんな感じ。
def solution(A: [int]) -> int:
A.sort()
for i in range(len(A)):
if i + 1 != A[i]:
return i + 1
return len(A) + 1
これで100%になる。
計算量 O(N) or O(N * log(N))
感想
この問題までは特にパフォーマンスを気にしなくても問題はなかったのだが、ついにこの問題でパフォーマンス20%のコードが誕生した。
その凄く素直なコードが以下。
for i in range(len(A)):
if i + 1 not in A:
return i + 1
return len(A) + 1
配列に要素があるかどうかの確認をinでやるのは遅い。
TapeEquilibrium
問題
テープの均衡。
空でないN個の整数が入った配列Aがある。これはテープの上に置かれた数字を表している。
任意の整数P（0 < P < N）がこのテープを2つに分ける。A[0], A[1], ..., A[P-1]とA[P], A[P+1], ..., A[N-1]になる。
この2つに分けられたテープ上のそれぞれの数字を足したものの差で最も小さいものは何か？
例
Aが下記の場合
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
テープは4通りに分けることができる。
P=1ならそれぞれの足した値は3と10になり差は7になる。
P=2ならそれぞれの足した値は4と9になり差は5になる。
P=3ならそれぞれの足した値は6と7になり差は1になる。
P=4ならそれぞれの足した値は10と3になり差は7になる。
というわけでP=3の時の1が答え。
考え方
問題はPの場所より左（添字の小さい方）の数の合計とPから右（添字の大きい方）の数の合計がなるべく同じになるPを求める問題。
左から（添字0から）順番に数を足していけば左側の合計は求められるが、その際に同時に右側の合計もわからないと差を求められない。
左がわかった時に右を求めるには、全部の合計から左の合計を引けば右の合計がわかる。
P=2
A[0] A[1] A[2] A[3] A[4]
3 1 2 4 3
3+1=4 | 2+4+3=9
sum(A)=13
right = sum - left
と言うわけで、最初に全部足してしまう。
後は最初から順番に数を足して行き（Pの左側を足したもの）、全部足した値からそれを引く（Pの右側を足したもの）。この2つの差を求めてそれまでで最も小さかった差と比べてそれよりも差が小さければ最も小さかった差をアップデート。
最終的に最も小さな差が求まる。
最終的にこんな感じ。
def solution(A: [int]) -> int:
a_sum = sum(A)
min_delta = 2000
left_sum = 0
for i in A:
left_sum += i
right_sum = a_sum - left_sum
delta = abs(left_sum - right_sum)
if delta < min_delta:
min_delta = delta
return min_delta
これで100%になる。
計算量 O(N)
Lesson 4 Counting Elements
要素を数える。
FrogRiverOne
問題
カエルが川の向こう岸に渡ろうとしている。カエルは川の片側（位置0）にいて逆側（位置X+1）に行きたい。川に木から葉っぱが落ちてくる。（カエルは落ちて来た葉っぱの上を飛び跳ねて向こう岸に行く）
与えられた配列Aは川に落ちてきた葉っぱの位置を表すN個の数字で埋められている。A[K]はK秒後に落ちて来た一枚の葉っぱの位置を表す。
カエルが向こう岸へ渡れる最短の時間を求める。カエルはこちら側から向こう岸（1からX）まで葉っぱが埋め尽くされた時に渡れる。川の流れる速さは無視して良い程度に小さい。一度川に落ちた葉っぱの位置は変わることがない。
🐸 -> 🐸
位置 0 1 2 3 4 5 6
秒 0 🍂
秒 1 🍂
秒 2 🍂
秒 3 🍂
秒 4 🍂
秒 5 🍂
秒 6 🍂
秒 7 🍂
例
X=5
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
この場合、場所1〜5全てに葉っぱが落ちてくるのは6秒後（A[6]）に場所5に落ちて来た時。
なので答えは6になる。
考え方
配列の中を順に見ていって1..X全てが出揃った時（index）が答え。
葉っぱが落ちてくる位置は[1..X]なので、集合型が使えるならそこに値を放り込んで大きさがXになったら全部埋まったと考えるのが簡単。
葉っぱが揃わずに向こう岸に渡れない場合は-1を返すのを忘れないように。
最終的にこんな感じ。
def solution(X: int, A: [int]) -> int:
pool = set()
for i, v in enumerate(A):
pool.add(v)
if len(pool) == X:
return i
return -1
これで100%になる。
計算量 O(N)
PermCheck
問題
順列は1..Nの数字がそれぞれ一回ずつ入っている配列。
大きさNの配列に1..Nの数字が1回ずつ入っているかどうかを確認する。
例
A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2
これは大きさ4の配列に1..4の数字が全部入っているから順列。
A[0] = 4
A[1] = 1
A[2] = 3
これは大きさ3の配列に1..3の数字が全部入ってないから順列でない。
考え方
順番に見ると簡単なのでまずはソート。
するとA[0]は必ず1になるはず。
さらにA[N-1]はNになるはず。
と考えて行くと0から配列を見ていってA[index]=index+1でない場合には順列でないことになる。最後までチェックできたら順列である。
最終的にこんな感じ。
def solution(A: [int]) -> int:
A.sort()
for i, v in enumerate(A):
if i + 1 != v:
return 0
return 1
これで100%になる。
計算量 O(N) or O(N * log(N))
最後に
以上、レッスン1から4までのメモ。
コーディングテストって言うの？面白い！
easyのレッスンだけやってるからだと思うけど、パズル感覚で解けるのが楽しい。
日曜日が雨だったのでじっくり遊んでしまった！
多分AtCoderとかはこれのすっごいことをやってるんだろうなと勝手に妄想。実際にやったことないけど何となく虎の穴的なイメージ。
それに比べるとpaizaはプログラムを学び始める人向けって感じ。何かの広告？で見てアカウント作ったことがあって、少しやってみたけど足し算ができるか？とかループが書けるか？みたいなものが次々と出てきて早々に辞めてしまった。が、今見てみたらかなり変わってる気がする…
Codility終わったらまたやってみようか。
と言うわけで、次回はLesson 5から8までを予定。
Discussion