こんにちは。そろそろ学校でテストが始まってきてやや緊張気味です。

CodeFights Arcadeモード Introでの問題演習３週目です。今回は試験的に、各項目のタイトルを問題のタイトルにし、問題も載せてみます。添えられた数字は問題番号です。では今週も張り切っていきます！

22. avoidObstacles

まずは問題文。訳したほうがいいのかどうか…とりあえずはなしで。

You are given an array of integers representing coordinates of obstacles situated on a straight line.
Assume that you are jumping from the point with coordinate 0 to the right. You are allowed only to make jumps of the same length represented by some integer.
Find the minimal length of the jump enough to avoid all the obstacles.

Example:
For inputArray = [5, 3, 6, 7, 9], the output should be
avoidObstacles(inputArray) = 4.
Check out the image below for better understanding:

[Input] array.integer inputArray
Non-empty array of positive integers.
Guaranteed constraints:
2 ≤ inputArray.length ≤ 10,
1 ≤ inputArray[i] ≤ 40.

自分の解答

int avoidObstacles(std::vector<int> a) {
    std::vector<bool> v(41, false); //数直線
    for(int i : a) v[i] = true; //障害物の位置だけtrue
    for(int c = 2; c <= 40; c++) { //cがジャンプ幅
        int j = 0; //数直線上の位置
        while(!v[j] && j < 41){ j +=c;} //ここで実際に数直線上を飛んでみてる。
//障害物に当たったら(つまりv[j]がtrueだったら)、あるいは当たらずに数直線の距離限界を超えられたらループを抜ける
        if(j >= 40) return c; //初めて障害物に当たらずに距離40の数直線を超えられた時のジャンプ幅を返す。
    }
}

あるジャンプ幅で飛んで、一度も障害物に当たらずに数直線の限界を超えたことが確認できたらその時のジャンプ幅を返せば良いと考えました。

別解

yasharさんより。

int avoidObstacles(std::vector<int> a) {
    for(int i = 1; ;++i) //iがジャンプ幅
    {
        int t = 1;
        for(int j:a)
            t = t && j%i;
        if(t)return i;
    }
}

あるジャンプ幅で飛ぶとして、それぞれの障害物にあたりうるかを調べ、どれにも当たらないことがわかればその時のジャンプ幅を返す。
- j % i
- これが0になる ＝ jをiで割り切れる ＝ iのジャンプ幅でjの位置にある障害物に当たってしまう。
- 1以上になる ＝ jをiで割り切れない ＝ iのジャンプ幅ならjの位置にある障害物に当たることはない。
- t && j%i
- 初めtは1だが、右辺の結果次第で０になりその後内側のループが終わって外のループに入り直すまで1に戻ることはない。つまり、一つでも障害物に当たるとわかったジャンプ幅では数直線を超えられないので、次のif文のreturn iを行うこともない。

感想

僕のがイメージ図をそのままプログラムにして障害物を実際の数直線に見立てた動的配列に配置しているのに対し、yasharさんは問題を数学？的に考えてより簡単に処理してる。すごい…どうすればこういう風に問題の見方を変えられるのだろう。数をこなすしかないのかな？

23. Box Blur

問題文

自分の解答

返す用の配列をあらかじめ初期値も与えて用意し、あとは普通にfor loopで各3*3ブロックの平均とって配列にぶっこむ。やたら長い行が平均とってるところです。地味に二次元配列の初期化方法忘れていたのでいい勉強になりました。

std::vector<std::vector<int>>  boxBlur(std::vector<std::vector<int>> image) {
    std::vector<std::vector<int>> ret (image.size()-2, std::vector<int>(image[0].size()-2, 0));
    for (int i = 2; i < image.size(); i++)
        for (int j = 2; j < image[0].size(); j++)
            ret[i - 2][j-2] = (image[i-2][j-2]+image[i-2][j-1]+image[i-2][j]+image[i-1][j-2]+image[i-1][j-1]+image[i-1][j]+image[i][j-2]+image[i][j-1]+image[i][j])/9;

    return ret;
}

別解

またyasharさん。ほぼほぼ自分と同じですが平均の求め方がはるかに綺麗でした。
i, jのfor loopで3*3の枠を固定したあと、さらにr, cのfor loopでその枠の中の要素を足し合わせてるみたいです。

std::vector<std::vector<int>> boxBlur(std::vector<std::vector<int>> m) {
    vector<vector<int>> a(m.size()-2,vector<int>(m[0].size()-2));
    for(int i = 0; i < a.size(); ++i)
        for(int j = 0; j < a[0].size(); ++j)
        {
            for(int r = 0; r < 3; ++r)
                for(int c = 0; c < 3; ++c)
                    a[i][j] += m[i+r][j+c];
            a[i][j] /= 9;
        }
    return a;
}

感想

for loopは重ねすぎないほうがいいっていう先入観にすっかりとらわれていました。処理の効率とかはまだよくわかりませんが、今回のような場合はコードの可読性を優先したほうがいいのでしょうか🤔

24.Minesweeper

問題

自分の解答

大量のif文を書くのが避けたかったので、matrixよりも一回り大きい二次元配列を用意してそこでまずいくつ地雷と隣接してるかの計算をしました。最後のfor-loopでvの外ひと枠を削ったものをretに代入しています。

std::vector<std::vector<int>> minesweeper(std::vector<std::vector<bool>> matrix) {
    std::vector<std::vector<int>> v(matrix.size()+2, std::vector<int>(matrix[0].size()+2, 0));
    for (int i = 0; i < matrix.size(); i++)
        for (int j = 0; j < matrix[0].size(); j++)
            if (matrix[i][j]) {
                for (int r = 0; r < 3; r++)
                    for (int c = 0; c < 3; c++) {
                        if (r == 1 && c == 1) continue;
                        ++v[i + r][j + c];
                    }
            }

    std::vector<std::vector<int>> ret(matrix.size(), std::vector<int>(matrix[0].size(), 0));
    for (int i = 0; i < matrix.size(); i++)
        for (int j = 0; j < matrix[0].size(); j++)
            ret[i][j] = v[i + 1][j + 1];
    return ret;
}

別解1

catromさんより。僕が地雷を見つけたらその周囲に＋１したのに対し、こちらではあるマス[i][j]の周りに地雷を見つけるごとに[i][j]のマスに＋１しています。より綺麗で見やすいし、わかりやすい。

std::vector<std::vector<int>> minesweeper(std::vector<std::vector<bool>> matrix) {
    vector < vector <int> > r (matrix.size(), vector <int> (matrix[0].size()));
    for(int i = 0; i < matrix.size(); i++) {
        for(int j = 0; j < matrix[0].size(); j++) {
            r[i][j] += i > 0 && j > 0 && matrix[i-1][j-1];
            r[i][j] += i > 0 && matrix[i-1][j];
            r[i][j] += i > 0 && j < matrix[0].size() - 1 && matrix[i-1][j+1];
            r[i][j] += j > 0 && matrix[i][j-1];
            r[i][j] += j < matrix[0].size() - 1 && matrix[i][j+1];
            r[i][j] += i < matrix.size() - 1 && j > 0 && matrix[i+1][j-1];
            r[i][j] += i < matrix.size() - 1 && matrix[i+1][j];
            r[i][j] += i < matrix.size() - 1 && j < matrix[0].size() - 1 && matrix[i+1][j+1];
        }
    }
    return r;
}

別解２

yasharさんより。長くごちゃごちゃすると思っていた条件文を見たことないものを使って綺麗にまとめていましたΣ(-᷅_-᷄๑)

std::vector<std::vector<int>> minesweeper(std::vector<std::vector<bool>> m) {
    vector<vector<int>> a(m.size(), vector<int>(m[0].size()));
    for(int i = 0; i < a.size(); ++i)
    {
        for(int j = 0; j < a[0].size(); ++j)
        {
            for(int r = -1; r < 2; ++r)
                for(int c = -1; c < 2; ++c)
                {
                    if(!(r|c))continue;
                    if(i+r>=0 and i+r<a.size() and j+c>=0 and j+c<a[0].size() && m[i+r][j+c])
                        ++a[i][j];
                }
        }
    }
    return a;
}

ビット処理包括的 OR 演算子: |

ビットごとの包括的 OR 演算子 ( | ) は、1 番目のオペランドの各ビットを 2 番目のオペランドの対応するビットと比較します。 どちらかのビットが 1 の場合、対応する結果のビットは 1 に設定されます。 それ以外の場合は、対応する結果ビットが 0 に設定されます。

ビットごとの包括的 OR 演算子のオペランドは両方とも整数型である必要があります。 オペランドには「Arithmetic Conversion (算術変換)」で説明している通常の算術変換が適用されます。

別解２の方では、地雷がある場所にはその地雷自身によって＋１しないのでそのチェックにこの演算子を使っているようです。

and

これなんだろう。調べてもビットANDや論理ANDしか出てこない。見た感じ&&と変わらなそうだけど…
wikipediaによればandは&&の代替表現だそう。

代替表現は、記号的に等価として扱われ、どこでも記号を代替表現に置き換えても問題ない。置き換える先は、演算子としてではなく記号として扱われる。

25. Array Replace

問題。配列の要素を置き換えるだけです。

Given an array of integers, replace all the occurrences of elemToReplace with substitutionElem.

自分の解答

raged-based for-loopですが、要素を変えなきゃいけないのでリファレンス&を使いました。

std::vector<int> arrayReplace(std::vector<int> inputArray, int elemToReplace, int substitutionElem) {
    for (int& i : inputArray) if (i == elemToReplace) i = substitutionElem;
    return inputArray;
}

別解

airjp73さんより。std::replaceを使っていました。(ちなみにリンク先のサイトに日本語訳版はあるのですが機械翻訳だったので英語の方を貼りました。)

std::vector<int> arrayReplace(std::vector<int> arr, int elemToReplace, int substitutionElem) {

    std::replace(arr.begin(), arr.end(), elemToReplace, substitutionElem);

    return arr;
}

26. evenDigitsOnly

問題

Check if all digits of the given integer are even.

自分の解答

whileの条件文、ダメもとで試したら通ってしまった。条件文に代入式いれると無限ループに入ると思ってたけど勘違い…？？

bool evenDigitsOnly(int n) {
    do {
        if (n % 10 % 2 != 0) return false;
    }while (n /= 10);
    return true;
}

別解

nishant_sharmaさんより。ビットAND演算子使えたなぁ

bool evenDigitsOnly(int n) {
    while(n){
        if(n&1) return false;
        n/=10;
    }
    return true;
}

27. variableName

問題文

Correct variable names consist only of English letters, digits and underscores and they can't start with a digit.

Check if the given string is a correct variable name.

自分の解答

忘れがちなのでcctypeのメソッド一覧を貼っておきます。

bool variableName(std::string name) {
    if (std::isdigit(name[0])) return false;
    for(char c: name) if (!(std::isalnum(c) || c == '_')) return false;
    return true;
}

別解

yasharさんより。regex誰か使ってそうだなーって思ってたらやはり使ってる方いた。前回後回しにしてしまったので今回はちゃんと調べてみる。

bool variableName(std::string name) {
    regex r("[_a-zA-Z][_a-zA-Z0-9]*");
    return regex_match(name,r);
}

正規表現 regex

標準C++の正規表現: ＜regex＞
C++ 正規表現で検索文字列の抽出／出現位置の判定【match_results／std::regex】

cpprefjp
regexオブジェクトの初期化の種類に関する情報がほぼ全く出てこないのだけどどうしてだろう…調べ方が悪いのかな_:(´ཀ`」 ∠):

とりあえずできる範囲で別解のほうを解釈すると、アンダースコアか小文字大文字のアルファベットで始まり、左記の文字あるいは数字で終わりまで続く照合パターンを２行目で作り、最後にregex_matchでname全体がその照合パターンに合致していればtrueを返す。かな…？

28. alphabeticShift

問題文

Given a string, replace each its character by the next one in the English alphabet (z would be replaced by a).

自分の解答

std::string alphabeticShift(std::string inputString) {
    for(char& c: inputString){
        if (c == 'z') c = 'a';
        else c++;
    }
    return inputString;
}

別解

chameleon_tartuさんより。

std::string alphabeticShift(std::string inputString) {
    for (int i = 0; i < inputString.size(); ++i) {
        inputString[i] = (inputString[i] + 1 - 'a') % 26 + 'a';
    }
    return inputString;
}

29. chessBoardCellColor

問題文

Given two cells on the standard chess board, determine whether they have the same color or not.
Example:
For cell1 = "A1" and cell2 = "C3", the output should be
chessBoardCellColor(cell1, cell2) = true.

自分の解答

マスの座標を色が濃いマスなら奇数、薄いなら偶数になるように直して、二つのマスが奇数か偶数かの判定を返しました。

bool chessBoardCellColor(std::string cell1, std::string cell2) {
    int c1 = cell1[0] - 'a' + cell1[1] - '0';
    int c2 = cell2[0] - 'a' + cell2[1] - '0';
    return (c1 & 1) == (c2 & 1);
}

別解

yasharさんより。もっとシンプルです。

bool chessBoardCellColor(std::string a, std::string b) {
    return (a[0]+a[1])%2 == (b[0]+b[1])%2;
}

30. Circle of Numbers

問題

Consider integer numbers from 0 to n - 1 written down along the circle in such a way that the distance between any two neighbouring numbers is equal (note that 0 and n - 1 are neighbouring, too).

Given n and firstNumber, find the number which is written in the radially opposite position to firstNumber.

Example:

For n = 10 and firstNumber = 2, the output should be
circleOfNumbers(n, firstNumber) = 7.

自分の解答

int circleOfNumbers(int n, int firstNumber) {
    if (firstNumber < n / 2) return firstNumber + n / 2;
    if (firstNumber >= n / 2) return firstNumber - n / 2;
}

別解

yasharさんより。よく思いつくなあ…

int circleOfNumbers(int n, int a) {
    return (a+n/2)%n;
}

31.depositProfit

問題

You have deposited a specific amount of dollars into your bank account. Each year your balance increases at the same growth rate. Find out how long it would take for your balance to pass a specific threshold with the assumption that you don't make any additional deposits.

自分の解答

int depositProfit(int deposit, int rate, int threshold) {
    int y = 0;
    double d = deposit;
    while (d < threshold) {
        d *= (1 + rate/100.0);
        y++;
    }
    return y;
}

別解

loren_hさんより。

int depositProfit(int deposit, int rate, int threshold) {
    double increase = (double)threshold / (double) deposit;
    double power = 1 + (double)rate/100;
    return ceil(log(increase)/log(power));
}

std::log

複素数の自然対数（ネイピア数 e を底とした対数）を得る。log は logarithm（対数）、あるいは、logarithmic function（対数関数）の略。

std::log10

おまけ

複素数の常用対数（10 を底とした対数）を得る。log は logarithm（対数）、あるいは、logarithmic function（対数関数）の略。

std::ceil

引数 x 以上で最小の整数値を得る。（天井関数）

std::floor

おまけ

引数 x 以下で最大の整数値を得る。（床関数)

32. absoluteValuesSumMinimization

自分の解答

中央値を返せば良い。

int absoluteValuesSumMinimization(std::vector<int> a) {
    return (a.size() & 1) == 0 ? a[a.size()/2 - 1] : a[a.size()/2];
}

C++ 演算子の優先順位と結合規則

ビットAND & の優先順位が等価比較 == より低いことを知らず、a.size() & 1を括弧で括らずにいたら出るはずの結果が出てこなくてめちゃくちゃ悩みました。ちなみに論理AND &&はさらに下。

別解

sir_ementalerさんより。そもそも条件?:を使わなくても中央値返せることに気づいてさらに凹むまでがセット…

int absoluteValuesSumMinimization(std::vector<int> a) {
    return a[(a.size() - 1) / 2];
}

33. stringsRearrangement

問題

Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character.

Example:
For inputArray = ["aba", "bbb", "bab"], the output should be
stringsRearrangement(inputArray) = false;

All rearrangements don't satisfy the description condition.

For inputArray = ["ab", "bb", "aa"], the output should be
stringsRearrangement(inputArray) = true.

Strings can be rearranged in the following way: "aa", "ab", "bb".

自分の解答

自力では解けませんでした。辛い。

bool stringsRearrangement(std::vector<std::string> a) {
    std::sort(a.begin(), a.end());    
    for (int i = 1; i < a.size(); i++)
        if (std::inner_product(a[i - 1].begin(), a[i - 1].end(), a[i].begin(), 0, std::plus<>(), std::not_equal_to<>()) != 1)
            return false;
    return true;
}

std::inner_product

Computes inner product (i.e. sum of products) or performs ordered map/reduce operation on the range [first1, last1) and the range beginning at first2.

別解1

catromさんより。while(next_permutation())で全てのstringの組み合わせについて調べて、隣り合わせのstringが全て一文字違いになった時にtrueを返す。そういった順列が一度も見つからなかったらループから抜けてfalseを返す。

bool stringsRearrangement(std::vector<std::string> inputArray) {
    while(next_permutation(inputArray.begin(), inputArray.end())) {
        bool flag = 1;
        for(int i = 0; i < inputArray.size() - 1; i++) {
            int c = 0;
            for(int j = 0; j < inputArray[i].size(); j++)
                if(inputArray[i][j] != inputArray[i+1][j]) c++;
            if(c != 1) flag = 0; 
        }
        if(flag) return 1;
    }
    return 0;
}

std::next_permutation

Rearranges the elements in the range [first,last) into the next lexicographically greater permutation.

A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare lexicographicaly to each other; The first such-sorted possible permutation (the one that would compare lexicographically smaller to all other permutations) is the one which has all its elements sorted in ascending order, and the largest has all its elements sorted in descending order.

If the function can determine the next higher permutation, it rearranges the elements as such and returns true. If that was not possible (because it is already at the largest possible permutation), it rearranges the elements according to the first permutation (sorted in ascending order) and returns false.

別解2

sir_ementalerさんより。一瞬別の言語かと思ったけど多分やっていることは別解１と同じはず。たぶん…。疲れてしまって調べる気力が湧かないので一旦次にいきます_:(´ཀ`」 ∠):

// Look ma, no literals
int y, k, d, i, p, stringsRearrangement(auto a) {
    for (auto z = a; !i | a != z; y |= k, next_permutation(begin(a), end(a)))
        for (s : p = - --k, a) {
            for (c : d = i = y, s)
                d -= c != a[p][i++];
            p += k;
            k &= !~d;
        }
    return y;
}

34.extractEachKth

問題

Given array of integers, remove each kth element from it.
Example:
For inputArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and k = 3, the output should be
extractEachKth(inputArray, k) = [1, 2, 4, 5, 7, 8, 10].

[execution time limit] 0.5 seconds (cpp)
Guaranteed constraints:
5 ≤ inputArray.length ≤ 15,
-20 ≤ inputArray[i] ≤ 20.
1 ≤ k ≤ 10.

自分の解答

std::vector<int> extractEachKth(std::vector<int> inputArray, int k) {
    for (int n = k * (inputArray.size() / k) - 1; n >= 0; n -= k)
        inputArray.erase(inputArray.begin() + n);
    return inputArray;
}

別解

yasharさんより。inputArrayから消すのではなく、消すべき要素を飛ばして新しい配列を作って返す。

std::vector<int> a, extractEachKth(std::vector<int> s, int k) {
    int n = s.size();
    for(int i = 0; i < n; ++i)
        if((i+1)%k)
            a.push_back(s[i]);
    return a;
}

35.firstDigit

問題

Find the leftmost digit that occurs in a given string. A string contains at least one digit.

自分の解答

char firstDigit(std::string inputString) {
    for (char c: inputString) if (std::isdigit(c)) return c;
}

別解

sir_ementalerさんより。

char firstDigit(std::string inputString) {
    return inputString[inputString.find_first_of("0123456789")];
}

std::basic_string::find_first_of

Finds the first character equal to one of the characters in the given character sequence. The search considers only the interval [pos, size()). If the character is not present in the interval, npos will be returned.

36. differentSymbolsNaive

問題

Given a string of lowercase English letters, find the number of different characters in it.

自分の解答

int differentSymbolsNaive(std::string s) {
    std::vector<int> a(26, 0);
    for (char c: s) ++a[c - 'a'];
    int n = 0;
    for (int i: a) if (i > 0) ++n;
    return n;
}

別解

sir_ementalerさんより。

int differentSymbolsNaive(std::string s) {
    return std::set<char>(s.begin(), s.end()).size();
}

std::set

std::set is an associative container that contains a sorted set of unique objects of type Key.

あとがき

今回は第22〜36問までの15問を解きました。残り半分も楽しんで解いていきたいと思います( ´ ▽ ` )

ではまた来週。