AtCoder Beginner Contest 125の解説

A - Biscuit Generator

入力:  A\ B\ C
出力: ビスケットの合計枚数
制約:

  •  1 \le A, B, T \le 20
  •  A, B, T \in \mathbb{N}

 T+0.5秒後まで生産するとありますが、この 0.5は無視してよいです。
 A, 2A, 3A秒後にビスケットが生産されるということは、 A秒毎に B枚のビスケットができるということなので、私たちがよく知っている「道のり=速さ×時間」の要領で答えを求めることができます。求める答えは、
 \displaystyle{\left\lfloor{\frac{T}{{A}}}\right\rfloor}\cdot{B}
になります。

auto ip = readAs!(int[]), A = ip[0], B = ip[1], T = ip[2];
writeln((T / A * B));

感想: ごくふつうのA問題でした。

B - Resale

入力:
 N
 V_1\ V_2\ \cdots\ V_N
 C_1\ C_2\ \cdots\ C_N
出力:  X - Yの最大値
制約:

  •  1 \le N \le 20
  •  1 \le C_i, V_i \le 50
  • 入力は全て整数

 i番目の宝石を手に入れるとき、 +V_iの価値と -C_iのコストを得るため、最終的にはその宝石について V_i - C_iの価値を得ることができます(答えは \displaystyle{X}-{Y}=\sum_{{i}}{\left({V}_{{i}}-{C}_{{i}}\right)}ですから、価値とコストを同一視できます)。

したがって、 V_i - C_i > 0のとき、その宝石を取るのが得です。そのような宝石を全て取れば、最大値を求めることができました。

int res = 0;
foreach(i; 0..N) {
	if(V[i] - C[i] > 0) res += V[i] - C[i];
}
res.writeln;

感想: 実装をミスって少し時間がかかってしまった。

C - GCD on Blackboard

入力:
 N
 A_1\ A_2\ \cdots\ A_N
出力: 書き換えた後の N個の整数のGCDの最大値
制約:

  •  2 \le N \le 10^5
  •  1 \le A_i \le 10^9
  • 入力は全て整数

ある整数を好きな整数に書き換えられるということは、 N個の整数 A_1, A_2, \cdots, A_N全体のGCDをとるとき、その整数についてだけGCDの演算をしないようにすることと同等です。
したがって、 N個の整数それぞれについて、それ以外の整数のGCDをとったときの最大値を求める問題だと言い換えることができます。

そこで、 N個それぞれについてループを回して、それ以外の N-1個の整数のGCDをとってあげればわかる…というような解法は O(N^2 \log A)となりTLEします。(今回の問いの中心です)

ここでGCDという演算がどのような性質を持つのか考えてみると、これは結合法則交換法則が成り立ちます。したがって、 i番目の整数以外のGCDは \displaystyle \gcd{{\left( \gcd{{\left({A}_{{1}},{A}_{{2}},\ldots,{A}_{{{i}-{1}}}\right)}}, \gcd{{\left({A}_{{{i}+{1}}},{A}_{{{i}+{2}}},\ldots,{A}_{{N}}\right)}}\right)}}として求めてもよいことがわかります。ゆえに、前処理として
 \displaystyle{L}_{{i}}={\left\lbrace\begin{matrix}{A}_{{0}}&{\quad\text{if}\quad}{i}={0}\\ \gcd{{\left({L}_{{{i}-{1}}},{A}_{{i}}\right)}}&\text{otherwise}\end{matrix}\right.}

 \displaystyle{R}_{{i}}={\left\lbrace\begin{matrix}{A}_{{{N}-{1}}}&{\quad\text{if}\quad}{i}={N}-{1}\\ \gcd{{\left({R}_{{{i}+{1}}},{A}_{{i}}\right)}}&\text{otherwise}\end{matrix}\right.}

とすると(0-indexed)、 \displaystyle \gcd{{\left({L}_{{{i}-{1}}},{R}_{{{i}+{1}}}\right)}}の最大値を求めればよいことになり、時間計算量は O(N \log A_1 + N \log A_N)とすることができました。

なお、よくある累積和については、元 aに対して必ず逆元 -aが存在するため一つの配列で考えることができますが、GCDという演算においては逆元を考えることができないので、 L, Rとして両方から累積GCDを考える必要がありました。

auto L = new int[](N);
auto R = new int[](N);

L.front = A.front;
R.back = A.back;
foreach(i; 1..N) {
	L[i] = gcd(L[i-1], A[i]);
}
foreach_reverse(i; 0..N-1) {
	R[i] = gcd(R[i+1], A[i]);
}
ulong res;
foreach(i; 0..N) {
	if(i == 0) { res = R[1]; continue; }
	if(i == N-1) { res = max(res, L[N-2]); continue; }
	res = max(res, gcd(L[i-1], R[i+1]));
}
res.writeln;

感想: これは300点の中でもかなり難しい方だと思う(実装は大変ではないが、考察が大変)

D - Flipping Signs

入力:
 N
 A_1\ A_2\ \cdots\ A_N
出力:  \displaystyle{\sum_{{{i}={1}}}^{{N}}}{B}_{{i}}の最大値
制約:

  •  2 \le N \le 10^5
  •  -10^9 \le A_i \le 10^9
  • 入力は全て整数

この問題の操作は、となりあった整数の正負を反転するものですが、f:id:private_yusuke:20190428110528p:plain
このように操作を繰りかえすことで任意の2つの整数の正負を反転させることができます。

したがって、整数列の中の偶数の数を kとすると、 kが偶数の場合は全て正にすることができるので \displaystyle\sum_{{i}}{\left|{A}_{{i}}\right|}が答えになります。
一方、 kが奇数の場合はどのようにしても1つの整数が負のままとなるので、 \displaystyle\sum_{{i}}{\left|{A}_{{i}}\right|}-{2}\cdot\min{\left|{A}_{{i}}\right|}を出力すればよいです。

なお、奇数の場合に2回引き算をするのは、 \displaystyle\sum_{{i}}{\left|{A}_{{i}}\right|}の部分で \displaystyle\min{\left|{A}_{{i}}\right|}を足してしまっている分を引かなければならないからです。

ulong cnt = A.count!(i => i < 0);
ulong res = A.map!(i => i.abs).sum;
if(cnt % 2) res -= A.map!(i => i.abs).reduce!min * 2;
res.writeln;

感想: 気づけばすぐに解けそうだった。操作をうまく用いるとどんなことができるか、というところに着目することが大事な問題だった。

A: Submission #5138695 - AtCoder Beginner Contest 125
B: Submission #5140509 - AtCoder Beginner Contest 125
C: Submission #5164574 - AtCoder Beginner Contest 125
D: Submission #5163895 - AtCoder Beginner Contest 125