#304150 (Java21) No.1106 🦉 何事もバランスが大事

提出ソース

結果

問題	No.1106 🦉 何事もバランスが大事
ユーザー	yuppe19 😺
提出日時	2018-12-15 17:25:12
言語	Java21 (openjdk 21)
結果	AC
実行時間	164 ms / 2,000 ms
コード長	2,095 bytes
コンパイル時間	3,184 ms
コンパイル使用メモリ	79,148 KB
実行使用メモリ	42,752 KB
最終ジャッジ日時	2024-05-02 23:05:40
合計ジャッジ時間	17,742 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	135 ms 41,548 KB
testcase_01	AC	134 ms 40,976 KB
testcase_02	AC	132 ms 41,520 KB
testcase_03	AC	136 ms 41,824 KB
testcase_04	AC	162 ms 42,444 KB
testcase_05	AC	133 ms 41,152 KB
testcase_06	AC	134 ms 41,384 KB
testcase_07	AC	133 ms 41,572 KB
testcase_08	AC	133 ms 41,568 KB
testcase_09	AC	132 ms 41,204 KB
testcase_10	AC	122 ms 40,136 KB
testcase_11	AC	134 ms 41,164 KB
testcase_12	AC	136 ms 41,496 KB
testcase_13	AC	134 ms 41,172 KB
testcase_14	AC	133 ms 41,580 KB
testcase_15	AC	134 ms 41,560 KB
testcase_16	AC	133 ms 41,188 KB
testcase_17	AC	133 ms 41,424 KB
testcase_18	AC	132 ms 41,744 KB
testcase_19	AC	133 ms 41,344 KB
testcase_20	AC	133 ms 41,860 KB
testcase_21	AC	135 ms 41,356 KB
testcase_22	AC	120 ms 40,472 KB
testcase_23	AC	139 ms 41,676 KB
testcase_24	AC	136 ms 41,768 KB
testcase_25	AC	136 ms 41,932 KB
testcase_26	AC	161 ms 41,740 KB
testcase_27	AC	157 ms 41,900 KB
testcase_28	AC	156 ms 41,776 KB
testcase_29	AC	164 ms 42,544 KB
testcase_30	AC	161 ms 42,484 KB
testcase_31	AC	161 ms 42,744 KB
testcase_32	AC	158 ms 42,392 KB
testcase_33	AC	159 ms 42,204 KB
testcase_34	AC	162 ms 42,540 KB
testcase_35	AC	159 ms 42,396 KB
testcase_36	AC	158 ms 42,056 KB
testcase_37	AC	160 ms 42,364 KB
testcase_38	AC	160 ms 42,656 KB
testcase_39	AC	159 ms 42,052 KB
testcase_40	AC	162 ms 42,032 KB
testcase_41	AC	161 ms 42,496 KB
testcase_42	AC	161 ms 42,032 KB
testcase_43	AC	162 ms 42,324 KB
testcase_44	AC	160 ms 42,088 KB
testcase_45	AC	159 ms 42,056 KB
testcase_46	AC	160 ms 42,156 KB
testcase_47	AC	161 ms 41,776 KB
testcase_48	AC	159 ms 42,296 KB
testcase_49	AC	155 ms 42,020 KB
testcase_50	AC	160 ms 42,188 KB
testcase_51	AC	150 ms 42,432 KB
testcase_52	AC	159 ms 42,680 KB
testcase_53	AC	158 ms 42,752 KB
testcase_54	AC	157 ms 42,284 KB
testcase_55	AC	157 ms 42,456 KB
testcase_56	AC	160 ms 42,416 KB
testcase_57	AC	156 ms 42,472 KB
testcase_58	AC	158 ms 42,256 KB
testcase_59	AC	160 ms 42,324 KB
testcase_60	AC	160 ms 42,668 KB
testcase_61	AC	160 ms 42,624 KB
testcase_62	AC	157 ms 42,372 KB
testcase_63	AC	160 ms 42,488 KB
testcase_64	AC	160 ms 42,536 KB
testcase_65	AC	161 ms 42,584 KB
testcase_66	AC	164 ms 42,040 KB
testcase_67	AC	163 ms 42,056 KB
testcase_68	AC	159 ms 42,448 KB
testcase_69	AC	160 ms 42,444 KB
testcase_70	AC	160 ms 41,904 KB
testcase_71	AC	159 ms 42,432 KB
testcase_72	AC	162 ms 42,232 KB
testcase_73	AC	159 ms 42,376 KB
testcase_74	AC	159 ms 42,112 KB
testcase_75	AC	161 ms 42,548 KB
testcase_76	AC	156 ms 42,120 KB
testcase_77	AC	161 ms 42,492 KB
testcase_78	AC	156 ms 42,320 KB
testcase_79	AC	161 ms 41,996 KB
testcase_80	AC	158 ms 42,076 KB
testcase_81	AC	160 ms 42,568 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.*;
import java.util.*;
import java.util.stream.*;

import static java.lang.Math.*;

public class Main {
  Integer[] conv(long x, int base) {
    List<Integer> v = new ArrayList<>();
    while(x != 0) {
      int rem = (int)(x % base);
      if(rem > base / 2) { rem -= base; }
      v.add(rem);
      x -= rem;
      x /= base;
    }
    Collections.reverse(v);
    return v.toArray(new Integer[0]);
  }

  private long f(long x) {
    Integer[] a = conv(x, 5);
    int n = a.length;
    // dp[未満フラグ][先行ゼロを抜けたか][荷物側の分銅数][反対側の分銅数] := パターン数
    long[][][][] dp = new long[2][2][n+1][n+1];
    dp[0][0][0][0] = 1;
    for(int i=0; i<n; ++i) {
      long[][][][] ndp = new long[2][2][n+1][n+1];
      for(int less=0; less<2; ++less) {
        for(int nuke0=0; nuke0<2; ++nuke0) {
          for(int cntM=0; cntM<=n; ++cntM) {
            for(int cntP=0; cntP<=n; ++cntP) {
              if(dp[less][nuke0][cntM][cntP] == 0) { continue; }
              // [l, r]
              int l = nuke0==1 ? -2 : 0,
                  r = less ==1 ?  2 : a[i];
              for(int d=l; d<=r; ++d) {
                int nless   = less ==1 || d < a[i] ? 1 : 0,
                    n_nuke0 = nuke0==1 || d > 0    ? 1 : 0,
                    ncntM   = cntM + (d < 0 ? -d : 0),
                    ncntP   = cntP + (d > 0 ?  d : 0);
                if(ncntM > n) { continue; }
                if(ncntP > n) { continue; }
                ndp[nless][n_nuke0][ncntM][ncntP] += dp[less][nuke0][cntM][cntP];
              }
            }
          }
        }
      }
      dp = ndp;
    }
    long res = 0;
    for(int less=0; less<2; ++less) {
      for(int nuke0=0; nuke0<2; ++nuke0) {
        for(int cnt=1; cnt<=n; ++cnt) {
          res += dp[less][nuke0][cnt][cnt];
        }
      }
    }
    return res;
  }

  private void solve() {
    Scanner sc = new Scanner(System.in);
    long N = sc.nextLong();
    long res = f(N);
    System.out.println(res);
  }

  public static void main(String[] args) {
    new Main().solve();
  }
}

yukicoder

結果

テストケース

ソースコード