A.ABD(100)

問題

https://beta.atcoder.jp/contests/abc099/tasks/abc099_a

方針

nが999以下のときはABC、1000以上のときはABD

雑記

特になし

B.Stone Monument(200)

問題

https://beta.atcoder.jp/contests/abc099/tasks/abc099_b

西からk番目の高さがk(k+1)/2メートルの木がある。それぞれの木は各々1メートルごとに立っている。今、雪がxメートル積もっているとき、ある西側の木がaメートル、東側の木がbメートルであった。雪が積もっている高さを求めよ。

方針

方程式を解くだけである。k-1番目とk番目の木として考えると、a+x=k(k-1)/2,b+x=k(k+1)/2である。これを解くとk=b-aとなるからx=(b-a)(b-a-1)/2-aである。

雑記

特になし

C.Strange Bank(300)

問題

https://beta.atcoder.jp/contests/abc099/tasks/abc099_c

以下の硬貨がある。

1円
6¹円、6²円、6³円、...
9¹円、9²円、9³円、...

この硬貨を使用してちょうどN円(N<=10⁵)払うとき、最小の硬貨の枚数は何枚か。

方針

10⁵以下で6^k,9^k(k>=1)の整数は何があるのかまずは実験した。すると使える硬貨は全部で12枚であることがわかった。最初は大きい硬貨から貪欲に払うといった方法で解けばよいのではないかと考えた。しかし、貪欲に解くとサンプルケース3でWAになる。（サンプルケースありがとう）。つまり例えば13円を払うとき貪欲に払うと、13=9+1+1+1+1となるから5枚必要だが、13=6+6+1とすると3枚で払うことができる。貪欲では上手くいかないとわかったので別の方法を考える。硬貨の遷移を考えると、例えば6円の硬貨を持っているとき、x-6円のときは6円の硬貨1枚で払えることがわかる。そうでない場合は1円を払ってx-1円から遷移すればいいことに気がついた。すなわちDPができる。DPの遷移は以下である。

c[i]円の硬貨を持っているとき、x円への遷移は

dp[x] = min(dp[x-c[i]]+1, dp[x-1]+1)

である。これをすべて硬貨を使って、100000円までのdpテーブルを作成すればよい。ただし、遷移しなくてもよい場合があるのでdp[x]とmin(dp[x-c[i]]+1, dp[x-1]+1)のminで更新する。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            Set<Integer> set = new HashSet<>();

            set.add(1);
            for (int i = 1; i < 10; i++) {
                int m = (int)Math.pow(6, i);
                if (m <= 100000) {
                    set.add(m);
                } else {
                    break;
                }
            }

            for (int i = 1; i < 10; i++) {
                int m = (int)Math.pow(9, i);
                if (m <= 100000) {
                    set.add(m);
                } else {
                    break;
                }
            }

            Integer[] c = new Integer[set.size()];
            set.toArray(c);
            Arrays.sort(c);

            int[] dp = new int[100010];
            Arrays.fill(dp, INF);
            for (int i : c) {
                dp[i] = 1;
            }

            for (int j = 1; j < 100010; j++) {
                for (int i = 0; i < c.length; i++) {
                    if (j - c[i] < 0) continue;
                    dp[j] = min(dp[j], min(dp[j-c[i]]+1, dp[j-1]+1));
                }
            }

            out.println(dp[n]);

        }

雑記

AOJで同じ問題をやったことがあった。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=jp なので、貪欲でNGだったときにDPでできるという確信が持てた。ちなみに貪欲でできるときは各硬貨が倍数になっているときである。例えば日本国の硬貨は 1 5 10 50 100 500 と大きい数の硬貨は小さい数の硬貨の倍数になっているため貪欲でできる。

D.Good Grid(400)

問題

https://beta.atcoder.jp/contests/abc099/tasks/abc099_d

N×Nマスのグリッドがある。上からi行目の左からj列目のマスを(i,j)とする。各マスにはk(1<=k<=C)が塗られており、はじめに(i,j)は色c_(i,j)で塗られている。このグリッドは以下の条件を満たすとき、良いグリッドとする。

1<=i,j,x,y<=N を満たす任意のi,j,x,y
(i+j)%3 = (x+y)%3 ならば (i,j)の色と(x,y)の色が同じ
(i+j)%3 != (x+y)%3 ならば (i,j)の色と(x,y)の色が異なる

グリッドが良いグリッドになるように0個以上のマスを塗り替える。あるマスにおいて、塗り替える前の色がXであり、塗り替えた後の色がYである場合に感じる、そのマスに対して感じる違和感はD_(X,Y)である。すべてのマスに対して感じる違和感の和のとりうる最小値を求めよ。

方針

グリッドが良いグリッドになる条件をノートで実験すると、各マスは0,1,2のいずれかの値になることがわかる。mod3なので当たり前だが。また各マスを色c_(i,j)からkにするときの違和感(=コスト)を考えてみると、そのコストはすでにD[c[i][j]][k]で与えられている。mod3で分けられる各マスがそれぞれ異なる色l,m,nで塗るときのコストを最小化すればいいのではないかと気づいた。最初これはナイーブに考えると、色の組み合わせがC³でN×Nのグリッドの各マスを考えるのでN²、合わせて計算量はO(C³・N²)になると見積もることができた。これは明らかに間に合わない。少し考えると、mod3で分けられるマスをある数に塗り替えるときのコストは1度だけ計算すればいいことがわかる。これはメモ化すればいいのでは?と思い実装した。

       long[][] memo;
        int N, C;
        int[][] d,c;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            N = in.nextInt(); C = in.nextInt();
            d = new int[C][C];
            c = new int[N][N];

            for (int i = 0; i < C; i++) {
                for (int j = 0; j < C; j++) {
                    d[i][j] = in.nextInt();
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    c[i][j] = in.nextInt();
                }
            }

            memo = new long[3][C+1];
            for (int i = 0; i < 3; i++) {
                Arrays.fill(memo[i], -1);
            }

            long ans = Long.MAX_VALUE/2;
            for (int i = 1; i <= C; i++) {
                for (int j = 1; j <= C; j++) {
                    for (int k = 1; k <= C; k++) {
                        if (i == j || j == k || k == i) {
                            continue;
                        }
                        ans = Math.min(ans, dfs(0, i) + dfs(1, j) + dfs(2, k));
                    }
                }
            }

            out.println(ans);

        }

        long dfs(int mod, int to) {

            if (memo[mod][to] > 0) {
                return memo[mod][to];
            }

            int ret = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if ((i+1 + j+1) % 3 == mod) {
                        ret += d[c[i][j]-1][to-1];
                    }
                }
            }

            return memo[mod][to] = ret;
        }

雑記

本番に一発ACできてうれしかった。なんとなく同じwriter(namonakiacc)の過去のD問題と同じような雰囲気の問題であった。メモ化の計算量はO(C³+N²)だと思われる。ただACしたときの実行時間が1762msであったので制限時間ギリギリであり定数項が大きいのかもしれない。なお解説を見てわかったが、メモ化ではなく、事前にmod3で分けたとき、もともと存在する色のマスの個数をカウントしておけばよさそうである。

数学/競プロメモ

AtCoder Beginner Contest 099

A.ABD(100)

問題

方針

雑記

B.Stone Monument(200)

問題

方針

雑記

C.Strange Bank(300)

問題

方針

雑記

D.Good Grid(400)

問題

方針

雑記