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

Submission #1773594

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=65;
        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);
        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)
                        m[0][i+1][j+1]=Math.min(m[0][i+1][j+1],m[0][i][j]);
                    if(j>0)
                        m[1][i+1][j-1]=Math.min(m[1][i+1][j-1],m[0][i][j]|1L<<i);
                    m[1][i+1][j]=Math.min(m[1][i+1][j],m[1][i][j]);
                }else{
                    m[0][i+1][j]=Math.min(m[0][i+1][j],m[0][i][j]);
                    if(j<2*B-1)
                        m[0][i+1][j+1]=Math.min(m[0][i+1][j+1],m[1][i][j]);
                    if(j>0)
                        m[1][i+1][j-1]=Math.min(m[1][i+1][j-1],m[1][i][j]|1L<<i);
                }
            }
        }
        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ソースコード長 1355 Byte
File nameファイル名
Exec time実行時間 188 ms
Memory usageメモリ使用量 37876 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 109 ms 21968 KB
10_small_00.txt AC 188 ms 34772 KB
20_medium_01.txt AC 183 ms 37876 KB
20_medium_02.txt AC 179 ms 37360 KB
20_medium_03.txt AC 168 ms 34776 KB
30_large_04.txt AC 176 ms 35696 KB
30_large_05.txt AC 185 ms 32788 KB
30_large_06.txt AC 178 ms 37096 KB
80_power_of_2.txt AC 102 ms 18772 KB