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

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

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

 |