Hatena::Grouptopcoder

tochukasoの日記

2014-08-12

**AtCoder Regular Contest 27

| 17:09

3完

A問題

問題概要

・時間と分が引数で与えられる。

・18時まであと何分あるかを返却せよ

解き方
    void solve() throws Throwable {
        int H = (17 - readInt()) * 60;
        int M = 60 - readInt();
        pw.println(H+M);
    }

B問題

問題概要

・長さが同じ2つの文字列が与えられる。

・この2つの文字列は同一の数字を示す。

・アルファベットはそれぞれ0~9の可能性がある。

・矛盾をおこなさない数字の組み合わせが何通りあるかを答える。

解き方

・効率的な方法は分からないので愚直にシミュレーション

・部分点ゲット・・・・・

・うーん。改善方法が分からない。

・アルファベットの絞り込みを行っている個所を2重ループで回すように変更。

AC!! 嘘解法っぽいなぁ・・・

・アルファベットを絞り込んでいるときに関係性があるアルファベットの数字の可能性も消去しているはずだけど、

 漏れがあるのかも

    void solve() throws Throwable {
        
        int N = readInt();
        String string1 = readString();
        String string2 = readString();
        char[] s1 = string1.toCharArray();
        char[] s2 = string2.toCharArray();
        boolean[][] prohibitAlphabets = new boolean[26][10];
        
        for (int Z = 0; Z < 2; Z++) {
            
        for (int i = 0; i < N; i++) {
            char c1 = s1[i];
            char c2 = s2[i];
            boolean isNum1 = false;
            boolean isNum2 = false;
            if (c1 < 'A') {
                isNum1 = true;
            }
            if (c2 < 'A') {
                isNum2 = true;
            }
            if(isNum1) {
                if(!isNum2) {
                    for (int j = 0; j < 10; j++) {
                        if(j == Character.getNumericValue(c1)) continue;
                        prohibitAlphabets[c2-'A'][j] = true;
                    }
                }
                
            } else {
                if(i == 0) {
                    prohibitAlphabets[c1 - 'A'][0] = true;
                }
                if(!isNum2) {
                    for (int j = 0; j < 10; j++) {
                        if(prohibitAlphabets[c1 - 'A'][j]) prohibitAlphabets[c2-'A'][j] = true;
                        if(prohibitAlphabets[c2 - 'A'][j]) prohibitAlphabets[c1-'A'][j] = true;
                    }
                }
            }
 
            if(isNum2) {
                if(!isNum1) {
                    for (int j = 0; j < 10; j++) {
                        if(j == Character.getNumericValue(c2)) continue;
                        prohibitAlphabets[c1-'A'][j] = true;
                    }
                }
            } else {
                if(i == 0) {
                    prohibitAlphabets[c2 - 'A'][0] = true;
                }
            }
        }
        }
        long res = 1;
        boolean[] used = new boolean[26];
 
        for (int i = 0; i < N; i++) {
            long count = 0;
            char c1 = s1[i];
            char c2 = s2[i];
            for (int j = 0; j < 10; j++) {
                if (c1 < 'A' || c2 < 'A' || used[c1 - 'A'] || used[c2 - 'A']) {
                    count = 1;
                    break;
                }
                if(prohibitAlphabets[c1 - 'A'][j] || prohibitAlphabets[c2 - 'A'][j]) continue;
                count++;
            }
            if(c1 >= 'A') {
                used[c1-'A'] = true;
            }
            if(c2 >= 'A') {
                used[c2-'A'] = true;
            }
            res*=count;
            
        }
        
        pw.println(res);
    }

C問題

問題概要

・典型的DP

・ナップザック問題が少し複雑になった感じ

・2種類のチケットとチケットで買えるものがあって、価値の総和が最も高い場合にいくつになるかを返却する。

・2種類のチケットのうち、1種類のチケットは物を買う時に常に消費しなければならない制約がある

解き方

・必須チケットじゃなくて通常のチケットを優先して使えばよさそう

・部分点もある問題かぁ・・・・

・買えるもののインデックス(300以下)、必須チケットの使用枚数(300以下)、通常チケットの使用枚数(300以下)の値毎に

 最大の価値をメモすることでDP出来そう。

 でも、300*300*300=2700万要素の配列かぁ・・・・メモリ足りなそうだなぁ。

・うーーーーん。どうやって解くべきか。・・・・intのメモリ確保容量ってどれくらいだろう。

 4byteかぁ。ということは、100メガちょっと。ん?足りそうだぞ。

・MLE・・・・・30点ゲット

・やっぱりC問題はまだ解けないよなぁ。

・と思いつつもよくよく見直してlong型で配列を宣言していたのをint型に変更したらAC

    int X, Y, N;
    int[] mustTikets = null;
    int[] happiness = null;
    static int[][][] dp = null;
 
    void solve() throws Throwable {
        
        X = readInt();
        Y = readInt();
        N = readInt();
        mustTikets = new int[N];
        happiness = new int[N];
        for (int i = 0; i < N; i++) {
            mustTikets[i] = readInt();
            happiness[i] = readInt();
        }
        
        dp = new int[N][X+1][Y+1];
        pw.println(dfs(0,0,0));
    }
 
    int dfs(int i, int special, int normal) {
        if (i == N)
            return 0;
        if (dp[i][special][normal] != 0)
            return dp[i][special][normal];
        if (special >= X || mustTikets[i] + special + normal > X + Y) {
            return dp[i][special][normal] = dfs(i + 1, special, normal);
        } else {
            int last = Math.max(0, mustTikets[i] - (Y - normal) - 1);
            return dp[i][special][normal]= Math.max(dfs(i + 1, special, normal),
                    dfs(i + 1, special + 1 + last,
                            normal + (mustTikets[i] - last - 1))
                            + happiness[i]);
        }
    }

結果は59位で、2級に昇級出来ましたヽ(^o^)丿

時間があれば、D問題の部分点も取れそうだったのに残念

2014-07-23

SRM628 Div2

| 20:58

1完

easy

概要

・チェス盤とビショップの駒が与えられる。

・ビショップの現在位置の座標と移動したい場所の座標が与えられる。

・移動出来ない場合は-1,移動できる場合は移動に掛る回数を返却する。

解答方法

・x軸の距離とy軸の距離が等しい場合、1回で移動できる。

・x軸の距離とy軸の距離の偶奇が等しくない場合、移動できない。

 等しい場合、2回で移動できる。

	public int howManyMoves(int r1, int c1, int r2, int c2)
	{
	    
	    int p1 = Math.abs(r1 - r2);
	    int p2 = Math.abs(c1 - c2);
	    
	    if(p1 == 0 && p2 == 0) return 0;
	    
	    if(p1 == p2) {
	        return 1;
	    } else if (p1 % 2 == p2 % 2) {
	        return 2;
	    } 
	    return -1;
        }

medium

概要

・(,),{,},[,],Xで構成される文字列が与えられる。

・各カッコの同期が取れているかを操作する。また、Xは任意の文字に置き換えることが出来る。

XMLファイルの様に入れ子構造は許容しないものとする。

解答方法

・各種カッコが連続しているものを除外する。

・Xをそれぞれ6種類の文字に置き換えて、上記の処理を回す。

    private boolean dfs(String s) {
        while(s.contains("[]") || s.contains("{}") || s.contains("()")) {
            s = s.replaceAll("\\(\\)", "");
            s = s.replaceAll("\\[\\]", "");
            s = s.replaceAll("\\{\\}", "");
        }
        
        if(s.length() == 0) {
            return true;
        } else {
            if(s.contains("X")) {
                return dfs(s.replaceFirst("X", "[")) ||
                        dfs(s.replaceFirst("X", "{")) ||
                        dfs(s.replaceFirst("X", "(")) ||
                        dfs(s.replaceFirst("X", "]")) ||
                        dfs(s.replaceFirst("X", "}")) ||
                        dfs(s.replaceFirst("X", ")")) ;
                
            }
        }
        
        return false;
    }
    
	public String ifPossible(String expression)
	{
	    boolean b = dfs(expression);
	    return  b ? "possible" : "impossible";
        }

実際には、easyの問題は幅優先探索を使用して、

何回で移動出来るか試してたので、実装にちょっと時間かかりましたorz

medium問題は、Xのうまい取扱い方法が分からなくて

実装ミスりました。Xが5回以内しか出現しないという緩めの制約だったので、

全通り試せばいいとは思ってたんですが・・・・

918⇒891

グレーに落ちました。

8月からは月一ぐらいしか参加できなそうなのになぁ・・・・