AtCoder Grand Contest 044

コンテスト前のレート：1771
レート通りのパフォーマンスが得られる順位：514位

A - Pay to Win

問題
10分ほど考えて全くわからなかったのでB問題を先に見てみることに。B問題を解いてから戻って来るも、1時間以上かけても解けず。
終了後に他の人のコードをチラ見して一応通すことはできた。

問題概要

以下の操作を任意の順に回以上行い、をに変えるときの最小コストを求めよ。

• する。コストは。
• する。コストは。
• する。コストは。
• またはする。コストは。

個のテストケースに答えよ。

• 入力は全て整数
• 
• 
• 

思考過程

1. が程度なら、「：をに変える最小コスト」でできそうだが、って一体どうすれば？
2. メモ化再帰で必要なところだけ記録すれば、を考えて、それがつとしても程度に収まりそう？
3. 遷移として、とりあえずそれぞれ割り切れるなら割る。
4. サンプルより、より増える遷移も見る必要がある。遷移を書き直して、再帰のステップ（現在の数に関する処理）を、をして帰ってきた結果の最小値を取るようにしてみたりする。　→無限再帰する。
5. 視点を変えて、から始めての最小値を取るような遷移を試してみる。　→サンプルの1～3ケース目ですら合ったり合わなかったり。
6. ダイクストラ的に、コストが小さい順にやっていけば？　→サンプルの1～3ケース目は多分できたが、4～5ケース目はTLE。
7. 現時点でのを超えた時点で打ち切りすることを考えたりするが、上手くいかず終了。

以下コンテスト後。

1. 上記の4.に戻る。
2. 現在の数をとして、それぞれについて、を割り切れれば割る。割り切れなければ、未満と超で最も近い割り切れる数まで足し引きして割る。　→サンプル5は合ったが4はWA
3. が極端に小さいケースが駄目っぽいので、だけで半分まで減らす遷移を適当に追加する。　→AC

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static Map<Long, Long> map;
    static long n, a, b, c, d, e;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int t = Integer.parseInt(sa[0]);
        for (int i = 0; i < t; i++) {
            sa = br.readLine().split(" ");
            n = Long.parseLong(sa[0]);
            a = Long.parseLong(sa[1]);
            b = Long.parseLong(sa[2]);
            c = Long.parseLong(sa[3]);
            d = Long.parseLong(sa[4]);

            e = Long.MAX_VALUE / d; // オーバーフロー対策
            map = new HashMap<>();
            map.put(0L, 0L);
            map.put(1L, d);
            System.out.println(dfs(n));
        }
        br.close();
    }

    static long dfs(long x) {
        if (map.containsKey(x)) {
            return map.get(x);
        }

        long ret = Long.MAX_VALUE;
        if (x % 2 == 0) {
            ret = Math.min(ret, dfs(x / 2) + a); // ÷2
            if (x / 2 <= e) {
                ret = Math.min(ret, dfs(x / 2) + x / 2 * d); // -1で半分まで
            }
        } else {
            ret = Math.min(ret, dfs(x / 2) + a + d); // 引いて÷2
            ret = Math.min(ret, dfs(x / 2 + 1) + a + d); // 足して÷2
            if (x / 2 < e) {
                ret = Math.min(ret, dfs(x / 2) + x / 2 * d + d); // -1で半分まで
            }
        }
        if (x % 3 == 0) {
            ret = Math.min(ret, dfs(x / 3) + b); // ÷3
        } else {
            long y = x % 3;
            ret = Math.min(ret, dfs(x / 3) + b + d * y); // 引いて÷3
            y = 3 - y;
            ret = Math.min(ret, dfs(x / 3 + 1) + b + d * y); // 足して÷3
        }
        if (x % 5 == 0) {
            ret = Math.min(ret, dfs(x / 5) + c); // ÷5
        } else {
            long y = x % 5;
            ret = Math.min(ret, dfs(x / 5) + c + d * y); // 引いて÷5
            y = 5 - y;
            ret = Math.min(ret, dfs(x / 5 + 1) + c + d * y); // 足して÷5
        }
        map.put(x, ret); // メモ化
        return ret;
    }
}

B - Joker

問題
なんとなくA問題よりとっつきやすそうな感じがして、結果通せたが、計算量ちゃんとわかってたわけではないので微妙・・・。

問題概要

～の番号がついた人が、の正方形に並んだマスにいる。行目には左から順に～番の人、行目には～番の人、・・・のように並んでいる。
これらの人が、人～人の順で外に移動していく（上下左右の方向への移動を繰り返し、外周まで移動する）。
移動の際、まだ人が残っているマスを通るにはコストがかかるとき、全員が外に移動するのにかかる最小コストを求めよ。

• 
• ～は、～の順列

思考過程

1. 各人が外に出るコストは初め、外周の人は、つ内側は、・・・のようにピラミッド型になっている。
2. 例１（）で言えば、番のいずれかがいなくなれば、番のコストがになる。
3. 人が出て行く度に、BFSでコストを更新できそうだがなんかめんどくさそう？
4. 単純に、毎回外までの最短距離を01BFSするのでも結構早いのでは？　→TLE
5. やっぱり元の方針に戻ることを考える。人が出て行く度に更新される範囲は、なんとなく毎回外までBFSするよりははるかに少ない範囲で済みそうだと思った。
6. 実装上は、各マスから外に出るまでのコストを持っておく二次元配列（下記ソース中のb）の他、人が残っている箇所を表す二次元配列（同a）を用意すると、コスト更新のBFSが書きやすそうだった。

※コスト更新のトータルが高々というのは後から解説見てわかったが、底面が一辺の正方形で、高さがの四角錐の体積を考えたら確かにそのくらいかと納得した。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int n2 = n * n;
        int[] p = new int[n2];
        sa = br.readLine().split(" ");
        for (int i = 0; i < n2; i++) {
            p[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        // 人が残っている箇所。全て1で初期化。
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i], 1);
        }
        // 外に出るまでのコスト。上下左右の最短距離（ピラミッド型）で初期化。
        int[][] b = new int[n][n];
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                int ni = n - 1 - i;
                int nj = n - 1 - j;
                b[i][j] = Math.min(i, j);
                b[i][j] = Math.min(b[i][j], ni);
                b[i][j] = Math.min(b[i][j], nj);
            }
        }

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int ans = 0;
        for (int i = 0; i < n2; i++) {
            int x = p[i] / n;
            int y = p[i] % n;
            ans += b[x][y]; // 答えにコストを加算
            a[x][y] = 0; // 指定箇所の人退場
            // 以下コスト更新BFS
            Queue<Integer> que = new ArrayDeque<>();
            que.add(p[i]);
            while (!que.isEmpty()) {
                int cur = que.poll();
                int cx = cur / n;
                int cy = cur % n;
                for (int k = 0; k < 4; k++) {
                    int nx = cx + dx[k];
                    int ny = cy + dy[k];
                    int alt = b[cx][cy] + a[cx][cy]; // （配列a）人が残っていれば+1
                    if (0 <= nx && nx < n && 0 <= ny && ny < n
                            && alt < b[nx][ny]) {
                        que.add(nx * n + ny);
                        b[nx][ny] = alt;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで53分04秒＋1ペナ。143位。
あとはもう1問くらい解けたらいいなとゆっくりA問題をやり直す。
2時間経過時点でCとDも一応チラ見したけど、まともに考える気も起こらず。

最終結果：Bの1完、58分04秒、389位、パフォーマンス1979
レート変動：1771→1793

同日のPASTも94点取れたし、冷えっぱなしの4月を乗り越えた後の5月は割と良い結果続き。