「プログラマ脳を鍛える数学パズル」を解いてみる上級編#1【アルゴリズム学習】

概要

翔泳社から出版されている「プログラマ脳を鍛える数学パズル」のプログラミング問題をC++で解きます。
この本ではRuby,JavaScript,Cでの解答はありますが、C++は載っていないため練習として解いてみようと思います。
記事、コード共にまだまだな部分も多いので、何かお気づきの点があれば、コメントお願いいたします。

入門編はコチラ
初級編はコチラ
中級編はコチラ

ぜひ、いいねと思ったらスキお願いいたします！！！
ついに上級編に突入しました！

問題１

Q57：あみだくじの横線

解答１

ソースコード
本では3つ目の解答として紹介されているものです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define repi(i,a,n) for(int i = (int)a; i < (int)(n); i++)
#define ll long long

int V=7;
int H=10;

//再帰的に横線を作成
void make_bars(int v,std::vector<int> h){
   std::vector<int> new_h(h.size()+v-1,0);
   
   //各横線のパターン数をカウント
   rep(i,v){
       rep(j,h.size()){
           new_h[i+j]+=h[j];
       }
   }
   
   //横線の数が既定の数になれば結果を表示して終了、そうでなければ、棒の数を増やして再帰
   if(v==V+1){
       std::cout << h[H] << std::endl;
   }else{
       make_bars(v+1,new_h);
   }
}
int main(void){
   std::vector<int> init(1,1);
   make_bars(1,init);
}

実行結果

問題２

Q58：最速の連絡網

解答２

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define repi(i,a,n) for(int i = (int)a; i < (int)(n); i++)
#define ll long long

int N=14;
//ループを回すかどうかをチェックするための関数
//誰からも連絡を受けていない連絡待ちの人がいる場合true、それ以外はfalseを返す
bool check(std::vector<std::vector<int>> s){
   int cnt=0;
   for (std::vector<int> i : s) {
       if(i[1]==N){
           cnt++;
       }
   }
   if(cnt==0){
       return true;
   }else{
       return false;
   }
}

int main(void){
   //初期状態の人数をセット　連絡待ちの人：連絡不要の人：連絡必要な人：先生の電話の回数
   std::vector<int> init={N,0,0,0};
   std::vector<std::vector<int>> status;
   status.push_back(init);
   int step=0;
   
   while(check(status)){
       std::vector<std::vector<int>> next_status;
       for (std::vector<int> s : status) {
           rep(b,s[1]+1){//他の生徒に連絡する人数
               rep(c,s[2]+1){//連絡が必要な生徒の人数
                   if(s[2]>0){//すでに連絡を受けている生徒がいる場合
                       if(s[0]-b-c+1>=0){//生徒から先生に連絡がある場合
                           std::vector<int> tmp={s[0]-b-c+1,s[1]+c,s[2]+b-1,s[3]+1};
                           next_status.push_back(tmp);
                       }
                   }
                   if(s[0]-b-c>=0){//生徒から先生への連絡がない場合
                       std::vector<int> tmp={s[0]-b-c,s[1]+c,s[2]+b,s[3]};
                       next_status.push_back(tmp);
                   }
                   if(s[0]-b-c-1>=0){//先生から生徒へ連絡がある場合
                       std::vector<int> tmp={s[0]-b-c-1,s[1]+c+1,s[2]+b,s[3]+1};
                       next_status.push_back(tmp);
                   }
               }
           }
       }
       
       //next_statusからstatusにあるものを削除
       for (std::vector<int> i : status) {
           for (int j = 0; j < next_status.size(); j++) {
               if(i==next_status[j]){
                   next_status.erase(next_status.begin()+j);
                   break;
               }
           }
       }
       
       //かぶりを削除
       sort(all(next_status));
       auto result = std::unique(all(next_status));
       next_status.erase(result, next_status.end());
       
       status=next_status;
       step++;
   }
   std::cout << step <<"分"<< std::endl;
   
   
   //先生が電話する回数が最小のものを表示
   int ans=N*2;
   for (std::vector<int> s : status) {
       if(s[1]==N){
           ans=min(ans,s[3]);
       }
   }
   std::cout << ans <<"回"<< std::endl;
   
}

実行結果

今回の学び

・あみだくじの問題は解く方法は本でも紹介されている通り数パターンあるが、今回実装した方法は知っているだけで、簡単かつ高速に解くことができる。

・q58について、生徒の状態に注目し、その状態の人数の変化をたどることで楽に実装することができる。問題文を読んだときは難しそうに感じたが、問題を解きやすいように変換することが重要だということを学んだ。

参考文献

「プログラマを鍛える数学パズル」著:増井敏克

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問