AtCoder Beginner Contest 323

D 問題

• 優先度付きmapで小さい値から処理をおこなう。
• 小さい値から貪欲的に結合していき、結合できない奇数となるものの合計を計算する。

Main.java

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

public class Main {
	public static void main(String args[] ) throws Exception {

		BufferedReader br = new BufferedReader( new  InputStreamReader( System.in ) ) ;
		int N = Integer.valueOf ( br.readLine() ) ;
		
		TreeMap<Long,Long> map = new TreeMap<>() ;
		for ( int i=0  ;i<N ; i++ ) {
			String[] ss  = br.readLine().trim().split(" ") ;
			int S = Integer.valueOf ( ss[0] ) ;
			int C = Integer.valueOf ( ss[1] ) ;
			map.put( (long) S , (long) C ) ;
		}
		
		long t = 0 ;
		while ( ! map.isEmpty() ) {
			Map.Entry<Long,Long> entry = map.pollFirstEntry() ;
			long key   = entry.getKey() ;
			long value = entry.getValue() ;

			if ( value % 2 != 0 ) t += 1 ;
			if ( value / 2 != 0 )
				map.put( key * 2 , map.getOrDefault( key *2 , 0L ) + value / 2 ) ;
		}
		System.out.println( t ) ;
	}
}

E 問題

• 下記のようにdp配列を使いまわせば制限時間内になる。ループ内で配列を新たに作るとNG

Main.java

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

public class Main {
	public static void main(String args[] ) throws Exception {

		BufferedReader br = new BufferedReader( new  InputStreamReader( System.in ) ) ;
		String[] ss = br.readLine().trim().split(" ") ;
		int N = Integer.valueOf( ss[0] ) ;
		int X = Integer.valueOf( ss[1] ) ;

		ss = br.readLine().trim().split(" ") ;
		int[] t = Arrays.stream ( ss ).mapToInt(Integer::valueOf).toArray() ;

		long mod =  998244353L ;
		long bx = BigInteger.valueOf( N ) .modInverse( BigInteger.valueOf( mod ) ).longValue() ;
		
		long t2 = 0 ;
		long[] dp = new long[X+1] ;
		dp[0] = 1 ;
		while ( true ) {
			int c = 0 ;
			for ( int i=0 ; i<dp.length ; i++ ) {
				if ( dp[i] == 0 ) continue ;
				long x = dp[i] ;
				dp[i] = 0 ;
				for ( int j=0 ; j<t.length ; j++ ) {
					if ( i + t[j] > X ) {
						if ( j== 0 ) {
							t2 += ( x * bx  ) % mod ;
							t2 %= mod ;
						}
					} else {
						dp[i+t[j]] += ( x * bx ) % mod ;
						dp[i+t[j]] %= mod ;
						c += 1 ;
					}
				}
			}
			if ( c == 0 ) break ;
		}
		System.out.println( t2 ) ;
	}
}

• もしくは曲が選ばれると必ず時刻が1以上増加するため、優先度付きMapを使い小さい値から処理をする。(処理内容が把握しやすいため、実際にはこちらで提出したが処理時間的にはよくない)

Main.java

		TreeMap<Integer,Long> map = new TreeMap<>() ;
		map.put( 0 , 1L ) ;
		
		long t2 =0 ;
		while ( ! map.isEmpty() ) {
			int r = map.firstKey() ; 
			long x = map.get(r).longValue() ;
			map.remove ( r ) ;

			for ( int i=0 ; i<t.length ; i++ ) {
				int v = t[i] ;
				if ( r + v > X ) {
					if ( i== 0 ) {
						t2 += ( x * bx  ) % mod ;
						t2 %= mod ;
					}
				} else {
					int key = r + v ;
					long x2 = ( x * bx ) % mod ;
					long d = map.getOrDefault( key , 0L ) ;
					d += x2 ; 
					d %= mod ; 
					map.put( key , d ) ;
				}
			}
		}