SRM442 DIV2 過去問

問題	結果	備考
250	○	238.74pt
500	△	解説見てから解いた
1000	−

250 - SimpleWordGame

問題文
『playerの言った単語がdictionaryの中にあったら(文字数^2)点が貰える。合計点数を返せ。でも同じの2回言っても点数にならないよ』

そのまま書いた。

public class SimpleWordGame {
    public int points(String[] player, String[] dic) {
        int res = 0;
        HashSet<String> hs = new HashSet<String>();
        for(String s : player) hs.add(s);
        for(String s : dic){
            if(hs.contains(s))
                res += s.length() * s.length();
        }
        return res;
    }
}

500 - Underprimes

問題文
『ある数nを素数の積で表すとき、かける素数の数が素数ならその数をUnderprimeと呼ぶ。A,B間のUnderprimeの数を返せ。ただし1はUnderprimeじゃないよ』
うーん日本語でおｋ

• 素数の積の要素数を配列に保存(素数なら0)

primefactors[primefactors[i]]==0

でUnderprimeかどうか分かる.

• エラトステネスのふるいみたいなものを使う
• DP使って解いてる人もいた

public class Underprimes {
    public int howMany(int A, int B) {
        int res = 0;
        int[] ec = new int[B+1];
        ec[0] = 1; ec[1] = 1;
        for(int i=2; i<=B; i++){
            if(ec[i]==0){
                for(int j=i*2; j<=B; j+=i){
                    for(int k=j; k%i==0; k/=i)
                        ec[j]++;
                }
            }
        }
        for(int i=A; i<=B; i++){
            if(ec[ec[i]]==0) res++;
        }
        return res;
    }
}

メモ

• 1000はあとで