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

提出ソース

結果

問題	No.1106 🦉 何事もバランスが大事
ユーザー	yuppe19 😺
提出日時	2018-12-15 17:25:12
言語	Java (openjdk 23)
結果	AC
実行時間	166 ms / 2,000 ms
コード長	2,095 bytes
コンパイル時間	4,691 ms
コンパイル使用メモリ	79,856 KB
実行使用メモリ	42,624 KB
最終ジャッジ日時	2024-11-23 18:28:30
合計ジャッジ時間	19,455 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	130 ms 41,416 KB
testcase_01	AC	135 ms 41,024 KB
testcase_02	AC	129 ms 40,920 KB
testcase_03	AC	131 ms 41,464 KB
testcase_04	AC	156 ms 42,160 KB
testcase_05	AC	130 ms 41,180 KB
testcase_06	AC	128 ms 40,948 KB
testcase_07	AC	119 ms 39,840 KB
testcase_08	AC	132 ms 41,232 KB
testcase_09	AC	129 ms 41,084 KB
testcase_10	AC	128 ms 41,304 KB
testcase_11	AC	130 ms 41,300 KB
testcase_12	AC	130 ms 41,360 KB
testcase_13	AC	132 ms 41,580 KB
testcase_14	AC	133 ms 41,572 KB
testcase_15	AC	133 ms 41,456 KB
testcase_16	AC	133 ms 41,388 KB
testcase_17	AC	133 ms 41,460 KB
testcase_18	AC	135 ms 41,620 KB
testcase_19	AC	121 ms 40,372 KB
testcase_20	AC	135 ms 41,524 KB
testcase_21	AC	136 ms 41,360 KB
testcase_22	AC	137 ms 41,404 KB
testcase_23	AC	140 ms 41,740 KB
testcase_24	AC	143 ms 41,748 KB
testcase_25	AC	140 ms 41,520 KB
testcase_26	AC	160 ms 42,200 KB
testcase_27	AC	160 ms 42,476 KB
testcase_28	AC	159 ms 42,180 KB
testcase_29	AC	162 ms 42,204 KB
testcase_30	AC	158 ms 42,040 KB
testcase_31	AC	159 ms 42,260 KB
testcase_32	AC	159 ms 42,332 KB
testcase_33	AC	159 ms 41,804 KB
testcase_34	AC	157 ms 41,832 KB
testcase_35	AC	160 ms 42,244 KB
testcase_36	AC	159 ms 42,136 KB
testcase_37	AC	156 ms 42,376 KB
testcase_38	AC	161 ms 42,096 KB
testcase_39	AC	161 ms 42,160 KB
testcase_40	AC	158 ms 42,348 KB
testcase_41	AC	152 ms 41,972 KB
testcase_42	AC	157 ms 41,832 KB
testcase_43	AC	165 ms 42,208 KB
testcase_44	AC	161 ms 41,932 KB
testcase_45	AC	157 ms 42,012 KB
testcase_46	AC	153 ms 42,340 KB
testcase_47	AC	152 ms 42,080 KB
testcase_48	AC	163 ms 42,172 KB
testcase_49	AC	155 ms 41,796 KB
testcase_50	AC	158 ms 42,108 KB
testcase_51	AC	155 ms 41,808 KB
testcase_52	AC	152 ms 42,044 KB
testcase_53	AC	152 ms 42,196 KB
testcase_54	AC	153 ms 42,076 KB
testcase_55	AC	154 ms 41,988 KB
testcase_56	AC	166 ms 42,280 KB
testcase_57	AC	157 ms 42,624 KB
testcase_58	AC	153 ms 42,320 KB
testcase_59	AC	156 ms 42,504 KB
testcase_60	AC	157 ms 42,468 KB
testcase_61	AC	158 ms 42,568 KB
testcase_62	AC	164 ms 42,436 KB
testcase_63	AC	158 ms 42,584 KB
testcase_64	AC	156 ms 42,004 KB
testcase_65	AC	153 ms 42,408 KB
testcase_66	AC	160 ms 42,164 KB
testcase_67	AC	158 ms 42,136 KB
testcase_68	AC	153 ms 42,112 KB
testcase_69	AC	156 ms 42,396 KB
testcase_70	AC	158 ms 42,212 KB
testcase_71	AC	158 ms 42,264 KB
testcase_72	AC	155 ms 41,968 KB
testcase_73	AC	153 ms 41,784 KB
testcase_74	AC	159 ms 42,040 KB
testcase_75	AC	158 ms 42,252 KB
testcase_76	AC	159 ms 41,984 KB
testcase_77	AC	159 ms 42,088 KB
testcase_78	AC	161 ms 41,948 KB
testcase_79	AC	160 ms 42,268 KB
testcase_80	AC	158 ms 42,180 KB
testcase_81	AC	161 ms 42,148 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

結果

テストケース

ソースコード