https://codility.com/programmers/lessons/8
これは難しい問題でした。O(N)の答えが浮かばなかったので、ググってCodilityのオフィシャルの解答を見て参考にしました。
https://codility.com/media/train/solution-flags.pdf
ですが、とりあえず、問題をよりよく理解するために、少しずつ進めて行きましょう。
まず、この問題は置ける旗の数の最大を求めているだけで、実際にどういう組み合わせで置けるかということは気にしてません。
なので、次に気になることは、どこに最初の旗を置けば良いのかということですね。どうやって考えればいいのでしょうか。答えとしては、実際は常に最初のpeekから初めて良いのです。
こういう場合を考えましょう．もし最初のpeekがA[1]にあり、２番目がA[3]で、３番目がA[7]だとし、二つの旗の間の距離が３より大きくなければいけないとしましょう。当然、A[1]とA[3]の両方に旗を置くことは出来ません。ここで(A[1], A[7])も (A[3],A[7])も組み合わせとしては正しいですよね。前者は６の距離、後者は４の距離だから条件を満たしますね。
実際に、最初のpeekは２番目のpeekより３番目のピークからは遠い位置にありますから、最初に見つかったピークに置いて、その次にあるピークが近すぎたとしても、どちらかを選んでれば、結局は置ける旗の数はおなじになりますね。ですから、最初は一番目のpeek から旗を置いて行って構いません。
以降のpeekはどうでしょうか？同じことが言えますね。例えばA[13]とA[20]の間の距離は常にA[15]とA[20]の距離より大きいですから、同じことになります。
たぶん、一番簡単に考えるには、旗を右から左にずらして行くということを想像してみると良いと思います。まず、任意の正しくルールに従って配置された旗とpeekの組み合わせを考えてください。
最初の旗は何処にあっても最初のpeekへと左方向に動かせますね。なぜなら、最初の旗の左には他の旗はないし、右に有る２番目の端からは遠くなるだけなので 、左に動かしても距離の制約に違反することはないですね。
こんどは２番目の旗が、距離の制約に違反しないで動かせるなら、最初の端から一番短いpeekに動かしてみましょう。距離の制約に違反しないで動したので、最初の旗と２番目の旗の距離は問題ないということになりますね。３番目の端から見ると、２番目の旗は単に遠くにはなれて行ったことになるので、距離の制約に違反することはないですね。
このように、全ての旗を左に動かして行くことが出来るようにスライドして詰めて行くことができます。ここで、全く旗の数はかわってないですよね。
これから以下のことが言えます。常に最初のpeekに旗を置いて良い。そして一番近い距離の制約に違反しないpeekに次の旗をおいて順々に置いて行く。これでk本の旗がおけるかどうか、常にチェックできる。
それではこの方針で、一歩ずつコードを実装していきましょう。
(1) 簡単な解答
一番簡単な解答は下のようになります。まず、peekを全て見つけ、インデックスを保管しますね。そして与えられた旗の数が置けるかどうか、peek_cntから０まで旗の数を減らしつつチェックして行きます。一度でも置けたらそれが最大なので、そこで終わります。
当然と言えば当然ですが、パフォーマンスが低いので66%しかもらえません。なにか考えないと行けないですね。
#include <alloca.h>
int check(int k, int* peeks, int peek_cnt)
{
//if we have to put only one flag, it is always possible..
if (k == 1){
return 1;
}
//the first flag can be set.
int prev = peeks[0];
int rest = k - 1;
//check if this is true
int i = 1;
while (i < peek_cnt){
int curr = peeks[i];
if (curr - prev >= k){
prev = curr;
rest--;
//we consumed the all the flag.
if (rest == 0){
return 1;
}
}
i++;
}
return 0;
}
int solution(int A[], int N)
{
//the max number of the peeks is N / 2.
int* peeks = (int*)alloca(sizeof(int) * (N / 2) );
int peek_cnt = 0;
//let's find the peeks first.
int i;
for (i = 1; i < N - 1; i++){
if (A[i - 1] < A[i] && A[i] > A[i + 1]){
peeks[peek_cnt] = i;
peek_cnt++;
}
}
//we don't have to check when there is no peek found.
if (peek_cnt == 0){
return 0;
}
//check how many flags can be set...
int max_flags = 0;
for (int i = peek_cnt; i > 0; i--){
int ret = check(i, peeks, peek_cnt);
if (ret != 0){
max_flags = i;
break;
}
}
return max_flags;
}
(2) 二分法を使った解答
さて、ここで考えましょう。
まず、K本の旗が置けるなら(K > 1)のときですが、当然K - 1本の旗が置けますよね。一番最後の旗を置かなければ良いんですから。持って行く旗の数が減るということは旗と旗の距離は近くなってよいので、現状のまま最後の旗をとっても、距離の制約に違反することはないです。
逆にK本の旗が置けなかったということはK + 1本の旗もおけないですね。
ここで二分法をつかって探索して答えを得ることができます。二分法ですのでO(log N)で検索できますね。旗のチェックは一回でO(N)ですからO(N * log(N))の計算量になります。前のより随分ましになりましたね、前のは、Nに依存した形で（最大の可能なpeekの数はNに依存しますよね）、毎回peekの数分チェックするのでO(N^2)ですよね。
ここで、何が旗の数Kの上限になるか考えてみましょう。もし、旗をK本おクトすると、最初の旗と最後の旗の間で、距離の制約を満たす可能な最小の距離は(K - 1) * Kになりますね。（たとえば３本置くときは１、４、７が可能な最小の距離ですね）。
ここで、配列Aの左はじ、右はじはpeekにはなれないので、(K - 1) * K + 2 < Nという制約が出てきます。((K - 1) * K + 2 <= Nでないのは、０始まりの配列だからですね）
この式を変形していくと
(K - 1) * K + 2 < N
(K - 1) * K < N - 2
K - 1 < ((N - 2) / K)
K < ((N - 2) / K) + 1;
となります。
ということは、Kがsqrt(N - 2)の時を考えると、Kは((N - 2)/ K)と等しくなりますね。なぜならK^2 = N - 2だからです(両辺をKで割ればわかりますね。） ですから上の
K < ((N - 2)/ K) + 1という不等式は成り立ちますね。
Kは旗の数なので正の整数ですが、sqrt(N- 2)は整数にはならないかもしれません。でもこの場合でも、Kがsqrt(N- 2)より小さい整数ならば上の不等式は正しいですね。Kが小さくなると(N - 2) / Kは逆に大きくなりますね。
では逆にKを大きくできるでしょうか？Kは正の整数なので、sqrt(N - 2)より大きい次の整数はfloor(sqrt(N - 2)) + 1となります（floorは切り捨てです）。ここでX＝floor(sqrt(N - 2))となるXをつかってKをX+1で置き換えても、上の不等式が成り立つか見てみましょう。
X + 1 < ((N - 2) / (X + 1)) + 1
両辺に(X + 1)をかけて
(X + 1) ^ 2 < (N - 2) + (X + 1)
X^2 + 2X + 1 < (N - 2) + (X + 1)
次に両辺から(X + 1)を引きましょう
X^2 + X < N - 2
X + 1 > sqrt(N - 2)としたので（floor(sqrt(N -2)) + 1 > sqrt(N - 2)ですからね）X ^ 2 は N - 2よりおおきくなり、その結果この不等式は成り立たなくなりますね。
つまり、旗の本数の上限はsqrt(N - 2)であるということです(このときsqrt(N - 2)を含みません）。下のコードではループの インデックスに整数をつかっており、上限も整数にしたかったので、sqrt(N - 2)が整数の時はsqrt(N - 2) - 1を上限に、層でない場合はfloor(sqrt(N - 2)) + 1にしています。
もしここで、頂上の数がこれより小さかったら、それをさらに上限として使えばよいですね。
この方針で実装したのが下のコードになります。
ですが、問題の要求するO(N)ではなく、O(N log n)の解答なのに100%もらっていますね・・・C言語でやったので実行速度が速すぎたからでしょうか…pythonなどでは同じ方針でしっかりとO(N log N)とでるかもしれませんね
#include <math.h>
#include <alloca.h>
int check(int k, int* peeks, int peek_cnt)
{
//if we have to put only one flag, it is always possible..
if (k == 1){
return 1;
}
//the first flag can be set.
int prev = peeks[0];
int rest = k - 1;
//check if this is true
int i = 1;
while (i < peek_cnt){
int curr = peeks[i];
if (curr - prev >= k){
prev = curr;
rest--;
//we consumed the all the flag.
if (rest == 0){
return 1;
}
}
i++;
}
return 0;
}
int solution(int A[], int N)
{
//there is no peek if N < 3.
if (N < 3){
return 0;
}
//the max number of the peeks is always less than N / 2.
//Indeed, the max number of the peeks, (N - 3) / 2 + 1.
//Think of [0, 1] and then
//add [0, 1] on the left hand side and [0] on the right hand side...
int* peeks = (int*)alloca(sizeof(int) * (N / 2) );
int peek_cnt = 0;
//let's find the peeks first.
int i;
for (i = 1; i < N - 1; i++){
if (A[i - 1] < A[i] && A[i] > A[i + 1]){
peeks[peek_cnt] = i;
peek_cnt++;
}
}
//we don't have to check when there is no peek found.
if (peek_cnt == 0){
return 0;
}
//check how many flags can be set...
//this time we use the bisection algorithm
int max_flags = 0;
int min = 1; //as we have at least one peek, min can be 1.
//we need to round up the sqrt(N - 2) to make it an upper limit
double tmp1 = sqrt(N - 2);
int tmp2 = (int)tmp1;
//the belo code is to handle when N == 3. we don' want tmp to be 0.
int tmp = 1;
if (tmp1 > 1){
tmp = (tmp1 == tmp2 ? tmp2 - 1: tmp2 + 1);
}
int max = peek_cnt < tmp ? peek_cnt : tmp;
while(min <= max){
int k = (max + min) / 2;
int ret = check(k, peeks, peek_cnt);
//we failed to put k flags, then try to check a smaller value.
if (ret == 0){
max = k - 1;
}
//we succeed to put k flags, update the max_flags and try a larger value.
else {
min = k + 1;
max_flags = k;
}
}
return max_flags;
}
この解答はオフィシャルのCodilityによる解答を説明しています。
https://codility.com/media/train/solution-flags.pdf.
O(N)の解答が思いつかなかったので、参考にしました。
まず、いままでの解答ではpeekのインデックスを別の配列にしまってそれを順々にチェックしていましたね。これはpeekの数に依存する回数チェックしなければならないので、非効率ですね。
下の解答では、それぞれのA[n]の位置に対応する配列next_peekをつくり、そこに「Aの配列の同じ位置から次にあるpeekもしくはそこがpeekであれば自分自身をさすようにインデックスの値をしまって行く」事にしています。
例えばA[3],A[5] and A[8]がpeekならば、next_peek[2]とnext_peek[6]はそれぞれ、5と8という値が入ることになります。
この配列next_peekをつかって、配列の有る位置から、次にあるpeekを一回の配列アクセスで簡単に探せることになります。たとえば１の位置に旗を置いたとして次の旗の距離まで３だとすると、４の位置に４があればそこに置け、そうでなければ次に置ける位置のインデックスがしまわれているのですね。
この方針でやるとたとえば最大のsqrt(N - 2)までチェックするとして、旗が１本おけるかは１回のアクセスでわかり、２本おけるかは２回のアクセスでわかり、となるので、チェックにかかる全体の時間はO(1 + 2 + 3 + ....+ sqrt(N - 2）)となります。１が公差、初項１、項数sqrt(N - 2)の等差配列なので、合計値は
sqrt(N - 2) * (1 + sqrt(N - 2)) / 2
=sqrt(N - 2) + (N - 2) / 2
計算量ですから大きい方をとって定数を払うとNの計算量になりますね。
で、最初のnext_peekを作るところもO(N)ですから、これはO(N)の計算量という事になります。
これで１００％のスコアですね。
#include <alloca.h>
int solution(int A[], int N) {
//for N < 3, there can be no peak.
if (N < 3){
return 0;
}
int* next_peek = (int*)alloca(sizeof(int) * N);
//-1 stands for there is no more peek.
next_peek[N - 1] = -1;
//scan backwards
int peek_cnt = 0;
int i;
for (i = N - 2; i > 0; i--){
if (A[i - 1] < A[i] && A[i] > A[i + 1]){
next_peek[i] = i;
peek_cnt++;
}
else {
next_peek[i] = next_peek[i + 1];
}
}
next_peek[0] = next_peek[1];
//now let's check
int max_flags = 0;
for (i = 1; (i - 1) * i + 2 < N && i <= peek_cnt; i++){
int pos = 0;
int num = 0;
while (pos < N && num < i){
pos = next_peek[pos];
//we don't have any more peek. exit this loop.
if (pos == -1){
break;
}
//we can set a flag at the pos.
//increment pos to seek the next peek
num++;
pos += i;
}
max_flags = max_flags < num ? num : max_flags;
}
return max_flags;
}
(4) まとめ
Codilityと他の方の解答を検索してみてみたのですが、あまり正確でない答えや解説が書かれているのがわかりました。
たとえばCodilityの解答でも、sqrt(N)をsqrt(N - 2)のかわりに上限としてしまっていたりします。
また、最後の(3) O(N) の解答もCodilityは(i - 1) * i + 2 < N && i <= peek_cntとせず(i - 1) * i <= Nのようにしてしまっており、peek_cntが小さい場合にも無駄に調べてしまおうとします。
また(3)のコードを二分法を組み合わせて検索すると、(3)の旗が置けるかどうかという判定の仕方と二分法を組み合わせた方が実際には早くなりますね。
（前のでも、ネットでは前提条件を間違えているコードがあるのに１００％だしてる解答があったりして、本当に考えてコードを理解して書いてるのだろうか？というものがあったりしました。完全に理解しないで難しい問題がとけてるというのは怖いですね）
ついでに二分法で(3)の O(N)のコードを書き換えたものを下記に示します
#include <alloca.h>
int solution(int A[], int N) {
//for N < 3, there can be no peak.
if (N < 3){
return 0;
}
int* next_peek = (int*)alloca(sizeof(int) * N);
//-1 stands for there is no more peek.
next_peek[N - 1] = -1;
//scan backwards
int peek_cnt = 0;
int i;
for (i = N - 2; i > 0; i--){
if (A[i - 1] < A[i] && A[i] > A[i + 1]){
next_peek[i] = i;
peek_cnt++;
}
else {
next_peek[i] = next_peek[i + 1];
}
}
next_peek[0] = next_peek[1];
//now let's check
int max_flags = 0;
//use the bisection algorithm
int min = 1; //as we have at least one peek, min can be 1.
//we need to round up the sqrt(N - 2) to get the upper limit
double tmp1 = sqrt(N - 2);
int tmp2 = (int)tmp1;
//the belo code is to handle when N == 3. we don' want tmp to be 0.
int tmp = 1;
if (tmp1 > 1){
tmp = (tmp1 == tmp2 ? tmp2 - 1: tmp2 + 1);
}
int max = peek_cnt < tmp ? peek_cnt : tmp;
while (min <= max){
int k = (max + min) / 2;
//let's check if k flags can be set.
int pos = 0;
int num = 0;
while (pos < N && num < k){
pos = next_peek[pos];
if (pos == -1){
break;
}
num++;
pos += k;
}
//we failed to put k flags, then try to check a smaller value.
if (num < k){
max = k - 1;
}
//we succeed to put k flags, update the max_flags and try a larger value.
else {
min = k + 1;
max_flags = k;
}
}
return max_flags;
}
0 件のコメント:
コメントを投稿