LeetCoding Challenge Oct. 26: Champagne Tower

LeetCode October Challenge の 26 日目。

今日の問題は Champagne Tower。

問題の概要

• 高さがグラス 100 段分のピラミット状 (ただし奥行きはどの段もグラス 1 個分) に構成されるシャンパンタワーにグラス n 配分のシャンパンを注いだ場合の任意の箇所のグラスに流れ込むシャンパンの量を求める
• 絵で表すと一目瞭然
  • 

考え方

• これは パスカルの三角形 に関係してそうな問題ですね
  • とは言えど、パスカルの三角形の特性を利用すれば簡単に解ける問題かと言えばそうではなかった… 🙄
• うまい解法が思いつかないので、まずはナイーブなやり方として、実際に注ぐ操作をシミュレートする実装をしてみる
  • つまりは、最上段のグラスから順にシャンパンを注いで溢れた分を直下の左右のグラスに均等に割り振る… を再帰的に繰り返すやつ
  • 各段のグラスそれぞれの量を記録するために O(n^2) (n は求めたいグラスの上からの段数) の空間計算量を必要としてしまう…
  • どこかに不具合があるのか、大きな値を与えたときにとても重くなってしまったぞ… 😰
• あまり筋がよさそうではないので、仕切り直して別のアプローチを試みよう
• 流れ込むシャンパンの量を知りたいグラスに着目して、そのグラスに流れ込むまでに至る経路を逆に (ボトムアップに) 求めてみてはどうかな？ 🤔
  • 絵にするとこんな感じ
  • 
  • 赤い点が着目しているグラスで、そのグラスのシャンパン量を知るためには緑色の部分だけを把握すればいい
• そういうわけで実装 → submit → 一発 accept 🤗
  • Runtime 3ms で Your runtime beats 77.03 % of java submissions. なので、もうちょっと頑張りたい 😤
• ボトムアップ以外に方法はないかな…？
  • そう言えば以前に Pascal's Triangle II を解いたときはどうやってたっけかな…？ → これはトップダウンで解いてるな 🤔
    • このとき空間計算量は O(n) で済ませていた。このやり方でやってみよう！
• 空間計算量 O(n) のトップダウンアプローチ
  • 最上段から順にループで処理するよ
  • i 段目における各グラスに流れ込むシャンパンの総量を長さ n の配列で保持するよ
    • 一つ上の段の結果を次の段の計算に使うよ
• 実装してみて submit → runtime が 1ms 縮まった 💪
  • せっかくなので、1ms にたどり着きたい…
  • シャンパンタワーが左右対称であることを利用して、計算量を 1/2 にしてみた → めでたく rumtine 1ms / beats 100% 達成 🎉

コード

ボトムアップに流入経路をたどる方法

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        // あるグラスから溢れてその直下の左右それぞれのグラスに流れ込むシャンパンの量を保持する二次元配列
        double[][] table = new double[query_row + 1][query_row + 1];
        bottomUp(poured, query_row, query_glass, table);

        return Math.min(table[query_row][query_glass] * 2 + 1, 1.0);
    }

    double bottomUp(double amount, int row, int glass, double[][] table) {
        if (table[row][glass] == 0.0) {
            if (row == 0) {
                table[0][0] = (amount - 1) / 2;
            } else {
                table[row][glass] =
                        ((glass > 0 ? bottomUp(amount, row - 1, glass - 1, table) : 0)
                                + (glass < row ? bottomUp(amount, row - 1, glass, table) : 0)) / 2 - 0.5;
            }
        }

        return Math.max(table[row][glass], 0);
    }
}

トップダウン・空間計算量 O(n) の解法

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[] row = new double[query_row + 1];
        row[0] = poured;

        for (int r = 1; r <= query_row; r++) {
            double prev = 0.0;

            int center = (r - 1) / 2;
            for (int x = r; x > center; x--) {
                double t = Math.max((row[x - 1] - 1) / 2.0, 0);
                row[x] = prev + t;
                prev = t;
            }

            row[center] = row[r - center];
        }

        return Math.min(row[Math.max(query_glass, query_row - query_glass)], 1.0);
    }
}