Hatena::Grouptopcoder

tochukasoの日記

|

2014-07-14

CodeForces R255 Div2

| 21:24

2完

C問題も問題の解き方の方向性は間違ってなかった。

実装力の無さが悔やまれる。

いいデバッグの仕方を身につけたい。

でも、567th/ 3251で過去最高の出来。

・A問題

 数列が与えられる。

 数列をKで割った余りをテーブルに格納する。

 既に余りが格納されている場合、順序を返却する。

 一回も衝突が起きない場合は-1を返却する。

 Setを使用して既に格納されている数字を管理する。

 数列の要素を順番に処理して、追加できない場合は順序を出力する。

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        
        Set<Integer> table = new HashSet<Integer>();

        int P = readBufInt();
        int N = readBufInt();
        for (int i = 1; i <= N; i++) {
            if(!table.add(readBufInt() % P)) {
                pw.println(i);
                return;
            }
        }
        pw.println("-1");       
    }

・B問題

 文字列が与えられる。

 文字列はアルファベットの'a'から'z"で構成されている。

 それぞれ'a'から'z'は点数を持っている。

 文字の順序*文字種の点数の総和を求める。

 また、任意の文字をk文字挿入することが出来る。

 最大値となる総和を求める。

 与えられた文字列のスコアを取得する。

 アルファベットの中で最も価値の高い文字を判別する。

 K*最も高い + 規定文字列のスコアで最大値を求める。

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        String S = br.readLine();
        int K = readBufInt();
        int[] a = readIntArray();
        
        int sum = 0;
        int max = 0;
        char[] sA = S.toCharArray();
        for (int i = 0; i < sA.length; i++) {
            char c = sA[i];
            sum += a[c - 'a'] * (i + 1);
        }
        
        for (int i : a) {
            max = Math.max(max, i);
        }
        for (int i = 1; i <= K; i++) {
            sum += (i + sA.length) * max; 
        }
        pw.println(sum);
    }

・C問題

 数列が与えられる。

 数列の任意の一文字を好きな数字に入れ替えることが出来る。

 必ず増加する(i < i+1)ような部分数列を取得し、最長の長さを求める。

 それぞれの要素の部分数列の長さを計算し、メモをする。

 任意の一文字を替えることが出来るので、最長の部分数列は以下のいずれかのパターンが考えられる。

 ・部分数列を3つ加算出来る場合、

  この場合は真ん中の数列の長さが1,かつ、左の数列の最終数字 + 2 <= 右の数列の最初の数字の条件を満たす必要がある。

1,2,3,8,5,6,7

 ・部分数列を2つ加算できる場合、

右の数列の長さが2以上、かつ、左の数列の最後の文字 + 2 <= 右の数列の2文字目

  1,2,3,2,5,6,7

 ・部分数列を2つ加算できる場合、

  左の数列の長さが2以上、かつ、左の数列の最後から2文字目 + 2 <= 右の数列の最初の数字

1,2,8,4,5,6,7

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        int N = readBufInt();
        int[] arr = readIntArray();
        
        if (N < 3) {
            pw.println(N);
            return;
        }
        shakutori(N, arr);
    }    

    static void shakutori (int N, int[] arr) {
        int[] subsequence = new int[arr.length + 1];
        System.arraycopy(arr, 0, subsequence, 0, arr.length);
        subsequence[arr.length] = -1;
        
        int to = 0;
        int before = 0;
        int[] dp = new int[N + 1];
        int length = 0;
        for (; to <= N; to++) {
            int now = subsequence[to];
            
            if(before < now) {
                length++;
            } else {
                for (int i = 0; i <= length; i++) {
                    dp[to - i] = length;
                }
                length = 1;
            }

            dp[to] = length;
            before = now;
        }
        dp[N] = 0;
//        for (int i = 0; i < N; i++) {
//            System.out.println(dp[i]);
//        }
        
        int max = 0;
        for (int i = 1; i < N - 1; i++) {
            int x = 0;
            if(dp[i + 1] == 1 && subsequence[i] + 1< subsequence[i + 2]) {
                x = dp[i] + dp[i + 2] + 1;
            }
            if (subsequence[i] > subsequence[i - 1] && subsequence[i] >= subsequence[i+1] ) {
                if(subsequence[i] + 1 < subsequence[i + 2]) {
                    x = Math.max(x, dp[i] + dp[i + 1]);
                }
                if (subsequence[i - 1] + 1 < subsequence[i + 1]) {
                    x = Math.max(x, dp[i] + dp[i + 1]);
                }
            }
            x = Math.max(x, dp[i] + 1);
            
            max = Math.max(max, x);
        }
        
        pw.println(Math.min(N, max));
    }

でも、この解法だとパターンわけがメンドクサイ上に、

漏れがないかの証明、判断が難しい。

これでシステムテストは通ってるけど、嘘解法な気もする。

初めにそれぞれの部分数列の長さを計算して、

あとは組み合わせるって考え方はいいと思うんだけど・・・・

D問題

 2次元配列の数列が与えられる。

 K回、縦、横の任意の列、行の総和を取得出来る。

 ただし、列の総和を取得すると、その総和を取得するための構成要素はPを減産する必要がある。

 K回の総和が最大となるように列、行から値を取得する。

 うーーーーん。

 データの量的に全探索はとても間に合わなそう。

 列か行かの総和が大きい方から毎回引けばいいか。

 サンプル通った。

 WA

 そりゃそうか。K回やらなきゃいけないんだから、マイナスを少なくするのを優先した方がいいケースもある。

 駄目だ。分からん。


1359⇒1501

念願のブルーコーダーになりました。

年内の目標はイエローコーダー!!

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

 

2014-07-06

CodeForces #254

| 00:45

0完

A問題に異様に時間を取られたうえに正答が導けなかった。

A問題は単純な全探索で解けるだろうと思ってたら

TLE,MLEで死にました。

というかよくよく考えたら探索とかいらなかった。

        for (int k = 1; k <= N ; k++) {
            for (int k2 = 1; k2 <= M; k2++) {
                if (map[k][k2] == '-') {
                    pw.print(map[k][k2]) ;
                } else {
                    
                    pw.print((k + k2) %2 == 0 ? 'B' : 'W');
                }
            } 
            pw.println();
        }

単純に市松模様なんだから探索とかいらない・・・・

何考えてたんだろう・・・

1451⇒1359

2014-06-29

SRM626

| 22:52

・Easy

 数値型の配列が与えられる。

 配列のサブ配列の総和を求める。

 例.[1,2,3]の場合、1, 2, 3, 1 + 2, 2 + 3, 1 + 2 + 3の合計 = 20となる

 選択する文字の長さ、開始位置、N文字分で3重ループして計算する

	public int findSum(int[] array)
	{
	    int sum = 0;
	    int N = array.length;
	    for (int i = 1; i <= N; i++) {
	        for (int j = 0; j + i<= N; j++) {
	            for(int k = 0; k < i; k++) {
	                sum += array[j+k];
	            }
	        }
	    }
	    return sum;
	}

 データの制約が緩い(配列の要素数は50)にも関わらず、

 時間がかかると思って効率的な解法を探して小一時間使った。

 結局3重ループの解法でいいと気付いた。

 なんという時間の無駄。

Medium

 2人が互いにサイコロを振りあう。

 サイコロはN面体。

 Aが勝つことは決まっている。

 Aの目の期待値を答える。

 Bの目を上から順番に見ていって、AがBの目を越える事がある場合に、

 総和と回数を足していく。(Bの目に対してAが勝つ場合にカウントする)

 最後に総和/回数を行う

	public double getExpectation(int a, int b)
	{
		double res = 0;
		
	    int sumCount = 0;
	    int sum = 0;
	    for (int i = b; i > 0; i --) {
	        if (a > i) {
	            int tmp = a - i;
	            sumCount += tmp;
	            for (int j = 0; j < tmp; j++) {
	                sum += a - j;
	            }
	        }
	    }
		
		
		return (double) sum /  sumCount;
	}

C問題。

時間なくて解けなかった。

時間あっても、解けないかな。

課題として、easy問題とmedium問題を確実に素早く解く力が必要

毎日必ず、Div2のeasyとmediumを解こう。

1072 ⇒ 1016

2014-06-28

ARC026

| 00:21

なかなか脱初心者出来ない・・・・・・

・B問題

 ルートNまで探索する。

 N自身は約数に含めないでカウントする。

 ループで割り切れる方の数とループの数が同一の場合に重複してカウントしないように気を付ける。


    String P = "Perfect"; 
    String D = "Deficient"; 
    String A = "Abundant"; 
    /**
     * @throws Throwable
     */
    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        
        long N = readLong();
        if ( N == 1) {
            pw.println(D);
            return;
        }
        long sum = 1;
        long max = (long)Math.sqrt(N);
        
        for (int i = 2; i <= max; i++ ) {
            if (N % i == 0) {
               sum += i;
               if (i != N / i) 
               sum += (N / i) ;
            }
        }
        if (sum == N) {
            pw.println(P);
        } else if (sum > N) {
            pw.println(A);
        } else {
            pw.println(D);
        }
    }    

C問題

 区間l⇔rを全て照らすように蛍光灯を付けた場合の最小コストを選択する。

 まずはDPで考える。

 DP[l=0からrまでの長さ] = その範囲内での最小コスト

 dp[i] = Min(dp[i], dp[N[l + N[C])でLになるまでループ処理を行う。

 計算量はO(N*L)。

 これでは間に合わないと思い、実装をためらう。

 時間ぎりぎりでこの方針で実装する。

 5分間に合わない。

 この方針+RMQ(Range Minimum Query)で間に合わせることが出来る

200点 121

|