#94251 (Java) No.362 門松ナンバー

• 問題: No.362 門松ナンバー
• ユーザー: 37zigen
• 提出日時: 2016-05-26 23:51:48
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 163 ms / 3,000 ms
• コード長: 2,211 bytes
• コンパイル時間: 2,340 ms
• コンパイル使用メモリ: 78,872 KB
• 実行使用メモリ: 42,876 KB
• 最終ジャッジ日時: 2024-10-07 16:22:54
• 合計ジャッジ時間: 6,268 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 19

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package yukicoder;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        new Main().solve();
    }
    void solve(){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        /*
         *dp[一番左の桁の数][左から一つ右にずれた桁の数][桁数]=門松数の数
         *leading 0を許す。
         */
        long[][][] dp=new long[10][10][101];
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                if(i==j)continue;
                dp[i][j][2]++;
            }
        }
        for(int digit=3;digit<20;digit++){
            for(int i=0;i<10;i++){
                for(int j=0;j<10;j++){
                    for(int k=0;k<10;k++){
                        if(isKadomatsu(i,j,k)){
                            dp[i][j][digit]+=dp[j][k][digit-1];
                        }
                    }
                }
            }
        }
        //sum[i]:ちょうどi桁の門松数の数
        //leading 0を許さない
        long[] sum=new long[30];
        for(int digit=3;digit<30;digit++){
            for(int i=1;i<10;i++){
                for(int j=0;j<10;j++){
                    sum[digit]+=dp[i][j][digit];
                }
            }
        }
        for(int rep=0;rep<t;rep++){
            long k=sc.nextLong();
            int d=3;
            //k番目の門松数はd桁の数
            long s=0;
            for(;;d++){
                s+=sum[d];
                if(s>=k){
                    break;
                }
            }
            String ans="";
            long now=k;
            for(int i=d-1;i>=3;i--){
                now-=sum[i];
            }
            int pre1=-1;
            int pre2=-1;
            //leading 0を許さない。
            //最初の2桁を確定させる。
            out:for(int i=1;i<10;i++){
                for(int j=0;j<10;j++){
                    now-=dp[i][j][d];
                    if(now<=0){
                        now+=dp[i][j][d];
                        ans+=String.valueOf(i)+String.valueOf(j);
                        pre1=i;
                        pre2=j;
                        d-=1;
                        break out;
                    }
                }
            }
            out2:for(;d>=2;d--){
                if(d==2){
                    for(int i=0;i<10;i++){
                        if(isKadomatsu(pre1,pre2,i)){
                            now--;
                            if(now==0){
                                ans+=String.valueOf(i);
                                break out2;
                            }
                        }
                    }
                }
                out3:for(int i=0;i<10;i++){
                    if(isKadomatsu(pre1,pre2,i)){
                        now-=dp[pre2][i][d];
                        if(now<=0){
                            now+=dp[pre2][i][d];
                            ans+=String.valueOf(i);
                            pre1=pre2;
                            pre2=i;
                            break out3;
                        }
                    }
                }
            }
            System.out.println(ans);
        }
    }
    boolean isKadomatsu(int x,int y,int z){
        if(x==y||y==z||z==x)return false;
        if(x<y&&y>z)return true;
        if(x>y&&y<z)return true;
        return false;
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX