SRM492 DIV2

SRM

xx-
Challenge : +50-(25*3) = -25
total : -25pt
rate : 856 -> 690

＿＿____
|←樹海|
.￣.||￣　　　　　　　 ┗(^o^ )┓三
　　||　　　　　　　　　　　┏┗ 　 三
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣

250 - TimeTravellingCellar

最も利益が大きくなるように、熟成させるワインセラーとその反動でダメにするワインセラーを選べよベジータ

  • え……1番大きいやつから1番小さいやつ引けばいいんじゃないの……？
  • いや違った、それだとprofitが同じでdecayが違うやつがある場合困る
  • じゃあそれ考慮して選べばいいよね
    • ハイ撃墜された！今君撃墜されたよ！！
    • profit = {4,3}, decay = {1,3}を食らって死亡。そうだね！profitを先に無条件で決めちゃだめだね！
  • ということで他の人のコード見る
  • 最大でも50*50なので全部実際に確かめてみればいいだけだった。生きたい。


○せいかい

import static java.lang.Math.*;
public class TimeTravellingCellar {
    public int determineProfit(int[] profit, int[] decay) {
        int ret = 0;
        int N = profit.length;
        for(int i = 0; i < N; i++) for(int j = 0; j < N; j++)
            if(i != j) ret = max(ret, profit[i] - decay[j]);       
        return ret;
    }
}


☓まちがい（本番中に提出したコード）

import static java.lang.Math.*;
public class TimeTravellingCellar {
    public int determineProfit(int[] profit, int[] decay) {
        int pr = 0;
        int idx = 0;
 
        int chkde = 0;
        for(int i = 0; i < profit.length; i++) {
            if(pr <= profit[i]) {
                if (pr == profit[i] && chkde < decay[i]) {
                    chkde = decay[i];                    
                    idx = i;
                    pr = profit[i];
                } else {
                    idx = i;
                    pr = profit[i];
                }
            }
        }
        
        int de = 1 << 21;
        for(int j = 0; j < profit.length; j++) {
            if(idx == j) continue;
            de = min(de, decay[j]);
        }
 
        return pr-de;
    }
}

550 - TimeTravellingGardener

並べて植えてある木のてっぺんを一直線にするために若返らせる必要のある木の数の最小値を返しやがれーーっ！！

  • あ、なんか出来そうな問題
  • 2点選んで直線作って、その直線より大きい木の数数えればいいのかな
  • (49+48+47+ ...)*50 だから余裕で間に合うよね
  • 直線より小さい木があったらその時点でアウトと
  • じゃあ実装
  • できた
  • ……テストケースの1と6が通らない
  • 6はどうだか分からないけど1はどの2本でも取れない時か
  • この時は木の数-1でおｋ
  • 6は……このケースじゃないな
  • どこで間違えてるんだうわーーーわからん！！！
  • タイムアップ


☓まちがい（本番中に提出したコード）

import static java.lang.Math.*;
public class TimeTravellingGardener {
    public int[] d;
    public int determineUsage(int[] distance, int[] h) {
        d = distance;
        int N = h.length;
        int ret = N;
        for(int i = 0; i < N; i++) {
            for(int j = i+1; j < N; j++) {
                int pt = 0;
                double dis2 = calcDist(i, j);
                double a = (double)(h[j] - h[i]) / dis2;
                
                int chk = 0;
                for(int k = 0; k < N; k++) {
                    int st = i;
                    int en = k;
                    int dis3 = calcDist( min(st,en), max(st,en) );
                    double tmp = (a * dis3) + h[i];
                    if((double)h[k] < tmp) break; else if (tmp < h[k]) {
                        pt++;
                    }
                    chk++;
                }
                if(chk == N) ret = min(ret, pt);
            }
        }
        return ret;
    }
    public int calcDist(int t1, int t2) {
        int acc = 0;
        for(int i = t1; i < t2; i++) {
            acc += d[i];
        }
        return acc;
    }
}


doubleの誤差が問題になるらしいけどなんだかそれ以前の問題な気がする……
practiceで解き直したら追記します。たぶん。