読者です 読者をやめる 読者になる 読者になる

足跡-sokuseki-

りかの日進月歩の記録

もしも日付を約分することができたなら



というツイートが流れてきて、「日付を約分できたら1年はどんな感じになるのかなあ」と思ったのがきっかけ。





ということで、プログラムを書いて計算しました。検証は

  1. 1年間には何種類の日付が存在するのか
  2. 1年間は最短で何日と言えるのか

です。あらかじめ言っておきますが、ソースコードの可読性は低いです。はい。言語はc++です。



Q. 1年間には何種類の日付が存在するのか




結論から言うと、231日です。



解法1

素数を高速に求めるエラトステネスの篩っぽいやり方で計算してみた。

#include<iostream>
using namespace std;

int main(void) {
  int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                              
  int ans=0;
  int date[13][32]={};
  for(int i=1;i<=12;i++){
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      if(date[i][j])continue;
      ans++;
      for(int k=2;i*k<=12&&j*k<=days[i*k];k++)
        date[i*k][j*k]++;
    }
  }
  cout<<ans<<endl;
}
解法2

月と日の最大公約数が1のペアだけ数えればよくね?みたいになったので、gcdを計算する方法で書いた。
(互いに素の話をはじめに@kyo_math1729 さんがしていたのをすっかり忘れていた)

#include<iostream>
#include<algorithm>
using namespace std;

int main(void) {
  int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                              
  int ans=0;
  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      if(__gcd(i,j)==1)ans++;
    }
  cout<<ans<<endl;
}

__gcd関数って便利ですね。





Q. 1年間は最短で何日と言えるのか


これまた結論から言うと、4日です。
@asagi_a4ac さんの言う通り、1/1 -> 1/2 (2/4) -> 2/5 (12/30) ->12/31 が最短でした。

(追記:これは日付を巻き戻すことを考慮していません。なので、たとえば、1/31に行くときに1/1 -> 2/2 -> 2/1 -> 1/31 という動きかたはしないものとしています。)

解法1

再帰関数に突っ込むという方法。12/31から戻っていくと、貪欲に計算できます(たぶん)。

#include<iostream>
#include<algorithm>
using namespace std;

int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                                

int date_num(int month,int day){
  int same_month=month/__gcd(month,day);
  int same_day=day/__gcd(month,day);
  if(same_month==1 && same_day==1)return 1;
  if(same_day==1){
    return date_num(same_month-1,days[same_month-1])+1;
  }else{
    return date_num(same_month,same_day-1)+1;
  }
}

int main(void) {
  cout<<date_num(12,31)<<endl;
}
解法2
dp[i][j]:=i月j日にたどり着ける最短日数

として、DP(動的計画法)で求める方法。

#include<iostream>
#include<algorithm>

using namespace std;
#define INF 1e9


int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                                

int main(void) {
  int i,j;
  int dp[13][32];

  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++)
      dp[i][j]=INF; //初期化

  dp[1][1]=1;
  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      if(days[i]==j){
        if(i==12)break;
        dp[i+1][1]=min(dp[i+1][1],dp[i][j]+1);
        break;
      }
      dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1);
      for(int k=2;i*k<=12&&j*k<=days[i*k];k++)
        dp[i*k][j*k]=min(dp[i*k][j*k],dp[i][j]);
    }
  cout<<dp[12][31]<<endl;
}
おまけ

1年のそれぞれの日付が最短何日でたどり着けるのかを調べた。
使ったソースコードはこれ。最後の出力を少し変えただけ。

#include<iostream>
#include<algorithm>

using namespace std;
#define INF 1e9


int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                                

int main(void) {
  int i,j;
  int dp[13][32];

  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++)
      dp[i][j]=INF; //初期化

  dp[1][1]=1;
  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      if(days[i]==j){
        if(i==12)break;
        dp[i+1][1]=min(dp[i+1][1],dp[i][j]+1);
        break;
      }
      dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1);
      for(int k=2;i*k<=12&&j*k<=days[i*k];k++)
        dp[i*k][j*k]=min(dp[i*k][j*k],dp[i][j]);
    }

 for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      cout<<i<<"月"<<j<<"日は"<<dp[i][j]<<"日目"<<endl;
    }
}


で、結果はこうなりました。

1月1日は1日目
1月2日は2日目
1月3日は3日目
1月4日は4日目
1月5日は5日目
1月6日は6日目
1月7日は7日目
1月8日は8日目
1月9日は9日目
1月10日は10日目
1月11日は11日目
1月12日は12日目
1月13日は13日目
1月14日は14日目
1月15日は15日目
1月16日は16日目
1月17日は17日目
1月18日は18日目
1月19日は19日目
1月20日は20日目
1月21日は21日目
1月22日は22日目
1月23日は23日目
1月24日は24日目
1月25日は25日目
1月26日は26日目
1月27日は27日目
1月28日は28日目
1月29日は29日目
1月30日は30日目
1月31日は31日目

2月1日は32日目
2月2日は1日目
2月3日は2日目
2月4日は2日目
2月5日は3日目
2月6日は3日目
2月7日は4日目
2月8日は4日目
2月9日は5日目
2月10日は5日目
2月11日は6日目
2月12日は6日目
2月13日は7日目
2月14日は7日目
2月15日は8日目
2月16日は8日目
2月17日は9日目
2月18日は9日目
2月19日は10日目
2月20日は10日目
2月21日は11日目
2月22日は11日目
2月23日は12日目
2月24日は12日目
2月25日は13日目
2月26日は13日目
2月27日は14日目
2月28日は14日目

3月1日は15日目
3月2日は16日目
3月3日は1日目
3月4日は2日目
3月5日は3日目
3月6日は2日目
3月7日は3日目
3月8日は4日目
3月9日は3日目
3月10日は4日目
3月11日は5日目
3月12日は4日目
3月13日は5日目
3月14日は6日目
3月15日は5日目
3月16日は6日目
3月17日は7日目
3月18日は6日目
3月19日は7日目
3月20日は8日目
3月21日は7日目
3月22日は8日目
3月23日は9日目
3月24日は8日目
3月25日は9日目
3月26日は10日目
3月27日は9日目
3月28日は10日目
3月29日は11日目
3月30日は10日目
3月31日は11日目

4月1日は12日目
4月2日は13日目
4月3日は14日目
4月4日は1日目
4月5日は2日目
4月6日は2日目
4月7日は3日目
4月8日は2日目
4月9日は3日目
4月10日は3日目
4月11日は4日目
4月12日は3日目
4月13日は4日目
4月14日は4日目
4月15日は5日目
4月16日は4日目
4月17日は5日目
4月18日は5日目
4月19日は6日目
4月20日は5日目
4月21日は6日目
4月22日は6日目
4月23日は7日目
4月24日は6日目
4月25日は7日目
4月26日は7日目
4月27日は8日目
4月28日は7日目
4月29日は8日目
4月30日は8日目

5月1日は9日目
5月2日は10日目
5月3日は11日目
5月4日は12日目
5月5日は1日目
5月6日は2日目
5月7日は3日目
5月8日は4日目
5月9日は5日目
5月10日は2日目
5月11日は3日目
5月12日は4日目
5月13日は5日目
5月14日は6日目
5月15日は3日目
5月16日は4日目
5月17日は5日目
5月18日は6日目
5月19日は7日目
5月20日は4日目
5月21日は5日目
5月22日は6日目
5月23日は7日目
5月24日は8日目
5月25日は5日目
5月26日は6日目
5月27日は7日目
5月28日は8日目
5月29日は9日目
5月30日は6日目
5月31日は7日目

6月1日は8日目
6月2日は9日目
6月3日は10日目
6月4日は11日目
6月5日は12日目
6月6日は1日目
6月7日は2日目
6月8日は2日目
6月9日は2日目
6月10日は3日目
6月11日は4日目
6月12日は2日目
6月13日は3日目
6月14日は3日目
6月15日は3日目
6月16日は4日目
6月17日は5日目
6月18日は3日目
6月19日は4日目
6月20日は4日目
6月21日は4日目
6月22日は5日目
6月23日は6日目
6月24日は4日目
6月25日は5日目
6月26日は5日目
6月27日は5日目
6月28日は6日目
6月29日は7日目
6月30日は5日目

7月1日は6日目
7月2日は7日目
7月3日は8日目
7月4日は9日目
7月5日は10日目
7月6日は11日目
7月7日は1日目
7月8日は2日目
7月9日は3日目
7月10日は4日目
7月11日は5日目
7月12日は6日目
7月13日は7日目
7月14日は2日目
7月15日は3日目
7月16日は4日目
7月17日は5日目
7月18日は6日目
7月19日は7日目
7月20日は8日目
7月21日は3日目
7月22日は4日目
7月23日は5日目
7月24日は6日目
7月25日は7日目
7月26日は8日目
7月27日は9日目
7月28日は4日目
7月29日は5日目
7月30日は6日目
7月31日は7日目

8月1日は8日目
8月2日は9日目
8月3日は10日目
8月4日は11日目
8月5日は12日目
8月6日は13日目
8月7日は14日目
8月8日は1日目
8月9日は2日目
8月10日は2日目
8月11日は3日目
8月12日は2日目
8月13日は3日目
8月14日は3日目
8月15日は4日目
8月16日は2日目
8月17日は3日目
8月18日は3日目
8月19日は4日目
8月20日は3日目
8月21日は4日目
8月22日は4日目
8月23日は5日目
8月24日は3日目
8月25日は4日目
8月26日は4日目
8月27日は5日目
8月28日は4日目
8月29日は5日目
8月30日は5日目
8月31日は6日目

9月1日は7日目
9月2日は8日目
9月3日は9日目
9月4日は10日目
9月5日は11日目
9月6日は12日目
9月7日は13日目
9月8日は14日目
9月9日は1日目
9月10日は2日目
9月11日は3日目
9月12日は2日目
9月13日は3日目
9月14日は4日目
9月15日は3日目
9月16日は4日目
9月17日は5日目
9月18日は2日目
9月19日は3日目
9月20日は4日目
9月21日は3日目
9月22日は4日目
9月23日は5日目
9月24日は4日目
9月25日は5日目
9月26日は6日目
9月27日は3日目
9月28日は4日目
9月29日は5日目
9月30日は4日目

10月1日は5日目
10月2日は6日目
10月3日は7日目
10月4日は8日目
10月5日は9日目
10月6日は10日目
10月7日は11日目
10月8日は12日目
10月9日は13日目
10月10日は1日目
10月11日は2日目
10月12日は2日目
10月13日は3日目
10月14日は3日目
10月15日は2日目
10月16日は3日目
10月17日は4日目
10月18日は5日目
10月19日は6日目
10月20日は2日目
10月21日は3日目
10月22日は3日目
10月23日は4日目
10月24日は4日目
10月25日は3日目
10月26日は4日目
10月27日は5日目
10月28日は6日目
10月29日は7日目
10月30日は3日目
10月31日は4日目

11月1日は5日目
11月2日は6日目
11月3日は7日目
11月4日は8日目
11月5日は9日目
11月6日は10日目
11月7日は11日目
11月8日は12日目
11月9日は13日目
11月10日は14日目
11月11日は1日目
11月12日は2日目
11月13日は3日目
11月14日は4日目
11月15日は5日目
11月16日は6日目
11月17日は7日目
11月18日は8日目
11月19日は9日目
11月20日は10日目
11月21日は11日目
11月22日は2日目
11月23日は3日目
11月24日は4日目
11月25日は5日目
11月26日は6日目
11月27日は7日目
11月28日は8日目
11月29日は9日目
11月30日は10日目

12月1日は11日目
12月2日は8日目
12月3日は9日目
12月4日は9日目
12月5日は10日目
12月6日は10日目
12月7日は11日目
12月8日は11日目
12月9日は12日目
12月10日は12日目
12月11日は13日目
12月12日は1日目
12月13日は2日目
12月14日は2日目
12月15日は2日目
12月16日は2日目
12月17日は3日目
12月18日は2日目
12月19日は3日目
12月20日は3日目
12月21日は3日目
12月22日は4日目
12月23日は5日目
12月24日は2日目
12月25日は3日目
12月26日は3日目
12月27日は3日目
12月28日は3日目
12月29日は4日目
12月30日は3日目
12月31日は4日目

面白いですね。ちなみに2/29は2/28から遷移するので15日目のはずです。

感想

こういうクソくだらないことを考えるのが結構楽しい。