CodeFights, ArcadeモードIntroでのプログラミング問題演習第４週目です。使用言語はC++。今週でIntroの問題はほぼ終わりになりますが、気を抜かずじゃんじゃか解いて行こうと思います٩( 'ω' )و
37. arrayMaxConsecutiveSum
Given array of integers, find the maximal possible sum of some of its k consecutive elements.
自分の解答１
int arrayMaxConsecutiveSum(std::vector<int> a, int k) {
int ma = 0;
for (auto i = a.begin() ; i + k - 1 < a.end(); i++)
ma = max(ma, std::accumulate(i, i + k, 0));
return ma;
}
これでいけるかと思いきやこのエラーメッセージorz
Execution time limit exceeded on test 7: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input.
自分の解答２
もしかしてstd::accumulateが微妙に良くないのかとnested for-loop試したが別にそんなことはなかった。
int arrayMaxConsecutiveSum(std::vector<int> a, int k) {
int ma = 0;
for (int i = k -1; i < a.size(); i++){
int sum = 0;
for (int c = 0; c < k; c++)
sum += a[i - c];
ma = max(ma, sum);
}
return ma;
}
自分の解答３
最初に比べて行数は増えてしまったけど、なんとかいけた。各部分配列の和の求め方を変えました(sのところ)。
int arrayMaxConsecutiveSum(std::vector<int> a, int k) {
int ma = std::accumulate(a.begin(), a.begin() + k, 0);
int s = ma;
for (int i = k; i < a.size(); i++) {
s = s + a[i] - a[i - k];
ma = max(ma, s);
}
return ma;
}
別解
fyzixさんより。僕の最後の解答をもっと簡潔かつ綺麗にした感じ。
int arrayMaxConsecutiveSum(std::vector<int> inputArray, int k) {
int m, s = m = accumulate(&inputArray[0], &inputArray[k], 0);
for (int i = k; i < inputArray.size(); ++i)
m = max(m, s += inputArray[i] - inputArray[i-k]);
return m;
}
38. growingPlant
Each day a plant is growing by upSpeed meters. Each night that plant's height decreases by downSpeed meters due to the lack of sun heat. Initially, plant is 0 meters tall. We plant the seed at the beginning of a day. We want to know when the height of the plant will reach a certain level.
自分の解答
うまいこと一つの式でかかる日にち計算できないかと試してみましたがうまくいかなかったので素直にfor-loop使って解きました。
int growingPlant(int upSpeed, int downSpeed, int desiredHeight) {
int d = 1;
while(true){
desiredHeight -= upSpeed;
if (desiredHeight <= 0) return d;
desiredHeight += downSpeed;
d++;
}
}
別解
yasharさんより。綺麗。
int growingPlant(int u, int d, int g) {
if(u>=g)return 1;
return 1 + (g-u)/(u-d) + bool((g-u)%(u-d));
}
39. Knapsack Light
You found two items in a treasure chest! The first item weighs weight1 and is worth value1, and the second item weighs weight2 and is worth value2. What is the total maximum value of the items you can take with you, assuming that your max weight capacity is maxW and you can't come back for the items later?
Note that there are only two items and you can't bring more than one item of each type, i.e. you can't take two first items or two second items.
自分の解答
int knapsackLight(int v1, int w1, int v2, int w2, int maxW) {
if (w1 + w2 <= maxW) return v1 + v2;
else if (max(w1, w2) <= maxW) return max(v1, v2);
else if (w1 < w2 && w1 <= maxW) return v1;
else if(w2 < w1 && w2 <= maxW) return v2;
return 0;
}
別解
yasharさんより。こっちの方が条件文少ないから早い？
int knapsackLight(int value1, int weight1, int value2, int weight2, int maxW) {
if(weight1 + weight2 <= maxW)return value1 + value2;
int res = 0;
if(weight1<=maxW)
res = max(res,value1);
if(weight2<=maxW)
res = max(res,value2);
return res;
}
40. longestDigitsPrefix
Given a string, output its longest prefix which contains only digits.
Example:
For inputString="123aa1", the output should be
longestDigitsPrefix(inputString) = "123".
自分の解答
std::string ret, longestDigitsPrefix(std::string s) {
int i = 0;
while (isdigit(s[i++])) ret += s[i - 1];
return ret;
}
別解
sir_ementalerさんより。
std::string longestDigitsPrefix(std::string inputString) {
return inputString.substr(0, inputString.find_first_not_of("0123456789"));
}
std::string
メソッド忘れるなよー(T^T)
41. digitDegree
Let's define digit degree of some positive integer as the number of times we need to replace this number with the sum of its digits until we get to a one digit number.
Given an integer, find its digit degree.
自分の解答１
int digitDegree(int n) {
int t = 0, c = 0;
while (n > 9) {
while (n > 0) {t += n % 10; n /= 10;}
n = t;
t = 0;
c++;
}
return c;
}
自分の解答２
別解としてstd::accumulateをつかった解答を考えてみたのですが、stringに変換した数字をaccumulateで集計するとASCII Codeの和がsに保存されることがわかって断念。
int digitDegree(int n) {
string s = to_string(n);
int c = 0;
while (s.size() > 1) {cout << s << endl; s = accumulate(s.begin(), s.end(), 0); c++;}
cout << s << endl;
return c;
}
9 + 1がjになってる(^◇^;)
うまいこと"0"を引くとかして機能させられないかと考えてはみたのですがすぐに良い解決策は思いつきませんでしたorz
別解
fyzixさんより。for-loopの使い方。。。
int i, N, digitDegree(int n) {
for (;n>9;++i)
for (N = n, n = 0; N; N/=10) n += N%10;
return i;
}
42. Bishop and Pawn
Given the positions of a white bishop and a black pawn on the standard chess board, determine whether the bishop can capture the pawn in one move.
自分の解答
bool bishopAndPawn(std::string bishop, std::string pawn) {
return abs(bishop[0] - pawn[0]) == abs(bishop[1] - pawn[1]);
}
今回は特に別解なし。
43. isBeautifulString
A string is said to be beautiful if b occurs in it no more times than a; c occurs in it no more times than b; etc.
Given a string, check whether it is beautiful.
自分の解答
処理効率あげるなら最初のfor-loopで最大のASCII valueもつアルファベットの位置も保存しておいてあとのfor-loopで使うとか？🤔
bool isBeautifulString(std::string s) {
int count[26] = {0};
for (char c: s) ++count[c - 'a'];
for (int i = 1; i < 26; i++)
if (count[i - 1] < count[i]) return false;
return true;
}
別解
sir_ementalerさんより。is_sortedなんてメソッドあるのか…
bool isBeautifulString(std::string inputString) {
int o[26] {};
for (const auto& c : inputString) {
o[c - 'a']++;
}
return std::is_sorted(std::rbegin(o), std::rend(o));
}
std::is_sorted
Checks if the elements in range [first, last) are sorted in non-descending order.
<=でチェック
44.Find Email Domain
An email address such as "John.Smith@example.com" is made up of a local part ("John.Smith"), an "@" symbol, then a domain part ("example.com").
The domain name part of an email address may only consist of letters, digits, hyphens and dots. The local part, however, also allows a lot of different special characters. Here you can look at several examples of correct and incorrect email addresses.
Given a valid email address, find its domain part.
自分の解答
てっきり有効なメールかも確認しなきゃいけないと思ってregexと苦戦していた…必要なかったし、最後までエラー直せなかったし、正規表現ほんとによくわからない(-᷅_-᷄๑)
regexの部分は消して解答提出した後ctrl+zするつもりができなくなっていたので載せていないですorz
std::string findEmailDomain(std::string a) {
int p = a.find_last_of('@');
return a.substr(p + 1, a.size());
}
ちなみにa.size()なくてもstring aの最後までsubstrに含まれます。別解見るまで忘れていました。。
45. buildPalindrome
Given a string, find the shortest possible string which can be achieved by adding characters to the end of initial string to make it a palindrome.
自分の解答
rbegin()-iとしていたがために明らかにstの外からretに文字列ひっついてきてびっくりした。rbegin()をつかってる時は逆向きに進みたい時に整数を+する。
std::string ret, buildPalindrome(std::string st) {
for (int i = st.size(); i >= 0; i--){
ret = st + std::string(st.rbegin() + i, st.rend());
if (ret == std::string(ret.rbegin(), ret.rend())) return ret;
}
}
別解
Fredrik_Pさんより。
std::string buildPalindrome(std::string st) {
string ret(st);
auto it = st.begin();
while (ret != string(ret.rbegin(), ret.rend())) {
ret.insert(st.size(), 1, *it++);
}
return ret;
}
vector::insert
46. Elections Winners
Elections are in progress!
Given an array of the numbers of votes given to each of the candidates so far, and an integer k equal to the number of voters who haven't cast their vote yet, find the number of candidates who still have a chance to win the election.
The winner of the election must secure strictly more votes than any other candidate. If two or more candidates receive the same (maximum) number of votes, assume there is no winner at all.
自分の解答
とても回りくどい解き方をしてしまった気がする
int electionsWinners(std::vector<int> v, int k) {
std::sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++)
if (v[i] + k > v[v.size()-1]) return v.size() - i;
if (v[v.size() - 1] > v[v.size() - 2]) return 1;
return 0;
}
別解
条件演算子。
int electionsWinners(std::vector<int> votes, int k) {
int best = *std::max_element(votes.begin(), votes.end()) - k;
return k ?
std::count_if(votes.begin(), votes.end(), [=](int v) {
return v > best;
})
:
std::count(votes.begin(), votes.end(), best) == 1;
}
std::count, std::count_if
Returns the number of elements in the range [first, last) satisfying specific criteria.
47. Is MAC48 Address?
A media access control address (MAC address) is a unique identifier assigned to network interfaces for communications on the physical network segment.
The standard (IEEE 802) format for printing MAC-48 addresses in human-friendly form is six groups of two hexadecimal digits (0 to 9 or A to F), separated by hyphens (e.g. 01-23-45-67-89-AB).
Your task is to check by given string inputString whether it corresponds to MAC-48 address or not.
自分の解答
正規表現使って解こうとしたけどダメでしたorz
以前見た別解を参考にしつつやったのですがそもそもその文法を説明しているサイトを見つけられていないのでどこが間違っているのかわからない。なんで見つけられないの(´；ω；`)
bool isMAC48Address(std::string s) {
regex r ("[0-9A-F]{2}(-[0-9A-F]{2}){6}");
if(regex_match (s, r)) return true;
return false;
}
と思ってよく見たら{6}じゃなくて{5}だ。つら。。。
bool isMAC48Address(std::string s) {
regex r ("[0-9A-F]{2}(-[0-9A-F]{2}){5}");
return regex_match(s, r);
}
48. isDigit
Determine if the given character is a digit or not.
自分の解答
なんだったんだろうこの問題。。。
bool isDigit(char symbol) {
return std::isdigit(symbol);
}
別解
sir_ementalerさんより。関数のポインター？
int(*isDigit)(int) = std::isdigit;
まとめ
今日が日曜だと思っていたら月曜日でした。一昨日に春休み入ったばかりだというのに既に曜日感覚が狂っている。スタンド攻撃では？？