JMK no matter what

옛날에 풀었던 것 같은데.. 음.. --;; 모르겠다. C# 으로 돌아봤다. 냐옹

250 DesignCalendar; /math 프로그래밍 대회 문제란 생각이 별로 들지 않는군요 'ㅅ'

lang:c#
public class DesignCalendar 
{
    private int gcd(int a, int b)
    {
        while(a % b != 0)
        {
            int c = a % b;
            a = b; b = c;
        }
        return b;
    }
    public int shortestPeriod(int dayLength, int yearLength) 
    {
        if (yearLength % dayLength == 0) return 1;
        int rem = yearLength % dayLength;
        int g = gcd(rem, dayLength);
        return dayLength / g;
    }
}

600 LocatingTreasure; digital root 를 구하는 함수 dig() 에 대해, dig(A), dig(A\^2), dig(A\^3), ... 만큼 상하좌우로 움직이는 것을 K번 했을 때 최종 위치는? 뭐 이런 문제. K 가 커서 나는 logK 타임에 행렬로 풀어야 하나 하면서 고민했는데, 생각해 보면 digital root 는 mod 9 인 셈이기 때문에 항상 주기가 생기게 된다. 8! x 4 번 움직이면 항상 제자리에서 돈다는 것을 증명할 수 있고, 따라서 나머지만 적당히 시뮬레이션 해주면 오케이.

lang:c#
public class LocateTreasure 
{
    public string location(int K, int multi) 
    {
        long y = 0, x = 0;
        const int M = 40320 * 8;
        int d = 1;
        int simulate = Math.Min(K, K % M + M);
        // simulate the first few steps
        Console.WriteLine("Simulating {0} steps ..", simulate);
        for (int i = 0; i < simulate; ++i)
        {
            switch (i % 4)
            {
                case 0: y += d; break;
                case 1: x += d; break;
                case 2: y -= d; break;
                default: x -= d; break;
            }
            d = (d * multi) % 9; if (d == 0) d = 9;
        }
        return x.ToString() + " " + y.ToString();
    }
}

900 PSequence; 주어진 숫자들을 mod p 에 따라 분류한 뒤, 한 그룹에서 수가 연속될 수 없다고 생각하고 푼다. 이 때 그룹의 원소들이 같으면 경우의 수도 같다는 것을 이용한 DP. C# 에서 GetHashCode() 에서 Array.GetHashCode() 썼다가 매번 다른 값이 돌아오는 덕분에 삽질 좀 함. GetHashCode() 등은 Resharper 에서 짜줄 것 같은데, 음, 아닐려나

lang:c#
public class PSequence 
{
    private const int MOD = 1234567891;
    private class State
    {
        int[] groups;
        int lastSize;
        public State(int[] g, int ls)
        {
            groups = g;
            lastSize = ls;
        }

        public override int GetHashCode()
        {
            int ret = lastSize;
            foreach (int x in groups)
                ret = unchecked(ret * 3137 + x);
            return ret;
        }

        public override bool Equals(object obj)
        {
            State other = (State)obj;
            if (lastSize != other.lastSize) return false;
            for (int i = 0; i < groups.Length; ++i)
                if (groups[i] != other.groups[i])
                    return false;
            return true;
        }
    }

    Dictionary<State, uint> cache;
    private uint solve(int[] groups, int lastSize)
    {
        if (groups[groups.Length - 1] == 0) return 1;        
        State key = new State(groups, lastSize);
        if (cache.ContainsKey(key)) return cache[key];
        uint ret = 0;        
        Boolean seen = false;
        for(int i = 0; i < groups.Length; ++i) if(groups[i] > 0)
        {            
            if (groups[i] == lastSize)
            {
                if (!seen)
                {
                    seen = true;
                    continue;
                }
            }
            int[] next = (int[])groups.Clone();
            next[i]--;
            Array.Sort(next);
            ret = (ret + solve(next, groups[i] - 1)) % MOD;            
        }
        cache[key] = ret;
        return ret;
    }
    public int count(int[] S, int p) 
    {
        cache = new Dictionary<State, uint>();
        int[] cnt = new int[p];
        for (int i = 0; i < S.Length; ++i)
            cnt[(S[i] + 1000 * 1000) % p]++;
        int nonzero = 0;
        for(int i = 0; i < p; ++i) if(cnt[i] > 0) ++nonzero;
        int[] g = new int[nonzero];        
        nonzero = 0;
        for(int i = 0; i < p; ++i) if(cnt[i] > 0) g[nonzero++] = cnt[i];
        Array.Sort(g);
        long sol = solve(g, 0);
        foreach (int i in g)
            for (int j = 2; j <= i; ++j)
                sol = (sol * j) % MOD;
        Console.WriteLine("{0} instances evaluated", cache.Count);
        return (int)sol;
    }

}

~~~~