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

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

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

 |