SRM489 DIV2 過去問 - Mostly Sourceless

Easy	○
Medium	○
Hard	−

Easy(250) - BadVocabulary

問題文略

あっはいそのまま実装ですねはい
substringのindex指定ってその数字含むんだっけ含まないんだっけ……
- 調べる、開始が含んで終了は含まない
submit. 227.36pt　遅い
- system test failed.
- えっ
substring(1, s.length()-1)だと長さが1の時に例外吐いて死ぬ
- substring(1, max(1, s.length()-1))に変更
resubmit. 192.21pt → passed system test
うごごごご……

import java.util.*;
import static java.lang.Math.*;
public class BadVocabulary {
    public int count(String badPrefix, String badSuffix, String badSubstring, String[] vocabulary) {
        int ans = 0;
        for(String s : vocabulary) {
            if(s.startsWith(badPrefix)) {
                ans++;
            } else if (s.endsWith(badSuffix)) {
                ans++;
            } else {
                String sub = s.substring(1, max(s.length()-1,1));
                if(sub.indexOf(badSubstring) != -1) ans++;
            }
        }
        return ans;
    }
}

Medium(500) - BuyingFlowers

バラスキーなTeddyとユリスキーなTracyが百合と薔薇を市松模様になるように庭に植えたい、と申しております。
百合薔薇セットがいくつか売りだされていて、その中から適当な組み合わせを選んで購入し
買った苗を全て市松模様になるように庭に植えていく。
植え終わった時の形はR*Cの長方形にならなければいけない。そのとき|R-C|の最小値を返す問題。

yahoo翻訳さんが「a set of」を「一組の」と訳したので選べる箱は2つと勘違いしてしまった
- 正しくは1つ以上の任意の個数の組み合わせ
1辺の長さが奇数の正方形になるときは百合と薔薇の数の差が1
それ以外は百合と薔薇の数が同じ
- 他に条件はないだろうか
- 1辺の長さが奇数の正方形のときは苗の合計が奇数、他は偶数
RとCは苗の合計の約数からとれるね
可能なすべてのRとCの組み合わせを入れたSetをつくって、それをfor文で回して上のチェックする、でいいか
なんかサンプル1つ通らないけどsubmit → system testしたら華麗にTLE
- |R-C|の最小値を計算するだけでいいので組み合わせを保持しとく必要がねェ！！
TLEはしなくなったみたいだけどサンプル通ってないしもちろんsystem test failed
約数を求めるときに2からループ開始してた……なにやってんの……1だよ……素数じゃないんだよ……
- 直して提出 → system test passed

import java.util.*;
import static java.lang.Math.*;
public class BuyingFlowers {

    public int buy(int[] roses, int[] lilies) {
        int init = 1 << 29;
        int ans = init;
        int N = roses.length;
        int lim = 1 << N;
        for(int i = 1; i < lim; i++) {
            int r = 0;
            int l = 0;
            for(int j = 0; j < N; j++) {
                if( ((i >> j) & 1) == 1) {
                    r += roses[j];
                    l += lilies[j];
                }
            }
            int minfac = calcMinFactor(r+l);
            
            if( (r+l)%2 == 0 && r == l ) ans = min(ans, minfac);
            if( (r+l)%2 == 1 && abs(r - l) == 1 ) ans = min(ans, minfac);
        }
        return (ans == init) ? -1 : ans ;
    }
    
    public int calcMinFactor(int n) {
        int res = 1 << 30;
        int lim = (int)sqrt(n);
        for(int i = 1; i <= lim; i++)
            if(n%i==0) res = min(res, abs(n/i-i));
        return res;
    }
}