もしも日付を約分することができたなら
あーーもう3/27か
— うし (@ei1333) 2017年3月27日
約分して1/9にしたい（また春休みが来るので
— うし (@ei1333) 2017年3月27日
というツイートが流れてきて、「日付を約分できたら1年はどんな感じになるのかなあ」と思ったのがきっかけ。
日付を約分できるとして、約分前と約分後の日付を同一視できるとすれば、1年は何日になるのだろうか……
— りかさん (@wk1080id) 2017年3月27日
@wk1080id 9日で年末に行けますね
— 浅葱 #けもフレの5話の活気を取り戻せ (@asagi_a4ac) 2017年3月27日
1/1,1/2=12/24,12/25,12/26,12/27,12/28,12/29,12/30,12/31
あー何種類の日付があるのかみたいなことを考えてました https://t.co/dOSNtIVPxg
— りかさん (@wk1080id) 2017年3月27日
@wk1080id 日と月が互いに素なものを数えればいいからオイラーのトーティエント関数とかで計算できそう(したくはない)
— ε (@kyo_math1729) 2017年3月27日
@asagi_a4ac @wk1080id 1/1,1/2=2/4,2/5=12/30,12/31の4日が最短っぽそう
— かっさ(Yang33) (@__KasSA) 2017年3月27日
ということで、プログラムを書いて計算しました。検証は
- 1年間には何種類の日付が存在するのか
- 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日目のはずです。
感想
こういうクソくだらないことを考えるのが結構楽しい。
