Hatena::Grouptopcoder

tochukasoの日記

 | 

2014-07-12

ABC B12

| 00:38

今回はテスト時間内の初の4完(前に400点はあったけど、満点が401点の時だったから、これが初の全完)

A,B,Cは単純なシミュレーション

D問題

 ・V個の頂点、E個の辺がある。

 ・任意の頂点からの最長距離が最短となる頂点を求める。

 ・競技プログラミングコンテストで初めての

  ダイクストラ法を使って、O(V^3)で解いた。

  半年前なら絶対に解けなかっただろうから、これが解けたのは感慨深い。

  Rは伸びないけど、きっと力はついてると思う。

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        
        int N = readInt();
        int M = readInt();
        int[][] roads =  readIntMatrix(M);
        
        Map<Integer, List<Integer[]>> map = new HashMap<Integer, List<Integer[]>>();
        for (int i = 1; i <= N; i++) {
            map.put(i, new ArrayList<Integer[]>());
        }
        
        for (int i = 0; i < M; i++) {
            {
                List<Integer[]> list = map.get(roads[i][0]);
                int[] arr = {roads[i][1], roads[i][2]};
                list.add(convIntArray(arr));
            }
            {
                List<Integer[]> list = map.get(roads[i][1]);
                int[] arr = {roads[i][0], roads[i][2]};
                list.add(convIntArray(arr));
            }
        }
        
        int min = Integer.MAX_VALUE;
        
        for (int i = 1; i <= N; i++) {
            
            int[] dp = new int[N + 1];
            boolean[] used = new boolean[N+1];
            Arrays.fill(dp, Integer.MAX_VALUE - 100);
            dp[i] = 0;
            for (int z = 1; z <= N; z++) {
               
                int f = -1;
                int time = Integer.MAX_VALUE;
                for (int j = 1; j <= N; j++) {
                    if(!used[j] && time > dp[j]) {
                        time = dp[j];
                        f = j;
                    }
                }
                used[f] = true;
                
                List<Integer[]> list = map.get(f);
                for (Integer[] integers : list) {
                    int to = integers[0];
                    int t = integers[1];
                    dp[to] = Math.min(dp[to], dp[f] + t);
                }
            } 
            
            int max = 0;
            for (int j = 1; j <= N; j++) {
                max = Math.max(max, dp[j]);
            }
            
            min = Math.min(min, max);
        }
        
        pw.println(min);
    }    

162位

SRM627

| 00:31

easy

 ・棒の長さを表す数列が与えられる。

 ・同一の長さの棒を4本使用して正方形を作る。

 ・何個の正方形を作ることが出来るかを返却する。

 ・同一の棒の長さをカウントして、4で割った商の和を求める。

	public int howManySquares(int[] sticks)
	{
	    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
	    for (int i = 0; i < sticks.length; i++) {
	        int cnt = 0;
	        if(map.containsKey(sticks[i])) {
	            cnt = map.get(sticks[i]);
	        }
	        cnt ++;
            
	        map.put(sticks[i], cnt);
	            
        }
	    int res = 0;
	    for (int i : map.values()) {
	        res += i / 4;
        }
	    return res;
	}

medium

 kawai Editの問題?

 問題文がうまく開かなかったので手をつけず。

hard

 ・数列が与えらる

 ・数列の部分数列を数回反転させることが出来る。

  ・反転させるエリアは重複を許さない。

 ・その後、バブルソートを行う。

  バブルソートでスワップする回数が最も少なくなるように反転させた場合、

  スワップ処理を何回行う必要があるか。

 DFSで解いたけど、TLEで爆死

 計算量がO(N^4K)ぐらいになった。N,K共に最大50なんで、50^5 = 3億1千万

 よく考えるとちょっと枝刈すれば間に合いそうだな・・・ぐぬぬ・・・

 チャレンジモードも一問失敗。

 ただ、その解答はチャレンジ成功されてたんで、Qが問題だった。

1016⇒920

 

 |