結果

問題 No.568 じゃんじゃん　落とす　委員会
コンテスト
ユーザー k_6101
提出日時 2019-12-21 13:06:37
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 5,440 bytes
コンパイル時間 4,078 ms
コンパイル使用メモリ 105,556 KB
実行使用メモリ 84,080 KB
最終ジャッジ日時 2024-07-19 07:12:30
合計ジャッジ時間 24,685 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 TLE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.InputStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;

import static java.util.Comparator.*;

public class Main {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        Solver solver = new Solver(System.in, out);
        solver.solve();
        out.close();
    }
}
class Solver {
	Scanner sc;
	PrintWriter out;
    public Solver(InputStream in, PrintWriter out) {
    	sc = new Scanner(in);
    	this.out = out;
    }
    // ==================================================================
    int[] cnt = new int[10];							// [正解数] ＝　人数
    MapList A = new MapList();							// Ａの点数　→　インデックスのリスト
    MapList B = new MapList();							// Ｂの点数　→　インデックスのリスト
    int[] X = new int[100010];							// [インデックス] = その人の点数
    public void solve() {
    	int N = Integer.parseInt(sc.next());
    	int M = Integer.parseInt(sc.next());
    	int a, b;
    	List<Integer> list;
    	for (int i = 0; i < N; i++) {
			X[i] = Integer.parseInt(sc.next()) + 1;		// 初期値は a は必ず正解とする
			cnt[X[i]]++;
			a = Integer.parseInt(sc.next());
			b = Integer.parseInt(sc.next());
			A.add(a, i);
			B.add(b, i);
		}
//    	A.dump();
//    	B.dump();
//    	for (int i = 0; i < 10; i++) {
//			out.println("cnt[" + i + "] = " + cnt[i]);
//		}
    	int ans = 999999999;
    	int sb = 100001;
    	LOOP:
    	for (int sa = 0; sa <= 100001; ) {
    		while(cnt[2] + cnt[3] + cnt[4] + cnt[5] < M) {
    			sb--;
    			if(sb < 0)	break LOOP;
    			if(B.contains(sb)) {
//            		out.println(" 1   SA = " + sa + "  SB = " + sb);
    				for(Integer index : B.getList(sb)) {	// 見つかった人はＢを正解になる
//    					out.println(" SB = " + sb + "  が見つかった[" + index + "]　　元の正解数 = " + X[index] 
//    							+ "  元の人数　= " + cnt[X[index]] + "  先の人数　= " + cnt[X[index]+1]);
    					cnt[X[index]]--;				// 元の正解数のカウントを減らす
    					X[index]++;						// 正解数を更新する
    					cnt[X[index]]++;				// 新しい更新数のカウントを増やす
    				}
    			}
    		}
    		ans = Math.min(ans, cnt[3] + cnt[4] + cnt[5]);	// ３問以上の最小人数を取得する
    		
    		if(A.contains(sa)) {
//        		out.println(" 2   SA = " + sa + "  SB = " + sb);
				for(Integer index : A.getList(sa)) {	// 見つかった人はＡを不正解になる
//					out.println(" SA = " + sa + "  が見つかった[" + index + "]　　元の正解数 = " + X[index] 
//							+ "  元の人数　= " + cnt[X[index]] + "  先の人数　= " + cnt[X[index]-1]);
					cnt[X[index]]--;					// 元の正解数のカウントを減らす
					X[index]--;							// 正解数を更新する
					cnt[X[index]]++;					// 新しい更新数のカウントを増やす
				}
			}
    		sa++;										// ＳＡを更新する
		}
    	out.println(ans);
    }
    // --------------------------------------
    // Integer のキーに対して、Ｉｎｔｅｇｅｒ　のリストを管理する
    class MapList {
    	private TreeMap<Integer, List<Integer>> map;
    	// 昇順のマップ
    	public MapList() {
    		map = new TreeMap<>();
    	}
    	// reverse = tree なら降順のマップ
    	public MapList(boolean reverse) {
    		if(reverse) {
    			map = new TreeMap<Integer, List<Integer>>(Collections.reverseOrder());
    		} else {
        		map = new TreeMap<>();
    		}
    	}
    	// 値の追加
    	public void add(Integer key, Integer val) {
    		List<Integer> list = map.get(key);
    		if(list == null) {
    			list = new ArrayList<>();
    			map.put(key, list);
    		}
    		list.add(val);
    	}
    	// 値の削除
    	public void del(Integer key, Integer val) {
    		List<Integer> list = map.get(key);
    		if(list == null)	return;
    		list.remove(val);
    		if(list.isEmpty())	map.remove(key);
    	}
    	// データが空か？
    	public boolean isEmpty() {
    		return map.isEmpty();
    	}
    	// キーセットを返す
    	public Set<Integer> keySet() {
    		return map.keySet();
    	}
    	// キーの要素があれば　true を返す
    	public boolean contains(Integer key) {
    		if(map.get(key) == null)	return false;
    		else						return true;
    	}
    	// リストの取得（なければ　null を返す）
    	public List<Integer> getList(Integer key) {
    		return map.get(key);
    	}
    	// ダンプ
    	public void dump() {
    		List<Integer> list;
    		out.println("------------ dump start -------------");
    		for(int key : map.keySet()){
    			list = map.get(key);
    			out.println("key = " + key);
    			for (int val : list) {
					out.print(" " + val);
				}
    			out.println("");
    		}
    		out.println("------------ dump end -------------");
    	}
    }
}
0