1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に
というものがあったのでC++解いてみました。
最近プログラミングやってなくてライブラリの使い方を調べながらでしたし、使用した環境がアップグレードしたばっかりのFedora 22でVimのプラグインが動かなかったり、制限時間に追われて焦りまくってたので酷いコードになっております。
自分で解いてみたい方にとってこの記事はネタバレとなりますのでご注意ください。
（上記の理由によりあまり参考にならないコードだと思いますが…）

一応解くのは全部解けたんですが（いや一部アウトか…）、5問中4問終わるまでで1時間掛かってしまい、5問目だけで1時間半掛かってしまいました。
5問目は横着しようとした結果逆にやたらとコードが複雑になってしまいそのバグ取りに時間が掛かったんですが、スパッと諦めて別の方法で書きなおしたら10分くらいで書けました。
負け惜しみです。

コンパイラ（clang++）のバージョン。

clang version 3.5.0 (tags/RELEASE_350/final)
Target: x86_64-redhat-linux-gnu
Thread model: posix

全て -std=c++14 でコンパイル。
（特にC++14の機能を使ってるわけではない。はず。）

それでは以下コード。

問1

for, while, 再帰を使ってリストの合計を計算する関数を3つ作れ。

コメント

template使ってるところに余裕が感じられます。

#include <iostream>
#include <vector>

template<typename T>
T sum_by_for(std::vector<T> &list)
{
  T s = T(0);
  for (size_t i = 0; i < list.size(); ++i)
  {
    s += list[i];
  }
  return s;
}

template<typename T>
T sum_by_while(std::vector<T> &list)
{
  T s = T(0);
  size_t i = 0;
  while (i < list.size())
  {
    s += list[i];
    ++i;
  }
  return s;
}

template<typename T>
T sum_by_recursion(std::vector<T> &list, size_t base = 0)
{
  if (base >= list.size()) return 0;
  return list[base] + sum_by_recursion(list, base + 1);
}

int main()
{
  std::vector<double> list{1.0, 2.0, 3.0};
  std::cout << sum_by_for(list) << std::endl;
  std::cout << sum_by_while(list) << std::endl;
  std::cout << sum_by_recursion(list) << std::endl;
}

問2

2つのリストをPythonのzip関数のような感じで交互に混ぜて結合する関数を作れ。

コメント

この辺りでちょっと焦りつつありコードが微妙な感じになってきます。

#include<iostream>
#include<vector>

template<typename T>
std::vector<T> zip(std::vector<T> listA, std::vector<T> listB)
{
  std::vector<T> result;
  size_t iA = 0;
  size_t iB = 0;
  for (size_t i = 0; i < listA.size() + listB.size(); ++i)
  {
    if (i % 2 == 0) {
      if (iA < listA.size()) result.push_back(listA[iA++]);
      else result.push_back(listB[iB++]);
    } else {
      if (iB < listB.size()) result.push_back(listB[iB++]);
      else result.push_back(listA[iA++]);
    }
  }
  return result;
}

int main()
{
  std::vector<double> A{1.0, 2.0, 3.0};
  std::vector<double> B{1.5, 2.5, 3.5, 4.5, 5.5};
  auto list = zip(A, B);
  for (auto v: list)
  {
    std::cout << v << ", ";
  }
  std::cout << std::endl;
}

問3

フィボナッチ数を100番目まで計算するプログラムを作れ。

コメント

整数の範囲に気をつければフィボナッチ数の計算は簡単なんですが、100番目付近のフィボナッチ数は符号なし64ビット整数の範囲を超えるため、このプログラムでは最後のほうの出力が正しくありません。
ただ、出題者の意図として多倍長整数の実装まで求めてるようには思えないのでそのままです。

#include<iostream>
#include<vector>

template<typename T>
void fib(std::vector<T> &list, size_t limit = 100)
{
  if (list.size() == 0)
  { 
    list.push_back(0);
    list.push_back(1);
  } 

  while (list.size() < limit)
  {
    list.push_back(list[list.size() - 2] + list[list.size() - 1]);
  }
}

int main()
{
  std::vector<uint64_t> list;
  fib(list);
  for (auto v: list)
  {
    std::cout << v << ", ";
  }
  std::cout << std::endl;
}

問4

リスト内の数値を文字列的に結合して最大の数を返すプログラムを作れ。
（例: [30, 2, 51, 8] → 851302）

コメント

文字列に変換して最初の1文字で比較して大きい順に並び替えた後結合してるだけです。
ただ、cat_maxはstd::stringではなくて数値型で返すように書くべきだったかもしれません。
後で知ったのですが入力が[5, 50, 56]のような場合このコードではダメですね。
正解はコードの中に追記しました。

#include<iostream>
#include<vector>
#include<algorithm>

template<typename T>
bool a(T &left, T &right)
{
  auto ls = std::to_string(left);
  auto rs = std::to_string(right);
  return (ls.at(0) > rs.at(0));
  // 追記
  // ↑は間違い。↓のように書くべきでした。
  // return (ls + rs > rs + ls);
}

template<typename T>
std::string cat_max(std::vector<T> &list)
{
  std::sort(list.begin(), list.end(), a<T>);
  std::string result;
  for (auto v: list)
  {
    result += std::to_string(v);
  }
  return result;
}

int main()
{
  std::vector<uint64_t> list{50, 2, 1, 9};
  std::cout << cat_max(list) << std::endl;
}

問5

1から9までの各数を足したり引いたり結合したりして結果が100になる式を全て求めるプログラムを作れ。
（例: 12 + 3 – 4 + 5 + 67 + 8 + 9 = 100）

コメント

コメントでjudgeと書いてある部分に関して、最初横着して各数値を演算子の位置から算出しながら計算するコードを書いたのですが、やたらと複雑になって大変な事になってしまいました。
一回コードを捨てて、演算子と数値を混ぜこぜにしたリストを作るようにして、プログラミング言語を実装するときのようにパーサを適用すれば…と思いついたら一瞬でした。
hundredがhandredになってますね…ヤバい。

#include<iostream>
#include<vector>

#define NONE -0
#define PLUS -1
#define MINUS -2

void print(std::vector<int> &ops, int64_t sum)
{
  for (int i = 0; i < ops.size(); ++i)
  {
    if (ops[i] == PLUS) std::cout << " + ";
    if (ops[i] == MINUS) std::cout << " - ";
    std::cout << i + 1;
  }
  std::cout << " = " << sum << std::endl;
}

void one_handred(std::vector<int> &ops)
{
  if (ops.size() == 9)
  {
    // judge
    std::vector<int> exp;
    for (int i = 0; i < ops.size(); ++i)
    {
      exp.push_back(ops[i]);
      exp.push_back(i + 1);
    }

    int64_t sum = 0;
    int64_t num = 0;
    int op = PLUS;
    for (auto v: exp)
    {
      if (v == NONE) num *= 10;
      else if (v == PLUS || v == MINUS)
      {
        sum += (op == PLUS)?num:(-num);
        num = 0;
        op = v;
      }
      else
      {
        num += v;
      }
    }
    sum += (op == PLUS)?num:(-num);

    if (sum == 100)
    {
      print(ops, sum);
    }
    return;
  }
  
  for (int op = NONE; op >= MINUS; --op)
  {
    ops.push_back(op);
    one_handred(ops);
    ops.pop_back();
  }
}

int main()
{
  std::vector<int> ops{PLUS};
  one_handred(ops);
}