Hatena::Grouptopcoder

yambe2002の日記

 | 

2015-09-16

SRM668 Div2 1000 AnArray

12:25

Int型の配列A(長さN)と、Int型のKが与えられる。このとき、Aから3つの値p, q, r(0 <= p < q < r < N)を取り出して、その積がKで割り切れるパターンの合計数を求める。

Aの長さ:3~2000

Kの値:1~1000000

Aの値:1~100000000

再帰+メモ化で提出(Hard初提出!)したが、SystemTestでTLEになっていた。

上位陣のコードによると、どうもKの約数をつかってDPしていたようだが、理解できなかったので解説を待つことにしよう。

※以下はTLEになる

public class AnArray {
    private ulong k;
    private int[] a;

    private Dictionary<Tuple<int, ulong, int>, int> Memo = new Dictionary<Tuple<int, ulong, int>, int>();

    private int calc(int idx, ulong carry, int remaining)
    {
        if (idx == a.Length) return 0;
        if (remaining == 0) return 0;

        var key = new Tuple<int, ulong, int>(idx, carry, remaining);
        if(Memo.ContainsKey(key)) return Memo[key];

        var len = a.Length - idx - 1;
        var ret = 0;
        if ((carry * (ulong)a[idx]) % k == 0)
        {
            ret = remaining == 3 ? ((len - 1) * len) / 2 :
                remaining == 2 ? len :
                1;
            ret = ret + calc(idx + 1, carry, remaining);
        }
        else
        {
            ret = calc(idx + 1, carry, remaining);
            ret = ret + calc(idx + 1, carry * (ulong)a[idx], remaining - 1);
        }

        Memo.Add(key, ret);
        return ret;
    }

    public int solveProblem(int[] A, int K) 
    {
        k = (ulong)K;
        return calc(0, 1, 3);
    }
}

結果:Systest Fail(TLE)

SRM668 Div2 600 IsItASquare

12:17

重複のない整数の座標(x, y)が4つ与えられたとき、この4点で正方形になっているかを判定する。

整数のみなので、頂点間の距離をすべて測り、結果が2パターン(辺か対角線の長さ)しかなければOK。

難しく考えすぎて、かなり長いコードを書いていた人が多かった。

public class IsItASquare {
    public double GetDist(int x1, int y1, int x2, int y2)
    {
        return Math.Pow(x1 - x2, 2) + Math.Pow(y1 - y2, 2);
    }

    public List<double> getDists(int idx, int[] x, int[] y)
    {
        var ret = new List<double>();
        for (int i = 0; i < 4; i++)
        {
            if (i == idx) continue;
            ret.Add(GetDist(x[idx], y[idx], x[i], y[i]));
        }

        return ret;
    }

    public string isSquare(int[] x, int[] y) {

        var hs = new HashSet<double>();
        for(int i=0; i<4; i++)
        {
            var dists = getDists(i, x, y);
            dists.ForEach(d => hs.Add(d));
        }

        return hs.Count <= 2 ? "It's a square" : "Not a square";
    }
}

結果:Pass

SRM668 Div2 250 VerySecureEncryption

12:12

文字列messageとkey、それに整数Kが与えられる。keyはmessageと同じ長さで、0~N-1(Nはmessageの長さ)の数字が一意に格納されている。これらを使い、暗号化された文字列を作成する。

key[Index]の値がaだとすると、message上の位置Indexにある文字が、暗号化された結果ではaの位置に移動される。そして、このプロセスをK回繰り返す。

指示通りにやるだけ。Kが偶数なら元の文字列と同じになるが、特にその判定をいれずとも十分に間に合う。

public class VerySecureEncryption {
    private char[] wk(char[] ms, int[] key)
    {
        var ret = new char[ms.Length];
        for (int i = 0; i < key.Length; i++)
        {
            var idx = key[i];
            ret[idx] = ms[i];
        }
        return ret;
    }

    public string encrypt(string message, int[] key, int K) {
        var ret = message.ToCharArray();

        for(int i=0; i<K; i++)  ret = wk(ret, key);

        return new string(ret);
    }
}

結果:Pass

 |