結果
問題 | No.87 Advent Calendar Problem |
ユーザー |
![]() |
提出日時 | 2015-08-17 03:04:39 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 236 ms / 5,000 ms |
コード長 | 3,471 bytes |
コンパイル時間 | 2,195 ms |
コンパイル使用メモリ | 77,376 KB |
実行使用メモリ | 54,392 KB |
最終ジャッジ日時 | 2024-07-18 09:57:27 |
合計ジャッジ時間 | 7,254 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import java.util.Scanner;public class Main {public static long simulate_count(final long begin, final long end, final int init_days, final int correct){int days = init_days;long count = 0;for(long year = begin; year < end; year++){if(year % 400 == 0){days += 2;}else if(year % 100 == 0){days += 1;}else if(year % 4 == 0){days += 2;}else{days += 1;}days %= 7;if(days == correct){ count++; }}return count;}public static int simulate_days(final long begin, final long end, final int init_days, final int correct){int days = init_days;long count = 0;for(long year = begin; year < end; year++){if(year % 400 == 0){days += 2;}else if(year % 100 == 0){days += 1;}else if(year % 4 == 0){days += 2;}else{days += 1;}days %= 7;if(days == correct){ count++; }}return days;}public static boolean is_leap(long year){if(year % 400 == 0){return true;}else if(year % 100 == 0){return false;}else if(year % 4 == 0){return true;}else{return false;}}public static void main(String[] args){Scanner sc = new Scanner(System.in);final long N = sc.nextLong();final int DAYS = 7;final int correct_days = 3;int days = 3;int[] numbered = {1, 4, 100, 400};long[][][] counts = new long[2][numbered.length][DAYS];int[][][] next_days = new int[2][numbered.length][DAYS];boolean[][][] memoized = new boolean[2][numbered.length][DAYS];long answer = 0;for(long year = 2015; year <= N; ){final boolean is_leap = is_leap(year);if(year % 400 == 0 && (year + 400) <= N){if(!memoized[is_leap ? 1 : 0][3][days]){memoized[is_leap ? 1 : 0][3][days] = true;counts[is_leap ? 1 : 0][3][days] = simulate_count(year, year + 400, days, correct_days);next_days[is_leap ? 1 : 0][3][days] = simulate_days(year, year + 400, days, correct_days);}answer += counts[is_leap ? 1 : 0][3][days];days = next_days[is_leap ? 1 : 0][3][days];year += 400;}else if(year % 100 == 0 && (year + 100) <= N){if(!memoized[is_leap ? 1 : 0][2][days]){memoized[is_leap ? 1 : 0][2][days] = true;counts[is_leap ? 1 : 0][2][days] = simulate_count(year, year + 100, days, correct_days);next_days[is_leap ? 1 : 0][2][days] = simulate_days(year, year + 100, days, correct_days);}answer += counts[is_leap ? 1 : 0][2][days];days = next_days[is_leap ? 1 : 0][2][days];year += 100;}else if(year % 4 == 0 && (year + 4) <= N){if(!memoized[is_leap ? 1 : 0][1][days]){memoized[is_leap ? 1 : 0][1][days] = true;counts[is_leap ? 1 : 0][1][days] = simulate_count(year, year + 4, days, correct_days);next_days[is_leap ? 1 : 0][1][days] = simulate_days(year, year + 4, days, correct_days);}answer += counts[is_leap ? 1 : 0][1][days];days = next_days[is_leap ? 1 : 0][1][days];year += 4;}else{if(!memoized[is_leap ? 1 : 0][0][days]){memoized[is_leap ? 1 : 0][0][days] = true;counts[is_leap ? 1 : 0][0][days] = simulate_count(year, year + 1, days, correct_days);next_days[is_leap ? 1 : 0][0][days] = simulate_days(year, year + 1, days, correct_days);}answer += counts[is_leap ? 1 : 0][0][days];days = next_days[is_leap ? 1 : 0][0][days];year += 1;}}System.out.println(answer);}}