京都大学プログラミングコンテスト2015

Submission #1773587

Source codeソースコード

import java.util.*;

class Main {
    static final long I=(1L<<62-1);
    static long f(long n){
        final int A=60;
        final int B=70;
        boolean[][][] dp=new boolean[2][A][2*B];
        long[][][] m=new long[2][A][2*B];
        for(int i=0;i<2;++i)
            for(int j=0;j<A;++j)
                Arrays.fill(m[i][j],I);
        dp[0][0][B]=true;
        m[0][0][B]=0;
        for(int i=0;i<A-1;++i){
            int d=(n&1L<<i)!=0?1:0;
            for(int j=0;j<2*B;++j){
                if(d==1){
                    if(j<2*B-1){
                        dp[0][i+1][j+1]|=dp[0][i][j];//0
                        m[0][i+1][j+1]=Math.min(m[0][i+1][j+1],m[0][i][j]);
                    }
                    if(j>0){
                        dp[1][i+1][j-1]|=dp[0][i][j];//1
                        m[1][i+1][j-1]=Math.min(m[1][i+1][j-1],m[0][i][j]|1L<<i);
                    }
                    dp[1][i+1][j]|=dp[1][i][j];//0,1
                    m[1][i+1][j]=Math.min(m[1][i+1][j],m[1][i][j]);
                } else {
                    dp[0][i+1][j]|=dp[0][i][j];//0,1
                    m[0][i+1][j]=Math.min(m[0][i+1][j],m[0][i][j]);
                    if(j<2*B-1){
                        dp[0][i+1][j+1]|=dp[1][i][j];//0
                        m[0][i+1][j+1]=Math.min(m[0][i+1][j+1],m[1][i][j]);
                    }
                    if(j>0){
                        dp[1][i+1][j-1]|=dp[1][i][j];
                        m[1][i+1][j-1]=Math.min(m[1][i+1][j-1],m[1][i][j]|1L<<i);
                    }
                }
            }
        }
        //System.err.println("dp[0][A-1][B]=" + dp[0][A-1][B]);
        //System.err.println("m[0][A-1][B]=" + m[0][A-1][B]);
        return m[0][A-1][B];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t=scan.nextInt();
        while(t-->0)
            System.out.println(f(scan.nextLong()));
    }
}

Submission

Task問題 H - Bit Count
User nameユーザ名 kirika_comp
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 300
Source lengthソースコード長 1995 Byte
File nameファイル名
Exec time実行時間 239 ms
Memory usageメモリ使用量 42584 KB

Test case

Set

Set name Score得点 / Max score Cases
All 300 / 300 00_sample.txt,10_small_00.txt,20_medium_01.txt,20_medium_02.txt,20_medium_03.txt,30_large_04.txt,30_large_05.txt,30_large_06.txt,80_power_of_2.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample.txt AC 115 ms 21076 KB
10_small_00.txt AC 214 ms 42332 KB
20_medium_01.txt AC 219 ms 38716 KB
20_medium_02.txt AC 237 ms 41304 KB
20_medium_03.txt AC 201 ms 38704 KB
30_large_04.txt AC 239 ms 41360 KB
30_large_05.txt AC 237 ms 42584 KB
30_large_06.txt AC 227 ms 41124 KB
80_power_of_2.txt AC 115 ms 21716 KB