AtCoder Beginner Contest 130

Updated:

AtCoder Beginner Contest 130

ソースコード

解法のメモ

A - Rounding

指示通りやるだけ。

B - Bounding

$D _ i$ たちを実際に求める。 $\sharp \{ i \in (N + 1) \mid D _ i \leq X \}$ を出力する。

C - Rectangle Cutting

面積の半分 $WH/2$ が達成できる。 $x = W/2$ かつ $y = H/w$ の場合にのみ 1 を出力する。

D - Enough Array

解法

全体の個数 $N(N + 1) / 2$ から $K$ 未満の個数を引くことにする。尺取り法で実装すればよろしい。

尺取り法の実装

左端 $i$ を普通にループを回す のが良さそうである。

  int j = 0;
  ll ans = 0;
  for (auto i = 0; i < N; i++)
  {
    while (j < N && s + a[j] < K)
    {
      s += a[j++];
    }
    ans += j - i;
    s -= a[i];
  }
  cout << N * (N + 1) / 2 - ans << endl;

ポイント

余事象を使った方が確かに簡単ですね。

E - Common Subsequence

LCS を求める問題とかなり近い。

基本の確認: LCS の求め方

$dp[i][j] = S[0, i)$ と $T[0, j)$ の LCS の長さ

と定めると、これは配る DP で実装できる。初期状態: $dp[0][0] = 1$, otherwise $0$. 答え: $dp[N][M]$. 遷移: \[ \begin{align} dp[i + 1][j] &\gets \max(dp[i + 1][j], dp[i][j]), & & \tag{E.1} \\\ dp[i][j + 1] &\gets \max(dp[i][j + 1], dp[i][j]), & & \tag{E.2} \\\ dp[i + 1][j + 1] &\gets \max(dp[i + 1][j + 1], dp[i][j] + 1) & & \text{ if }S[i] = T[j]. \tag{E.3} \end{align} \]

解説放送の解法

しかしこの問題では、共通文字列の総数を求めるように言われている。上のをほぼ $\mathbin{ {+} {=} }$ にすれば良さそうであるが、それだとうまくいかない。例えば $S = (1, 2)$, $T = (2, 1)$ の場合 $dp[1][1] = 1 + 1 = 2$ となるが、おかしい。これは $() = ()$ の 1 通りを $dp[0][1]$ と $dp[1][0]$ で重複して合算しているからである。

そこで、この遷移を $1$ 通りに絞るようにする。 $i$ だけ進めるのは $DP0$, $j$ だけ進めるのが $DP1$ であるようにする。以下のように定める。

$DP[i][j] = S[0, i)$ と $T[0, j)$ の共通部分列の総数、
$DP0[i][j] = DP[i][j]$ を求めるために $i$ だけ進めたもの、
$DP1[i][j] = DP[i][j]$ を求めるために $j$ だけ進めたもの。

$DP0, DP1$ は $DP$ を求めるための sub_table である。

先ほどの例だと $DP0[0][0] \to DP0[1][0] \to DP1[1][0] \to DP1[1][1]$ のという $1$ 通りの遷移しか許されないので、これで重複がなくなり、答えが正しく求まる。

つまり、初期状態: $DP0[0][0] = 1$, otherwise $0$. 答え: $DP1[N][M]$. 遷移: \[ \begin{align} DP0[i + 1][j] & \mathbin{ {+} {=} } DP0[i][j], & & \\\ DP1[i][j] & \mathbin{ {+} {=} } DP0[i][j], & & \\\ DP1[i][j + 1] & \mathbin{ {+} {=} } DP1[i][j], & & \\\ DP0[i + 1][j + 1] & \mathbin{ {+} {=} } DP1[i][j], & & \text{ if } S[i] = T[j] \\\ \end{align} \]

ポイント

別解はあるが、 snuke さんの方法が綺麗だと思う。

F - Minimum Bounding Box

解答

まず $x, y$ 軸は独立に考えておく。それぞれの軸について、考察するべき点は最大でも $6$ 通りしかない。速度 $-1, 0, 1$ で動く初期座標が最大・最小の点の $6$ パターンである。これらの相対的な位置だけが問題なので、それぞれ速度 $0, 1, 2$ であるとして構わない。軸の「幅」は、区分的に定数かまたは $1$ 次関数である。

したがって、矩形の面積 $S(t)$ は、有限個の区分的に、それぞれ最大でも $2$ 次の連続関数である。時刻 $\infty$ では矩形の面積が $\infty$ になる、または、全部の時間で定数であるから、適当な有界区間で最小値は達成される。ここで区間ごとに次の場合分けをする。

  • $S(t)$ が定数関数の区間:どの時刻でも同じ値を与える。
  • $S(t)$ が $1$ 次関数の区間:正の傾きだろうが負の傾きだろうが、端点で最小値を与える。
  • $S(t)$ が $2$ 次関数の区間:上に凸の場合は、端点で最小値を与える。下に凸の場合は、ただの $2$ 次関数だと最小値が $2$ 次関数の軸の部分という可能性があり得るのだが、今回の場合はない。なぜなら、 $S(t)$ が下に凸であるということは、 $x$ 軸方向にも $y$ 軸方向にも増えている、または、減っているのどちらかである。よって「区間に軸の部分に含まれる」という可能性はない。ゆえに、最小値は区間の端点でとる。

したがって最小値の候補となるのは、 $S(t)$ を区分した際の端点に限られる。すなわち、各軸の傾きが切り替わる点だけである。それはすなわち、速度 $0, 1, 2$ の点がすれ違う時に絞られる。これらを各軸で全列挙して、全部の最小値を求めればよろしい。

実装

各軸ごとに class を作るのが筋がいいだろう。以下では double get(double t); で矩形の幅を与えている。また vector<double> events(); で最大・最小それぞれで、すれ違う時刻を求めている。

class D
{
public:
  vector<double> l, r;
  D() : l(3, infty), r(3, -infty) {}
  void add(double x, int v)
  {
    ++v;
    mins(l[v], x);
    maxs(r[v], x);
  }
  double get(double t)
  {
    double nl = infty, nr = -infty;
    for (auto i = 0; i < 3; i++)
    {
      mins(nl, l[i] + i * t);
      maxs(nr, r[i] + i * t);
    }
    return nr - nl;
  }
  vector<double> events()
  {
    vector<double> ts;
    for (auto i = 0; i < 3; i++)
    {
      for (auto j = 0; j < i; j++)
      {
        double t = (l[j] - l[i]) / (i - j);
        if (t > 0)
        {
          ts.push_back(t);
        }
        t = (r[j] - r[i]) / (i - j);
        if (t > 0)
        {
          ts.push_back(t);
        }
      }
    }
    return ts;
  }
};

後は events() を組み合わせて、それぞれの for (auto t : ts) に対して面積を求めればよろしい。

int main()
{
  // init();
  cin >> N;
  D xd, yd;
  for (auto i = 0; i < N; i++)
  {
    int x, y;
    char d;
    cin >> x >> y >> d;
    if (d == 'L')
    {
      xd.add(x, -1);
      yd.add(y, 0);
    }
    if (d == 'R')
    {
      xd.add(x, 1);
      yd.add(y, 0);
    }
    if (d == 'U')
    {
      xd.add(x, 0);
      yd.add(y, 1);
    }
    if (d == 'D')
    {
      xd.add(x, 0);
      yd.add(y, -1);
    }
  }
  vector<double> ts;
  ts.push_back(0);
  ts.push_back(infty);
  {
    auto nts = xd.events();
    ts.insert(ts.end(), nts.begin(), nts.end());
  }
  {
    auto nts = yd.events();
    ts.insert(ts.end(), nts.begin(), nts.end());
  }
  double ans = 100000000000000000;
  for (auto t : ts)
  {
    double now = xd.get(t) * yd.get(t);
    mins(ans, now);
  }
  cout << fixed << setprecision(12) << ans << endl;
}

ポイント

上はほぼ snuke さんの実装です。非常に参考になる。しかしこれは多分実装ができなかっただろうね。

その他