ks2mのブログ

A - Many Formulae
- 思考過程
B - Insurance
- 思考過程
C - Calculator
- 思考過程

コンテスト前のレート：2080
レート通りのパフォーマンスが得られる順位：315位（1500点、70分14秒）

A - Many Formulae

問題
できてみればそこまで難しいDPでもなかったのに、時間かかってしまった。
例３がなかったらペナも出しまくってたかも。

思考過程

各 $A_i$ が全部で何回足されて何回引かれるか、寄与数を求められないか？　と思うがよくわからない。
"-"が $0$ 個の場合から $\frac{N}{2}$ 個くらいの場合まで分けるとか？　"-"が連続するかどうかを問わなければ二項係数でよいが、連続する場合を取り除くとかは厳しそう。
　
樹形図で伸ばしていくことを考えると、「 $dp[i][j]:=i$ 番目まで見て最後の符号が $j$ の場合の答え」として、 $j=$ "+"へは"+"と"-"から、 $j=$ "-"へは"+"からだけ遷移するようにしてできそう。
　
しかし、どうにも例３が合わない。modの取り方がおかしいかと思って見直してみても変わらず。
上記のDPで、答えだけでなく件数も管理して、 $A_i$ を足し引きするときに件数倍してやる必要があった。

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        int mod = 1000000007;
        long[] dpp = new long[n]; // i番目まで見て末尾が"+"の時の総和
        long[] dpm = new long[n]; // i番目まで見て末尾が"-"の時の総和
        long[] dpp2 = new long[n]; // i番目まで見て末尾が"+"の件数
        long[] dpm2 = new long[n]; // i番目まで見て末尾が"-"の件数
        dpp[0] = a[0];
        dpp2[0] = 1;
        for (int i = 1; i < n; i++) {
            dpp[i] += (dpp[i - 1] + a[i] * dpp2[i - 1]) % mod; // +→+
            dpp[i] += (dpm[i - 1] + a[i] * dpm2[i - 1]) % mod; // -→+
            dpp[i] %= mod;
            dpm[i] = (dpp[i - 1] - a[i] * dpp2[i - 1]) % mod; // +→-
            if (dpm[i] < 0) {
                dpm[i] += mod;
            }
            dpp2[i] = (dpp2[i - 1] + dpm2[i - 1]) % mod;
            dpm2[i] = dpp2[i - 1];
        }
        long ans = dpp[n - 1] + dpm[n - 1];
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで27分15秒＋0ペナ。739位。

B - Insurance

問題
「とりあえず三分探索してみればいいや」と決断するのが遅く、 $N$ で割り忘れる実装ミスをしている箇所があって解消に手間がかかり、時間がかかった。

思考過程

$2x=A_i$ となる $x$ を全部調べればよさそうな気もしたが、中間とかに答えがない根拠が薄い。
　
なんとなく下に凸な関数になっていそうな気がする。
例１で $x$ を $0.5$ ずつ増やしてみたりして、多分合っていそうという気を強める。
最近ABC204-Eで失敗したばかりで抵抗があったが、とりあえず一度三分探索を出すだけ出してみることにする。　→AC

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        // 失う金額の期待値
        double t = 0;
        for (int i = 0; i < n; i++) {
            t += a[i];
        }
        t /= n;

        // 保険料を三分探索
        double l = 0;
        double r = 1e9;
        for (int i = 0; i < 200; i++) {
            double m1 = (l * 2 + r) / 3;
            double m2 = (l + r * 2) / 3;
            double v1 = t + m1 - calc(a, m1);
            double v2 = t + m2 - calc(a, m2);
            if (v1 <= v2) {
                r = m2;
            } else {
                l = m1;
            }
        }
        System.out.println(t + r - calc(a, r));
    }

    // 保険金の期待値
    static double calc(int[] a, double x) {
        double x2 = x * 2;
        double ret = 0;
        for (int i = 0; i < a.length; i++) {
            ret += Math.min(a[i], x2);
        }
        return ret / a.length;
    }
}

ここまで43分44秒＋0ペナ。620位。

C - Calculator

問題

思考過程

値を大幅に増やしていくには、操作 $3, 4$ をメインに使うことになる。
操作 $3$ と $4$ を繰り返すとフィボナッチ数列になっている。
フィボナッチ数列の適当なところに $1$ を足してみると、足さなかった場合との差がフィボナッチ数列になっている。
$N$ をフィボナッチ数列に登場する値のみの和に分解することで、操作 $3$ と $4$ を繰り返しながらどのタイミングで操作 $1$ や $2$ を挟めばよいかがわかる。
　
実装上は、操作 $1$ や $2$ を行った後の最終的な数列で値が $N$ になるインデックスの偶奇によって、操作 $1, 2$ と $3, 4$ が入れ替わるようにする。
上記のインデックスは、フィボナッチ数列で $N$ を超えない最大の値が出現する箇所。
　
$N$ が小さい時（特に $1$ とか $2$ とか）の動作が怖かったので、念のため $130$ 以下の場合は $N$ 回操作 $1$ としてみた。（後から試してみたら、そんな保険を入れなくても通った）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        br.close();

        // 7
        if (n <= 130) {
            System.out.println(n);
            for (int i = 0; i < n; i++) {
                System.out.println(1);
            }
            return;
        }

        int m = 90;
        long[] a = new long[m];
        a[1] = 1;
        for (int i = 2; i < m; i++) {
            a[i] = a[i - 2] + a[i - 1];
        }

        long n2 = n;
        int[] c = new int[m];
        int msb = 0; // 6
        for (int i = m - 1; i > 0; i--) {
            c[i] = (int) (n2 / a[i]);
            n2 -= c[i] * a[i];
            if (msb == 0 && c[i] > 0) {
                msb = i;
            }
        }

        // デバッグ用
//      System.out.println(Arrays.toString(a));
//      System.out.println(Arrays.toString(c));

        int d = msb % 2;
        List<Integer> list = new ArrayList<>();
        list.add(2 - d);
        for (int i = 2; i <= msb; i++) {
            // 元のフィボナッチ数列からの差分調整のため、
            // フィボナッチ数列のp番目の値をc[p]回足したい
            // （c[p]は基本的に（必ず？）1以下）
            int p = msb - i + 1;
            for (int j = 0; j < c[p]; j++) {
                if (d == 0) {
                    list.add(1 + i % 2);
                } else {
                    list.add(2 - i % 2);
                }
            }
            if (d == 0) {
                list.add(3 + i % 2);
            } else {
                list.add(4 - i % 2);
            }
        }

        System.out.println(list.size());
        for (int i : list) {
            System.out.println(i);
        }

        // デバッグ用
//      int x = 0;
//      int y = 0;
//      for (int i : list) {
//          if (i == 1) x++;
//          else if (i == 2) y++;
//          else if (i == 3) x = x + y;
//          else if (i == 4) y = x + y;
//      }
//      System.out.println(x);
    }
}

ここまで81分36秒＋0ペナ。290位。

この後は、DとEを両方見て見事にどっちつかずになって両方とも解けず。
Fは見てもいない。

Dは、上の桁から見ていって初めて1が奇数個出てきた桁は絶対に0にはできないが、それより下の桁の扱いをどうすればいいのかよくわからず。

Eは貪欲に気付ける可能性ゼロではなかったかもしれなかったが、時間が足りなすぎた。

最終結果：ABCの3完1500点、81分36秒、349位、パフォーマンス2027
レート変動：2080→2074（-6）

AとBで出遅れた割には浅い傷で済んでまずまずの結果。Cで救われた。
Eに十分な時間を使えなかったことが心残り。