Hatena::Grouptopcoder

tochukasoの日記

2014-07-28

CodeForces MemSQL

| 16:41

1完・・・・

A問題

概要

・固有名詞のリストがあらかじめ提示される。

・引数で「a..b..c」の様な文字列が与えられる。

・'.'は任意の一文字に置き換えることが出来る。

・引数がどの文字列に合致するかを調べて返却する。

解法

・あらかじめ提示されている文字列にmatch(String regex)を使用する

    void solve() throws Throwable {
        int N = readInt();
        String word = readString();
        String[] names = {
                "vaporeon", "jolteon", "flareon", "espeon", "umbreon", "leafeon", "glaceon", "sylveon"
        };

        for (String string : names) {
            if(string.matches(word)) {
                pw.println(string);
                return;
            }
        }
    }

B問題

概要

・N * Mサイズの格子が与えられる。

・任意の4点を指定することが出来る。

・[p1,p2],[p2,p3],[p3,p4]の3本の直線の長さの総和が最大になるような4点を求める。

解法

・任意の4点は、左上(0,0),右下(N,M)が中心になる。

 そのため、点の候補になりそうなものをあらかじめ列挙する。(ここの指定が甘くて落としました。)

 順列を使用するが、4Cnなので、nが20ぐらいまでなら余裕で計算できた。

・また、N,Mが0の時の処理は特例として処理するようにした。

    int[][] pos = new int[8][2];
    double max = 0;
    int[] maxPos = null;

    void solve() throws Throwable {
        
        int N = readInt();
        int M = readInt();
        
        if(N == 0) {
            pw.println(0 + " " + 1);
            pw.println(0 + " " + M);
            pw.println(0 + " " + 0);
            pw.println(0 + " " + (M - 1));
            return;
        } else if(M == 0) {
            pw.println(1 + " " + 0);
            pw.println(N + " " + 0);
            pw.println(0 + " " + 0);
            pw.println((N-1) + " " + 0);
            return;
        }

        pos[0] = new int[] {0,0};
        pos[1] = new int[] {N,M};
        pos[2] = new int[] {N - 1,M};
        pos[3] = new int[] {0,1};
        pos[4] = new int[] {1,0};
        pos[5] = new int[] {N,0};
        pos[6] = new int[] {N, M -1};
        pos[7] = new int[] {0, M};
`
        permutationAll(new int[] {0,1,2,3,4,5,6,7});
        pw.println(pos[maxPos[0]][0] + " " + pos[maxPos[0]][1]);
        pw.println(pos[maxPos[1]][0] + " " + pos[maxPos[1]][1]);
        pw.println(pos[maxPos[2]][0] + " " + pos[maxPos[2]][1]);
        pw.println(pos[maxPos[3]][0] + " " + pos[maxPos[3]][1]);
    }
    void permutationAll(int[] p) {
        permutation(p, 0, p.length - 1);
    }
    void permutation(int[] elements, int nowCnt, int totalCnt) {
        if (nowCnt == 4) { 
            O++;
            double sum = 0;
            int p1 = elements[0];
            int p2 = elements[1];
            int p3 = elements[2];
            int p4 = elements[3];
            if(pos[p1][0] == pos[p2][0] && pos[p1][1] == pos[p2][1]) return;
            if(pos[p1][0] == pos[p3][0] && pos[p1][1] == pos[p3][1]) return;
            if(pos[p1][0] == pos[p4][0] && pos[p1][1] == pos[p4][1]) return;
            if(pos[p2][0] == pos[p3][0] && pos[p2][1] == pos[p3][1]) return;
            if(pos[p2][0] == pos[p4][0] && pos[p2][1] == pos[p4][1]) return;
            if(pos[p3][0] == pos[p4][0] && pos[p3][1] == pos[p4][1]) return;

            double seg1 = Math.sqrt(Math.pow(pos[p1][0] - pos[p2][0], 2) + Math.pow(pos[p1][1] - pos[p2][1], 2)); 
            double seg2 = Math.sqrt(Math.pow(pos[p2][0] - pos[p3][0], 2) + Math.pow(pos[p2][1] - pos[p3][1], 2)); 
            double seg3 = Math.sqrt(Math.pow(pos[p3][0] - pos[p4][0], 2) + Math.pow(pos[p3][1] - pos[p4][1], 2)); 
            sum = seg1 + seg2 + seg3;
//            System.out.println(sum + " " + p1 + " " + p2 + " " + p3 + " " + p4);

            if(max < sum) {
                max = sum;
                maxPos = Arrays.copyOf(elements, 4);
            }

        } else {

            for (int i = nowCnt; i <= totalCnt; i++) {
                int tmp = elements[nowCnt]; 
                elements[nowCnt] = elements[i]; 
                elements[i] = tmp;
                permutation(elements, nowCnt+1, totalCnt);
                tmp = elements[nowCnt]; 
                elements[nowCnt] = elements[i]; 
                elements[i] = tmp;
            }
        }
    }

この問題は結構時間を使ったので解きたかった。

C問題

概要

・1~NまでのトランプがMセットある。

・Mセットをごちゃ混ぜにして、N枚取得する。

・1枚トランプを引いて、また山に戻した時に、同一の数のトランプを引く確率を求める。

解法

・不明・・・・・

・コンビネーションを使うと計算量はすごい事になりそうだし、longの範囲で収まらない。

・他の人の解法だけ記しておく。

    void solve() throws Throwable {
        double N = readInt();
        double M = readInt();
        if(M == 1) {
            pw.println(1.0 / N);
            return;
        }
        pw.println(1 / N + (M-1) * (N-1) / N / (N * M - 1));
    }

Mが1の時は、トランプを混ぜないので、1/Nになるのは分かる。

それ以外の場合が分からない。

同一のカードが一枚しか入らない場合と、うーん。

D問題

概要

・タスクがN個ある。

・1個のタスクはA,B,Cを順番にこなす必要がある。

・A,B,Cそれぞれ一度に行えるタスクの個数とタスクにかかる時間が引数で与えられる。

・全てのタスクを終えるための最小の時間を答える。

解法

・動的計画法を使用する。

・タスクAは単純にフルで回す。(タスクAが終わった毎にタスクAを実行する。)

・タスクBのN個目が終わる最小の時間は、

 「タスクAのN個目が終わった時間」

 「タスクBの[N-タスクBを一度に処理できる個数]が終わった時間」

 のいずれかの後に終わる時間+タスクBにかかる時間となる。

・タスクCについてもタスクBと同様にタスクBとの比較で最小時間を計算する。

    int[] dp2 = new int[10001];
    int[] dp3 = new int[10001];
    int K = 0;
    int N1 = 0;
    int N2 = 0;
    int N3 = 0;
    int T1 = 0;
    int T2 = 0;
    int T3 = 0;

    void solve() throws Throwable {
        K = readInt();
        N1 = readInt();
        N2 = readInt();
        N3 = readInt();
        T1 = readInt();
        T2 = readInt();
        T3 = readInt();
        int before = 0;
        
        for (int i = N1; i < K + N1; i+=N1) {
            int nCnt = i / N1;
            int nTime = nCnt * T1;
            for (int j = before; j < i; j++) {
                int jCnt = (j - before) / N2 + 1;
                if(j - N2 >=0) {
                    dp2[j] = Math.max(dp2[j - N2] + T2, nTime + T2 * jCnt);
                } else {
                    dp2[j] = nTime + T2 * jCnt;
                }
            }
            before = i;
        }
        dp2[K] = dp2[K-1];
        before = 0;
        for (int i = 0; i < K; i++) {
            if(i -N3 >= 0) {
                dp3[i] = Math.max(dp2[i] + T3, dp3[i-N3] + T3);
            } else {
                dp3[i] = dp2[i] + T3;
            }
        }
        pw.println(dp3[K-1]);
    
    }

タスクAの処理にかかる時間を計算するところで、

タスクAのループ処理の終了条件をKにしているところで失敗しました。

ループの開始をタスクAで処理できる個数にしていたので、

K+N1まで計算しないとやりきらないことがあります。

結果としては1完ですが、

なぜかレートは上がりました・・・・・。

1488⇒1585

土曜か日曜の夜早め以外の時間帯は参加できなくなるので、

競プロはもうたまにだなー

2014-07-20

CodeForces R257 Div2

| 19:00

1完

A問題

概要

 ・飴が欲しくて一列に並んでいる子供がいる。

 ・子供はそれぞれ飴の欲しい数が異なる。

 ・列の先頭の子にN個の飴をあげる

 ・満足すれば列から抜ける。満足しなければ最後尾に並びなおす。

 ・一番最後に飴を貰う子を答える。

解答方法

 ・ループ処理で先頭から順に飴をあげる。

 ・飴をあげるごとに最後に飴をあげた子供の番号を更新する。

 ・ループ内で一度も飴をあげなかった場合(既に子供が並んでいない)に最後に飴をあげた番号を返す。

    void solve() throws Throwable {
        int n = readInt();
        int m = readInt();
        int[] c = readIntArray();
        int index = 0;
        while(true) {
            boolean isC = false;
            int i = 0;
            for (; i < n ; i++) {
                if(c[i] <= 0) {
                    continue;
                }
                c[i] -= m;
                index = i;
                isC = true;
            }
            if(!isC) {
                pw.println(index + 1);
                return;
            }
        }
    }    

B問題

概要

 ・f(i) = f(i-1) + f(i+1)

 ・f(1) = x, f(2) = y

 ・x,y,Nが与えられるときに、Nの戻り値を答える。

解答方法

 ・数学ゲー?

 ・N%6の戻り値分のケースに分類できる模様。

 ・でもよくわからない。

C問題

概要

 ・N * M のマスが与えられる。

 ・縦方向、または横方向に全部でN回分割出来る。

 ・最小のマスの大きさが最大になるようにした場合の大きさを返却する。

解答方法

 ・N,M,Kが10^9なので、Nの分割回数を0~K、または0~N試すとTLEになる。

1586⇒1486

CodeForces R256 Div2

| 18:45

2完

A問題

概要

 ・複数の棚がある。

 ・棚にメダルとトロフィーを入れたい。

 ・一つの棚にはメダル10個までかトロフィー5個までのどちらかのみを入れる。

 ・それぞれの大会で獲得したメダルとトロフィーの数と棚の数が与えられる。

 ・全て格納出来るかどうかを答える。

解答方法

 ・メダルとトロフィーの総和をそれぞれ計算する。

 ・それぞれ格納できる数で割る。

 ・また、剰余が発生するかを確認し、剰余が発生する場合は棚の数をデクリメントする。

ただし、他の人のソースを見て気付いたけど、わざわざ剰余を計算するよりも、以下の様に書いた方がすっきりしてよい。

あらかじめ「割られる数」に割る数-1を足してやれば、余りが出た場合も切り上げで求めることが出来る。

  N -= (aS + 4) / 5;

    void solve() throws Throwable {
        int[] a = readIntArray();
        int[] b = readIntArray();
        int N = readInt();
        
        int aS = 0;
        for (int aN  : a) {
            aS += aN; 
        }
        
        int bS = 0;
        for (int i : b) {
            bS += i;
        }
        
        N -= aS / 5;
        if (aS % 5 != 0) N--;
        
        N -= bS / 10;
        if (bS % 10 !=0) N--;
        
        if(N >=0) {
            pw.println("YES");
        } else {
            pw.println("NO");
        }
    }

B問題

概要

 ・文字列Sを変形して文字列Tにすることが出来るかどうか。

 ・文字列Sの要素を削除するだけでTに出来る場合は、「automaton」

 ・文字列Sの要素を並び変えるだけでTに出来る場合は、「array」

 ・どちらも行う場合は、「both」

 ・どちらを行っても出来ない場合は、「need tree」

解答方法

 ・それぞれの文字列のアルファベットの出現回数をメモする。

 ・文字列Tの方が出願回数の多いアルファベットがある場合、「need tree」

 ・文字列Sの方が出現回数の多いアルファベットがある場合、「automaton」のフラグを立てる。

 ・文字列Sと文字列Tで最長共通部分文字列を取得し、最長共通部分文字列の長さが文字列Tと等しくない場合、「array」のフラグを立てる。

 ・上記の2点より、「automaton」、「array」、「both」を判別する。

    void solve() throws Throwable {
        String s = readLine();
        String t = readLine();
        
        int[] sA = new int[27];
        int[] tA = new int[27];
        for (char c : s.toCharArray()) {
            sA[c-'a']++;
        }
        for (char c : t.toCharArray()) {
            tA[c-'a']++;
        }
        
        boolean isAutoMaton = false;
        for (int i = 0; i < 27; i++) {
            if(sA[i] > tA[i]) {
                isAutoMaton = true;
            } else if (sA[i] < tA[i]) {
                pw.println("need tree");
                return;
            }
        }
        
        char[] sX = s.toCharArray();
        char[] tX = t.toCharArray();
            
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < t.length(); j++) {
                if(sX[i] == tX[j]) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                } else {
                    dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        
        boolean isArray = false;
        if(dp[s.length()][t.length()] != t.length()) {
            isArray = true;
        }
        
        if(isAutoMaton && isArray) {
            pw.println("both");
        } else if (isAutoMaton) {
            pw.println("automaton");
        } else if (isArray) {
            pw.println("array");
        }
    }    

C問題

概要

 ・複数のフェンスがある。

 ・フェンスの横幅は1M,縦幅はそれぞれ異なる。

 ・フェンスに色を塗りたい。一回で塗れるのは縦方向、または横方向のみ。横方向に塗る場合は、塗る高さにフェンスが連続してないといけない。

 ・全てのフェンスに色を塗る時の最小の回数を求める。

解答方法(他の人のソースを参考にしてます)

 ・動的計画法を使う。

 ・dp[N+1]に、N本目を横塗りした場合の最小の塗る回数をメモする。

  やり方としては、N本目までに出現しているフェンスから遡って順々に、

  最も高さの低いフェンスから、今回横で塗りたいフェンスの高さの差を求める。

  N-j本目の最小の塗る数 + (i - j - 1)(一本遡る毎に縦塗りをする)+ 求めた高さの差

  N本目からN-j本目まで塗る場合の最小の塗る数を求める。

 

    void solve() throws Throwable {
        int N = readInt();
        int[] a = new int[N + 2];
        for (int i = 0; i < N; i++) {
            a[i+1] = readInt();
        }
        
        int[] dp = new int[N + 2];
        Arrays.fill(dp, N);
        dp[0] = 0;
        
        for (int i = 1; i <= N + 1; i++) {
            int minH = Integer.MAX_VALUE;
            for (int j = i - 1; j >= 0; j--) {
                minH = Math.min(minH,  a[j]);
                int p = Math.max(0, a[i] - minH);
                dp[i] = Math.min(dp[i], dp[j] + i-j-1 + p);
//                System.out.println(i + " " + j + " " + dp[i]);
            }
        }
        
        pw.println(dp[N+1]);
}

1501⇒1586

最高レート更新ヽ(^o^)丿

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-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-21

Codeforces Round #253

| 20:54

・A問題

 重複を除いた文字種の数をカウントする。

 既に使った文字をメモしておく。

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        
        char[] c = br.readLine().toCharArray();
        
        boolean[] used = new boolean[30];
        int sum = 0;
        
        for (char x : c) {
            if (x >= 'a' && x <= 'z') {
                if (!used[x - 'a']) {
                    used[x - 'a'] = true;
                    sum++;
                }
            }
        }
        pw.println(sum);
        
    }    

・B問題

 ある文字列が与えられたときに、

 その文字列の部分文字列を連続して同じになる場合の最長の長さを答える。

 また、引数で指定されたintを文字列の右に加算してよい。

    void solve() throws Throwable {
        char[] c = br.readLine().toCharArray();
        int K = readInt();
        int N = c.length;
        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 2; i + j <= N + K; j+=2) {
                boolean isFalse = false;
                for (int k = 0; k < j / 2; k++) {
                    if (i + j / 2 + k < N) {
                        if (c[i + k] != c[i + j / 2 + k ]) {
                            isFalse = true;
                            break ;
                        }
                    }
                }
                if (!isFalse) {
                    max = max(max, j);
                }
            }
        }
        pw.println(max);
    }    

C,D,Eは解けず。

1400⇒1451

最高レート更新ヽ(^o^)丿