結果

問題 No.319 happy b1rthday 2 me
ユーザー ぴろず
提出日時 2015-12-12 00:55:20
言語 Java
(openjdk 23)
結果
AC  
実行時間 134 ms / 2,000 ms
コード長 1,574 bytes
コンパイル時間 2,128 ms
コンパイル使用メモリ 77,076 KB
実行使用メモリ 41,500 KB
最終ジャッジ日時 2024-09-15 08:31:22
合計ジャッジ時間 7,456 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package no319;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        System.out.println(count1(b) - count1(a-1) + count2(b) - count2(a));
    }
    
    //0 ~ n の数で12を含むものの数
    public static long count1(long x) {
        char[] s = String.valueOf(x).toCharArray();
        int n = s.length;
        long[][][][] dp = new long[2][n][10][n+1];
        dp[1][0][0][0] = 1;
        for(int i=0;i<n;i++) {
            for(int large=0;large<2;large++) {
                for(int twelve=0;twelve<n;twelve++) {
                    for(int j=0;j<=9;j++) {
                        if (dp[large][twelve][j][i] == 0) {
                            continue;
                        }
                        int max = large == 1 ? s[i] - '0' : 9;
                        for(int k=0;k<=max;k++) {
                            int nlarge = (large == 1 && k == s[i] - '0') ? 1 : 0;
                            int ntwelve = (j == 1 && k == 2) ? twelve + 1 : twelve;
                            dp[nlarge][ntwelve][k][i+1] += dp[large][twelve][j][i];
                        }
                    }
                }
            }
        }
        long ans = 0;
        for(int i=0;i<2;i++) {
            for(int j=1;j<n;j++) {
                for(int k=0;k<10;k++) {
                    ans += dp[i][j][k][n] * j;
                }
            }
        }
//      System.out.println("c1:" + x + "," + ans);
        return ans;
    }
    
    //0 ~ x の中で2で始まって2で終わるものの数
    public static long count2(long x) {
        long ans = 0;
        if (x >= 2) {
            ans++;
        }
        if (x >= 22) {
            ans++;
        }
        long y = 202;
        long powten = 10;
        while(x >= y) {
            ans += Math.min((x - y) / 10,powten - 1) + 1;
            y = y * 10 - 18;
            powten *= 10;
        }
//      System.out.println("c2:" + x + "," + ans);
        return ans;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0