SRM494 DIV2

oxx 230.12pt [rate : 690 -> 747] (+57)

Medium解けたと思ったのに思いっきり間違ってて涙目
3問ともpracticeで解いておきました。

↓以下コード

250 - InterestingParty

最初に全部Setにぶち込んでチェックしていけばらくちん。

import java.util.*;
import static java.lang.Math.*;
public class InterestingParty {
    public int bestInvitation(String[] first, String[] second) {
        int ans = 0;
        int n = first.length;
        Set<String> set = new HashSet<String>();
        for(int i = 0; i < n; i++) {
            set.add(first[i]); set.add(second[i]);
        }
        for(String s : set) {
            int cnt = 0;
            for(int i=0; i<n; i++) {
                if(first[i].equals(s) || second[i].equals(s)) cnt++;
            }
            ans = max(ans, cnt);
        }
        return ans;
    }
}

500 - Painting

本番中に書いたコード
えっこれ縦横の最小値取れば終わりじゃん楽勝じゃじゃんと思って書いて提出 → System Test failed. → なん……だと……
どのケースで落とされたのか実際に見るまで反例思いつかなかった……

BBWW
BBWW
WBBW
WWBB
WWBB
こんなのでたやすく死にます。うわらば

実際に塗れる所を全部塗っていってみて、元の設計図と一緒だったらそのサイズのブラシで塗れることが分かります。
最大値が欲しいので大きい方から試していけばいいです。

import java.util.*;
import static java.lang.Math.*;
public class Painting {
    public int largestBrush(String[] picture) {
        int m = picture[0].length();
        int n = picture.length;

        out: for(int S=min(m,n); 0 < S; S--) {
            boolean[][] check = new boolean[n][m];
            //for(int i=0; i<n; i++) for(int j=0; j<m; j++) check[i][j] = false;

            for(int i=0; i+S<=n; i++) {
                for(int j=0; j+S<=m; j++) {
                   boolean canp = true;
                   in: for(int y=0; y<S; y++) {
                       for(int x=0; x<S; x++) {
                           if(picture[i + y].charAt(j + x) != 'B') { canp = false; break in; }
                       }
                   }
                   if (canp) {
                       for(int y=0; y<S; y++) {
                           for(int x=0; x<S; x++) {
                               check[i + y][j + x] = true;
                           }
                       }
                   }
               }
            }
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if (check[i][j] != (picture[i].charAt(j) == 'B')) {
                        continue out;
                    }
                }
            }
            return S;
        }
        return -1;
    }
}

1000 - AlternatingLane

alternatingになるように木を切らなくてもbeautyは計算できるので、そのままそれぞれ隣り合う木の差の絶対値の期待値の和を求めればいいです。「の」が多い。

E(X+Y+Z) = E(X)+E(Y)+E(Z)

3重ループで解いたらTLE食らいましたが、等差数列の和の公式使うと間に合いました。

(a+l)*n/2 　[a=初項,l=末項,n=項数]

import java.util.*;
import static java.lang.Math.*;
public class AlternatingLane {
    public double expectedBeauty(int[] low, int[] high) {
        double ans = 0.0;
        int N = low.length;

        for(int i = 0; i < N-1; i++) {
            double jac = 0;
            for(int j = low[i]; j <= high[i]; j++) {
                double l = low[i+1];
                double h = high[i+1];
                
                if(j <= l || h <= j)
                    jac += (abs(j-l)+abs(j-h))*(h-l+1)/2.0;
                else {
                    jac += (0+abs(j-h))*(abs(h-j)+1)/2.0;
                    jac += (1+abs(j-l))*(abs(l-j))/2.0;
                }
            }
            ans += jac / (high[i]-low[i]+1) / (high[i+1]-low[i+1]+1);
        }
        return ans;
    }
}

• またすぐSRMがあるのでがんばる。