AtCoder Beginner Contest 136
Updated:
- Review: 2020-05-22
Source codes
Solutions
A - Transfer
$\max(C - (A - B), 0)$ を出力する。
B - Uneven Numbers
直接やることができる。
int ans = 0;
for (auto i = 1; i <= N; i++)
{
stringstream SS;
SS << i;
string S{SS.str()};
if (S.size() % 2 == 1)
{
++ans;
}
}
cout << ans << endl;
C - Build Stairs
前の方は出来るだけ小さければ小さいほど良い。だから貪欲にやるのが最善である。前の数字だけ pre として持っておけば十分である。
ポイント
貪欲法。
D - Gathering Children
$0$-indexed とする。色々方法があるが、ダブリングで正解が求まる。偶奇だけが問題であるから $10^{100}$ 回数ではなく $2^{60}$ 回やれば良い。
$V[k][i] = 2 ^ k$ 回後の初期状態 $i$ の行き先
とすると、次の式で計算が可能である。
for (auto i = 0; i < N; i++)
{
V[0][i] = (S[i] == 'R' ? i + 1 : i - 1);
}
for (auto k = 0; k < 60; k++)
{
for (auto i = 0; i < N; i++)
{
V[k + 1][i] = V[k][V[k][i]];
}
}
ポイント
ダブリングは思いつかなかった。
E - Max GCD
$0$-indexed とする。答えは $sum = \sum _ {i \in N} A _ i$ の約数に限られる。約数を上から列挙して、それが実現可能かを判定すれば良い。
set<ll> candidates;
for (auto i = 1; i * i <= sum; i++)
{
if (sum % i == 0)
{
candidates.insert(i);
candidates.insert(sum / i);
}
}
for (auto it = candidates.rbegin(); it != candidates.rend(); it++)
{
if (solve(*it))
{
cout << *it << endl;
return 0;
}
}
$X$ が答えになるかどうかを判定する方法だが、まず $R[i] = A _ i \% X$ として sort しておく。この和がまず答えの候補である。実際、この回数分をマイナスし、プラスするところは適当に $1$ つだけ選べば良い。全体の和は $X$ の倍数であり、ゆえに $R[i]$ の和も $X$ の倍数であるから、帳尻は必ず合う。
ここで後ろの方をマイナスからプラスしていくのが最善であるのは簡単に示される(形式的な証明は省略)。そこでプラスの回数の和 $A$ とマイナスの回数の和 $B$ の大きい方が答えである。やはり同じ原理で操作が可能であることが示される。この時点で累積和を使えば $O(N ^ 2)$ で答えが出る。後ろの方は、マイナスとしては $R[i]$ であるが、プラスで数える際は $(X - R[i]) \% X$ になることに注意する。
さらに考察を進めると、 $A - B$ を $0$ に近づけるのが最善だとわかり、そして後ろの方からマイナスからプラスに生贄にしていくことによりこの数値は $-X$ していくことがわかる。つまり操作回数は $L = N - total / X$ とした時の $[0, L)$ の和である。これが $K$ 以下であれば答えである。
ポイント
以上をまとめると以下のコードにおさまる。
bool solve(ll X)
{
vector<ll> R(N);
for (auto i = 0; i < N; i++)
{
R[i] = A[i] % X;
}
sort(R.begin(), R.end());
ll total = accumulate(R.begin(), R.end(), 0LL);
int L = N - total / X;
ll need = accumulate(R.begin(), R.begin() + L, 0LL);
return need <= K;
}
考察をしてから解くのが大事である。
F - Enclosed Points
各点ごとにスコアをカウントするものとする。相対的な位置だけが問題である。それぞれの点について左上、左下、右上、右下を $a, b, c, d$ とする。その点を選べば必ず充たされる( $2^{N - 1}$ 通り)。その他は $2^{N - 1} - 1$ 通りのうちダメなものを引くとする。すると次式が正解である。 \[ 2 ^ {N} - 1 - 2 ^ {a + b} - 2 ^ {a + c} - 2 ^ {b + d} - 2 ^ {c + d} + 2 ^ a + 2 ^ b + 2 ^ c + 2 ^ d. \] $(a, b, c, d)$ をあとは平面走査で求めればよろしい。座標圧縮して Segment Tree を使えばよろしい。