AtCoder Beginner Contest 130
Updated:
- Review: 2020-05-18
Source codes
Solutions
A - Rounding
指示通りやるだけ。
B - Bounding
$D _ i$ たちを実際に求める。 $\sharp \{ 0 \leq i \leq N \mid D _ i \leq X \}$ を出力する。
C - Rectangle Cutting
面積については、半分 $WH/2$ が必ず達成できる。
切り方については、 $x = W/2$ かつ $y = H/2$ の場合にのみ 1 、残りは 0 を出力する。
D - Enough Array
解法
全体の個数 $N(N + 1) / 2$ から $K$ 未満の個数を引くことにする。尺取り法で実装すればよろしい。
尺取り法の実装
左端 $i$ を普通にループを回す のが良さそうである。
半開区間 $[left, right)$ を意識して実装する。
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 の求め方
Definition
$dp[i][j] = S[0, i)$ と $T[0, j)$ の LCS の長さ
と定めると、これは配る DP で実装できる。
Initial state
初期状態： $dp[0][0] = 1$, otherwise $0$.
Answer
答え： $dp[N][M]$.
Transition
遷移は以下の通り。
\[
\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$ であるようにする。以下のように定める。
Definition
$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$ 通りの遷移しか許されないので、これで重複がなくなり、答えが正しく求まる。
Initial state
初期状態： $DP0[0][0] = 1$, otherwise $0$.
Answer
答え： $DP1[N][M]$.
Transition
遷移は以下の通り。
\[
\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$ の点がすれ違う時に絞られる。これらを各軸で全列挙して、全部の最小値を求めればよろしい。
実装で間違いやすいところ
- 負の時刻を考慮から確実にはずす。 すれ違う時刻を求めると負になる場合があるが、これは実現されないので候補から排除する。
- 同様に、時刻 $0$ を確実に考慮にいれる。
- 初期値は $0$ の時刻のものを使う。 $10^{18}$ 程度では足りない。
- 大きい数字を扱っているので、
long double型を使う。 実装にもよるが、double型だと誤差が出て WA となる可能性がある。
解説放送の実装
各軸ごとに 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 さんの実装です。非常に参考になる。しかしこれは多分実装ができなかっただろうね。