Hatena::Grouptopcoder

(*/∇\*)  黒歴史恥ずかしい (*/∇\*)

Linux/C++組込みエンジニアですが、コンテストではJava使っています。
Profile: とぷこだ こどふぉ ページビュー:16533
 | 

2011-05-03

SRM 505 とぷこだ初参加♪ 23:31 SRM 505 とぷこだ初参加♪ - (*/∇\*)   黒歴史恥ずかしい (*/∇\*)  を含むブックマーク はてなブックマーク - SRM 505 とぷこだ初参加♪ - (*/∇\*)   黒歴史恥ずかしい (*/∇\*)

感想

チャットルームに色んな言葉話す人がenterしてくる雰囲気に圧巻されました。

SystemTestで悔しい><って思ったけども、これを教訓に頑張っていこうと思いました。

divLevelProblemNameStatus
2250SentenceCapitalizerInator  Passed System Test
2500PerfectSequences Failed System Test
2900RectangleArea Compiled

0→1140

250

各センテンスの1文字目を大文字に変換してくださいという問題。

解くだけ。


500

seq[0]+seq[1]+seq[2]+・・・seq[49]==seq[0]*seq[1]*seq[2]*・・・seq[49]

かどうかチェックする問題。

ただし、seq[0]~seq[49]のどれか一つは値を変更すること。

という問題。

seq[n]=xと置換して一次方程式を50回回せばいいのかなと考えた。

seq[0]+seq[1]+・・・+seq[n-1]+seq[n+1]+・・・seq[50]+x=seq[0]*seq[1]*・・・*seq[n-1]*seq[n+1]*・・・seq[50]*x

x-(seq[0]*seq[1]*・・・*seq[n-1]*seq[n+1]*・・・seq[50]*x)=-(seq[0]+seq[1]+・・・+seq[n-1]+seq[n+1]+・・・seq[50])



ExsampleTestをやったら4番で×

これもちょこちょこっと変更してSubmit。


900

少し書いたけどちゃんとは終わらず、Compiledで終わった。

途中のしかアップしてない。

SystemTest

500で死亡。

1個以外全部同じ値のパターンを考えていなかった。(↓のmainメソッドの例)

500 修正後ソース

import java.math.BigInteger;

public class PerfectSequences{

    public static void main(String[] args) {
        PerfectSequences temp = new PerfectSequences();
         System.out.println(temp.fixIt(new int[]{1000000000, 1, 1,
         1, 1, 1, 1, 1, 1}));
        System.out.println(temp.fixIt(new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                                 0, 0, 0, 7774555, 0, 0, 0, 0,
                                                 0, 0, 0 }));
    }

    public String fixIt(int[] seq) {
        if (seq.length == 1) return "Yes";
        for (int i = 0; i < seq.length; i++) {
            if (check(seq, i)) {
                return "Yes";
            }
        }
        return "No";
    }

    private BigInteger MAX = new BigInteger("1000000000");

    private boolean check(int seq[], int n) {
        BigInteger sum = new BigInteger("0");
        BigInteger mul = new BigInteger("1");
        for (int i = 0; i < seq.length; i++) {
            if (n == i) continue;
            if (seq[i] < 0) return false;
            sum = sum.add(new BigInteger(seq[i] + ""));
            mul = mul.multiply(new BigInteger(seq[i] + ""));
        }
        if (mul.subtract(BigInteger.ONE).equals(BigInteger.ZERO)) {
            return false;
        }
        BigInteger mod = sum.mod(mul.subtract(BigInteger.ONE).abs());
        BigInteger div = sum.divide(mul.subtract(BigInteger.ONE));
        if (mod.equals(BigInteger.ZERO) && div.compareTo(MAX) <= 0
                && div.compareTo(BigInteger.ZERO) >= 0) {
            if (new BigInteger(seq[n] + "").equals(div)) {
                return false;
            } else {
                return true;
            }
        } else {
            return false;
        }
    }
}

詰めが甘いのか、時間に制約あると慌ててしまうのか、両方なのかな。

もうちょっと頭の回転速くなったり、危険を察知できるようになりたい。

 |