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

概要

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

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

ぜひ、いいねと思ったらスキお願いいたします！！！

問題

Q63：カレンダーの最大長方形

解答

ソースコード

#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=5;
int WEEKS=6;
int DAYS=7;

int month_days[]={31,28,31,30,31,30,31,31,30,31,30,31};
std::vector<int> holiday_year;
std::vector<int> holiday_month;
std::vector<int> holiday_day;

//ツェラーの公式で曜日を求める
int getDayOfWeek(int year,int month,int day){
   int y,m,d;
   y=year;
   m=month;
   d=day;
   if(m==1 || m==2){
       m+=12;
       y-=1;
   }
   
   int C=(int)floor(y/100);
   int Y=y%100;
   int h=((d+(int)floor(26*(m+1)/10)+Y+(int)floor(Y/4)+5*C+(int)floor(C/4)+5)%7+1)%7;
   
   return h;
}

//祝日かどうかをチェックする
bool checkholiday(int y,int m,int d){
   rep(i,holiday_year.size()){
       if(holiday_year[i]==y && holiday_month[i]==m && holiday_day[i]==d){
           return true;
       }
   }
   return false;
}

//最大の四角形の面積を求める
int calc_rect(std::vector<int> cal){
   int s=0;
   rep(i,WEEKS){//開始点の行
       rep(j,DAYS){//開始点の列
           repi(k,i,WEEKS+1){//終了点の行
               repi(l,j,DAYS+1){//終了点の列
                   bool is_weekend=true;
                   
                   //四角形の中に平日以外のものが含まれているかをチェック
                   repi(r,i,k+1){
                       repi(c,j,l+1){
                           if(cal[c+r*DAYS]==0){
                               is_weekend=false;
                           }
                       }
                   }
                   //四角形の大きさを求める
                   if(is_weekend){
                       s=max(s,(k-i+1)*(l-j+1));
                   }
               }
           }
       }
   }
   std::cout << s << std::endl;
   return s;
}

//カレンダーを作成する
int calc(int y,int m){
   //曜日の取得
   int youbi =getDayOfWeek(y,m,1);
   int wday=youbi;
   
   //閏年の補正
   int last_day=month_days[m-1];
   if(y%4==0 && m==2)last_day++;
   
   //平日は１、それ以外を0としてカレンダーの配列を作成
   std::vector<int> cal(6*7,0);
   rep(i,last_day){
       if(0<wday && wday<6 && !(checkholiday(y,m,i+1))){
           cal[youbi+i]=1;
       }
       wday=(wday+1)%DAYS;
   }

   return calc_rect(cal);
}

int main(void){
   //ファイルから祝日の読み取り
   std::ifstream ifs("q63.txt");
   if(!ifs)return 1;
   string str;
   while(getline(ifs,str,'/')){
       holiday_year.push_back(stoi(str));
       getline(ifs,str,'/');
       holiday_month.push_back(stoi(str));
       getline(ifs,str);
       holiday_day.push_back(stoi(str));
   }
   ifs.close();
   
   //2006年から2015年までを求める
   int ans=0;
   repi(i,2006,2016){
       repi(j,1,13){
           ans+=calc(i,j);
       }
   }
   std::cout << ans << std::endl;
   
}

実行結果

ツェラーの公式について

q63のカレンダーの問題を解くにあたり、曜日を求める必要がありました。曜日を求める方法は各言語によってバラバラだと思います。本書籍で扱っているRubyのDate、C++のchronoなどを使用することで求めることができます。

しかし、それでは他の言語で実装する際に、いちいち調べる日時のライブラリを調べる必要があります。（もちろん、それも勉強の一つなので悪いわけではありません）

今回はどの言語でも対応できるように、ツェラーの公式を用いて曜日を求めました。詳しい式の内容や証明はWikipediaを参照してください。わかりやすく書かれていると思います。

下記のコードはq63で使ったツェラーの公式のソースコードです。年、月、日の情報を与えることで、曜日を出力します。曜日は日曜日を０として、0~6で日曜日から土曜日を表します。

#include <bits/stdc++.h>
using namespace std;
int main(void){

   int y,m,d;
   y=2014;
   m=14;
   d=1;
   
   if(m==1 || m==2){
       m+=12;
       y-=1;
   }
   
   int C=(int)floor(y/100);
   int Y=y%100;
   int h=((d+(int)floor(26*(m+1)/10)+Y+(int)floor(Y/4)+5*C+(int)floor(C/4)+5)%7+1)%7;
   std::cout << h << std::endl;
}

今回の学び

・カレンダー系の問題は各言語にある日時系のライブラリを駆使したほうが簡単に実装できそう。C++はC++20以降のchrono関数にカレンダー型があるので、それが便利そう。（今回の環境はC++14のため断念）

・四角形の中に休日があるかどうかを調べるときは、find()で範囲を指定して実行した方が単純で早く求められそう（時間がある時に修正予定）。

・ツェラーの公式を用いて曜日を求める方法を理解した。Wikipediaにもあるようにプログラムで実行する場合は式が若干異なるので注意する。

参考文献

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

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