#756238 (Java21) No.3 ビットすごろく

• 問題: No.3 ビットすごろく
• ユーザー: tk55513
• 提出日時: 2022-04-26 12:25:15
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 92 ms / 5,000 ms
• コード長: 12,981 bytes
• コンパイル時間: 2,961 ms
• コンパイル使用メモリ: 93,208 KB
• 実行使用メモリ: 39,376 KB
• 最終ジャッジ日時: 2024-06-28 07:28:05
• 合計ジャッジ時間: 6,758 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	67 ms; 37,684 KB
testcase_01	AC	64 ms; 37,336 KB
testcase_02	AC	64 ms; 37,352 KB
testcase_03	AC	83 ms; 38,344 KB
testcase_04	AC	71 ms; 37,916 KB
testcase_05	AC	80 ms; 38,564 KB
testcase_06	AC	74 ms; 37,932 KB
testcase_07	AC	70 ms; 37,740 KB
testcase_08	AC	86 ms; 38,856 KB
testcase_09	AC	89 ms; 38,940 KB
testcase_10	AC	89 ms; 39,208 KB
testcase_11	AC	83 ms; 38,696 KB
testcase_12	AC	87 ms; 38,552 KB
testcase_13	AC	73 ms; 38,308 KB
testcase_14	AC	80 ms; 38,948 KB
testcase_15	AC	92 ms; 39,072 KB
testcase_16	AC	84 ms; 38,816 KB
testcase_17	AC	81 ms; 38,948 KB
testcase_18	AC	71 ms; 38,140 KB
testcase_19	AC	91 ms; 38,800 KB
testcase_20	AC	70 ms; 37,380 KB
testcase_21	AC	66 ms; 37,372 KB
testcase_22	AC	82 ms; 38,928 KB
testcase_23	AC	80 ms; 39,376 KB
testcase_24	AC	81 ms; 39,348 KB
testcase_25	AC	82 ms; 39,048 KB
testcase_26	AC	66 ms; 37,576 KB
testcase_27	AC	74 ms; 38,472 KB
testcase_28	AC	87 ms; 39,108 KB
testcase_29	AC	91 ms; 38,840 KB
testcase_30	AC	66 ms; 37,704 KB
testcase_31	AC	68 ms; 37,384 KB
testcase_32	AC	88 ms; 38,444 KB

ソースコード

import java.io.*;
import java.util.*;
import java.util.function.BiFunction;

import static java.lang.Math.*;
import static java.lang.String.format;

public class Main {
    public static void main(String[] args) {
        solve();
    }
    final static int INF = Integer.MAX_VALUE>>1;
    final static int MOD = 1_000_000_007;
    final static int[] dx4 = { 0, 1, 0, -1 };
    final static int[] dy4 = { 1, 0, -1, 0 };
    final static int[] dx8 = {0, 1, 1,  1,  0, -1, -1, -1};
    final static int[] dy8 = {1, 1, 0, -1, -1, -1, 0, 1};
    public static void solve(){
        //TODO:Solve problem like ***
        Scanner sc=new Scanner();
        int n=sc.nextInt();
        int[] ans=new int[n];
        Arrays.fill(ans,INF);
        ans[0]=1;
        boolean[] isUsed=new boolean[n];
        PriorityQueue<FixedIntPair> pq = new PriorityQueue<>(Comparator.comparing((FixedIntPair fp)->fp.y));
        pq.add(new FixedIntPair(1,1));
        while (!pq.isEmpty()) {
            FixedIntPair fp=pq.remove();
            final int index=fp.x-1;
            if(isUsed[index])continue;
            isUsed[index]=true;
            final int cnt=Integer.bitCount(fp.x);
            final int low=index - cnt;
            if (low>= 0) {
                if(ans[low]>ans[index]+1){
                    ans[low]=ans[index]+1;
                    pq.add(new FixedIntPair(low+1,ans[low]));
                }
            }
            final int high=index+cnt;
            if (high < n) {
                if (ans[high] > ans[index] + 1) {
                    ans[high]=ans[index]+1;
                    pq.add(new FixedIntPair(high+1,ans[high]));
                }
            }
        }
        put(ans[n-1]==INF?-1:ans[n-1]);

    }

    private static abstract class SegmentTree {

        private final int originSize;
        private final int height;
        private final long[] node;
        private final long noRelationVal;
        protected SegmentTree (long[] original,long noRelationVal){
            this.noRelationVal=noRelationVal;
            originSize = original.length;
            {
                int height_ = 1;
                while (originSize > (1 << (height_ - 1))) {
                    height_++;
                }
                height = height_;
            }
            this.node = new long[ (1<<height)-1];
            //まず元の配列に対応する部分のnodeを埋める
            for(int i=0;i<originSize;i++){
                this.node[(1<<(height-1))-1+i]=original[i];
            }
            for(int i=(1<<(height-1))-1+originSize;i<(1<<height)-1;i++){
                this.node[i]=noRelationVal;
            }
            //空いているnodeを後ろから埋めていく
            for(int i = (1<<(height-1))-2; i>=0; i--){
                this.node[i]=marge(this.node[i*2+1],this.node[i*2+2]);
            }
        }
        public long getVal(int a,int b){
            return getVal(a,b,0,0,-1);
        }
        public long getVal(int a, int b, int k, int l, int r) {
            //node[k]=origin上の範囲[l,r]の合計を表している
            if(r < 0) r = (1<<(height-1))-1;
            if(b<l||r<a) return noRelationVal;
            if(a <= l && r <= b) return node[k];

            long vl = getVal(a, b, 2*k+1, l, (l+r)/2);
            long vr = getVal(a, b, 2*k+2, (l+r)/2+1, r);
            return marge(vl,vr);
        }
        public long getVal(int index){
            return node[(1<<(height-1))-1+index];
        }

        void setVal(int index,long val){
            if(index<0||index>=originSize) throw new IllegalArgumentException(format("挿入位置が不正%d",index));
            index=(1<<(height-1))-1+index;
            node[index]=val;
            while(index>0){
                index=(index-1)/2;
                node[index]=marge(node[2*index+1],node[2*index+2]);
            }
        }
        protected abstract long marge(long a,long b);
        @Override
        public String toString(){
            StringBuilder result=new StringBuilder();
            result.append(format("Class:%s\n",getClass().getSimpleName()));
            result.append(format("height:%d\n",height));
            for(int currentHeight=1;currentHeight<=height;currentHeight++){
                for(int i=(1<<(currentHeight-1))-1;i<=(1<<currentHeight)-2;i++){
                    result.append(format("%d ",node[i]));
                }
                result.append("\n");
            }
            return result.toString();
        }


        public static final class SumSegmentTree extends SegmentTree {
            SumSegmentTree(long[] original){
                this(original,0);
            }
            SumSegmentTree(long[] original,long noRelationVal){
                super(original,noRelationVal);
            }

            @Override
            public long marge(long a, long b) {
                return a+b;
            }
        }
        public static final class MinSegmentTree extends SegmentTree {
            MinSegmentTree(long[] original){
                this(original,Long.MAX_VALUE);
            }
            MinSegmentTree(long[] original,long noRelationVal){
                super(original,noRelationVal);
            }

            @Override
            public long marge(long a, long b) {
                return Math.min(a,b);
            }

        }
        public static final class MaxSegmentTree extends SegmentTree {
            MaxSegmentTree(long[] original){
                this(original,-Long.MIN_VALUE);
            }
            MaxSegmentTree(long[] original,long noRelationVal){
                super(original,noRelationVal);
            }

            @Override
            public long marge(long a, long b) {
                return Math.max(a,b);
            }
        }
    }

    private static void print(Object... objects){
        if(objects.length==1){
            System.out.print(objects[0]);
        }else{
            System.out.print(Arrays.toString(objects));
        }
    }
    private static void put(Object... objects) {
        print(objects);
        put();
    }
    private static void put(){
        System.out.println();
    }

    private static void putM(String name,char[][] mat){
        put("---------------------"+name+"-----------------");
        for (int i = 0; i < mat.length; i++) {
            put(Arrays.toString(mat[i]));
        }
    }
    private static void putM(String name,int[][] mat){
        put("---------------------"+name+"-----------------");
        for (int i = 0; i < mat.length; i++) {
            put(Arrays.toString(mat[i]));
        }
    }
    private static void putM(String name,long[][] mat){
        put("---------------------"+name+"-----------------");
        for (int i = 0; i < mat.length; i++) {
            put(Arrays.toString(mat[i]));
        }
    }
    private static void putM(String name,boolean[][] mat){
        put("---------------------"+name+"-----------------");
        for (int i = 0; i < mat.length; i++) {
            put(Arrays.toString(mat[i]));
        }
    }
    final static private class Scanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte())
                return buffer[ptr++];
            else
                return -1;
        }

        private boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr]))
                ptr++;
            return hasNextByte();
        }

        public String next() {
            if (!hasNext())
                throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public long nextLong() {
            if (!hasNext())
                throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while (true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if (b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }

        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
                throw new NumberFormatException();
            return (int) nl;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
    final static private class FixedIntPair {
        final public int x, y;
        final static public FixedIntPair ZEROS=new FixedIntPair(0,0);
        FixedIntPair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public static double distance(FixedIntPair fip1,FixedIntPair fip2){
            double x = (double) fip1.x - fip2.x;
            double y = (double) fip1.y - fip2.y;
            return Math.sqrt(x*x+y*y);
        }

        @Override
        public int hashCode() {
            return x*100000+y;
        }

        @Override
        public boolean equals(Object obj) {
            if(obj==null)return false;
            if(!(obj instanceof FixedIntPair)) return false;
            FixedIntPair pair=(FixedIntPair) obj;
            return this.x==pair.x&&this.y==pair.y;
        }

        @Override
        public String toString() {
            return format(FixedIntPair.class.getSimpleName()+":(%d,%d)", x, y);
        }
    }
    final static private class FixedLongPair {
        final public long x, y;
        final static public FixedLongPair ZEROS=new FixedLongPair(0,0);
        FixedLongPair(long x, long y) {
            this.x = x;
            this.y = y;
        }
        public static double distance(FixedLongPair flp1,FixedLongPair flp2){
            double x = (double) flp1.x - flp2.x;
            double y = (double) flp1.y - flp2.y;
            return Math.sqrt(x*x+y*y);
        }

        @Override
        public int hashCode() {
            return (int)x+(int)y;
        }

        @Override
        public boolean equals(Object obj) {
            if(obj==null)return false;
            if(!(obj instanceof FixedLongPair)) return false;
            FixedLongPair pair=(FixedLongPair)obj;
            return this.x==pair.x&&this.y==pair.y;
        }

        @Override
        public String toString() {
            return format(FixedLongPair.class.getSimpleName()+":(%d,%d)", x, y);
        }
    }
    final static private class Binary{
        public static String toZeroPadding(int i){
            return format("%"+Integer.toBinaryString(-1).length()+"s",Integer.toBinaryString(i)).replace(' ','0');
        }
        public static String toZeroPadding(long i){
            return format("%"+Long.toBinaryString(-1).length()+"s",Long.toBinaryString(i)).replace(' ','0');
        }
    }

    final static private class Util {
        static long gcd(long a,long b){
            a= abs(a);
            b= abs(b);
            if(a<b){
                long tmp=a;
                a=b;
                b=tmp;
            }
            while(b!=0){
                long r=a%b;
                a=b;
                b=r;
            }
            return a;
        }
        static int gcd(int a,int b){
            a= abs(a);
            b= abs(b);
            if(a<b){
                int tmp=a;
                a=b;
                b=tmp;
            }
            while(b!=0){
                int r=a%b;
                a=b;
                b=r;
            }
            return a;
        }
        static long lcm(long a,long b){
            long gcd=gcd(a,b);
            long result=b/gcd;
            return a*result;
        }
        static boolean isValidCell(int i,int j,int h,int w){
            return i>=0&&i<h&&j>=0&&j<w;
        }
    }
}