Hatena::Grouptopcoder

tochukasoの日記

 | 

2014-07-12

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

 

 |