Hatena::Grouptopcoder

tochukasoの日記

 | 

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^)丿

 |