結果

問題 No.362 門松ナンバー
ユーザー takeya_okinotakeya_okino
提出日時 2019-06-29 19:43:46
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 5,065 bytes
コンパイル時間 2,320 ms
コンパイル使用メモリ 78,924 KB
実行使用メモリ 67,544 KB
最終ジャッジ日時 2024-07-02 05:39:22
合計ジャッジ時間 17,424 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 389 ms
61,504 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    long U = (long)Math.pow(10, 14);
    for(int i = 0; i < t; i++) {
      long k = sc.nextLong();
      long r = 0;
      long l = U;
      long ans = 0;
      while(l > r + 1) {
        long med = (r + l) / 2;
        long a = func(med);
        if(a > k) {
          l = med;
        } else {
          r = med;
        }
        ans = r;
      }
      System.out.println(ans);
    }
  }

  public static long func(long N) {
    String n = String.valueOf(N);
    int len = n.length();
    long[][][][][] dp = new long[len][4][10][10][2];
    if(len < 3) {
      return 0;
    } else {
      for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
          int p1 = 0;
          int p2 = 0;
          int p3 = 0;
          int d1 = Integer.parseInt(String.valueOf(n.charAt(1)));
          int d2 = Integer.parseInt(String.valueOf(n.charAt(2)));
          if(i > d1) {
            p1 = 1;
          } else if(i == d1) {
            if(j > d2) {
              p1 = 1;
            } else if(j == d2) {
              p2 = 1;
            } else {
              p3 = 1;
            }
          } else {
            p3 = 1;
          }
          int d0 = Integer.parseInt(String.valueOf(n.charAt(0)));
          if(p1 == 1) {
            for(int k = 0; k < d0; k++) {
              if(k == 0) {
                if(i == 0) {
                  if(j == 0) dp[2][0][i][j][1]++;
                  if(j != 0) dp[2][1][i][j][1]++;
                } else {
                  if(i != j) dp[2][2][i][j][1]++;
                }
              } else {
                if(((k > i) && (i < j) && (k != j)) || ((k < i) && (i > j) && (k != j))) dp[2][3][i][j][1]++;
              }
            }
          }
          if(p2 == 1) {
            for(int k = 0; k <= d0; k++) {
              if(k == 0) {
                if(i == 0) {
                  if(j == 0) dp[2][0][i][j][1]++;
                  if(j != 0) dp[2][1][i][j][1]++;
                } else {
                  if(i != j) dp[2][2][i][j][1]++;
                }
              } else if(k < d0) {
                if(((k > i) && (i < j) && (k != j)) || ((k < i) && (i > j) && (k != j))) dp[2][3][i][j][1]++;
              } else {
                if(((k > i) && (i < j) && (k != j)) || ((k < i) && (i > j) && (k != j))) dp[2][3][i][j][0]++;
              }
            }            
          }
          if(p3 == 1) {
            for(int k = 0; k <= d0; k++) {
              if(k == 0) {
                if(i == 0) {
                  if(j == 0) dp[2][0][i][j][1]++;
                  if(j != 0) dp[2][1][i][j][1]++;
                } else {
                  if(i != j) dp[2][2][i][j][1]++;
                }
              } else {
                if(((k > i) && (i < j) && (k != j)) || ((k < i) && (i > j) && (k != j))) dp[2][3][i][j][1]++;
              }
            }            
          } 
        }
      }
      for(int i = 1; i < len; i++) {
        int d = Integer.parseInt(String.valueOf(n.charAt(i)));
        // dp[i - 1][0][0][0][1]からの遷移
        dp[i][0][0][0][1] = dp[i - 1][0][0][0][1];
        for(int l = 1; l < 10; l++) {
          dp[i][1][0][l][1] += dp[i - 1][0][0][0][1];
        }
        // dp[i - 1][1][j][k][1]からの遷移
        for(int l = 1; l < 10; l++) {
          for(int j = 0; j < 10; j++) {
            for(int k = 0; k < 10; k++) {
              if(l != k) dp[i][2][k][l][1] += dp[i - 1][1][j][k][1];
            }
          }
        }

        // dp[i - 1][2][j][k][1]からの遷移
        for(int l = 1; l < 10; l++) {
          for(int j = 0; j < 10; j++) {
            for(int k = 0; k < 10; k++) {
              if(((j > k) && (k < l) && (l != j)) || ((j < k) && (k > l) && (l != j))) dp[i][3][k][l][1] += dp[i - 1][2][j][k][1];
            }
          }
        }        

        // dp[i - 1][3][j][k][0]からの遷移
        for(int l = 1; l < 10; l++) {
          for(int j = 0; j < 10; j++) {
            for(int k = 0; k < 10; k++) {
              if(((j > k) && (k < l) && (l != j)) || ((j < k) && (k > l) && (l != j))) {
                if(l == d) {
                  dp[i][3][k][l][0] += dp[i - 1][3][j][k][0];
                }
                if(l < d) {
                  dp[i][3][k][l][1] += dp[i - 1][3][j][k][0];
                }
              }
            }
          }
        }           

        // dp[i - 1][3][j][k][1]からの遷移
        for(int l = 1; l < 10; l++) {
          for(int j = 0; j < 10; j++) {
            for(int k = 0; k < 10; k++) {
              if(((j > k) && (k < l) && (l != j)) || ((j < k) && (k > l) && (l != j))) dp[i][3][k][l][1] += dp[i - 1][3][j][k][1];
            }
          }
        }        
      }
      long ret = 0;
      for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
          for(int k = 0; k < 2; k++) {
            ret += dp[len - 1][3][i][j][k];
          }
        }
      }
      return ret;
    }
  }
}
0