AtCoder Beginner Contest 125の解説
A - Biscuit Generator
入力:
出力: ビスケットの合計枚数
制約:
秒後まで生産するとありますが、このは無視してよいです。
秒後にビスケットが生産されるということは、秒毎に枚のビスケットができるということなので、私たちがよく知っている「道のり=速さ×時間」の要領で答えを求めることができます。求める答えは、
になります。
auto ip = readAs!(int[]), A = ip[0], B = ip[1], T = ip[2]; writeln((T / A * B));
感想: ごくふつうのA問題でした。
B - Resale
入力:
出力: の最大値
制約:
- 入力は全て整数
番目の宝石を手に入れるとき、の価値とのコストを得るため、最終的にはその宝石についての価値を得ることができます(答えはですから、価値とコストを同一視できます)。
したがって、のとき、その宝石を取るのが得です。そのような宝石を全て取れば、最大値を求めることができました。
int res = 0; foreach(i; 0..N) { if(V[i] - C[i] > 0) res += V[i] - C[i]; } res.writeln;
感想: 実装をミスって少し時間がかかってしまった。
C - GCD on Blackboard
入力:
出力: 書き換えた後の個の整数のGCDの最大値
制約:
- 入力は全て整数
ある整数を好きな整数に書き換えられるということは、個の整数全体のGCDをとるとき、その整数についてだけGCDの演算をしないようにすることと同等です。
したがって、個の整数それぞれについて、それ以外の整数のGCDをとったときの最大値を求める問題だと言い換えることができます。
そこで、個それぞれについてループを回して、それ以外の個の整数のGCDをとってあげればわかる…というような解法はとなりTLEします。(今回の問いの中心です)
ここでGCDという演算がどのような性質を持つのか考えてみると、これは結合法則と交換法則が成り立ちます。したがって、番目の整数以外のGCDはとして求めてもよいことがわかります。ゆえに、前処理として
とすると(0-indexed)、の最大値を求めればよいことになり、時間計算量はとすることができました。
なお、よくある累積和については、元に対して必ず逆元が存在するため一つの配列で考えることができますが、GCDという演算においては逆元を考えることができないので、として両方から累積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
入力:
出力: の最大値
制約:
- 入力は全て整数
この問題の操作は、となりあった整数の正負を反転するものですが、
このように操作を繰りかえすことで任意の2つの整数の正負を反転させることができます。
したがって、整数列の中の偶数の数をとすると、が偶数の場合は全て正にすることができるのでが答えになります。
一方、が奇数の場合はどのようにしても1つの整数が負のままとなるので、を出力すればよいです。
なお、奇数の場合に2回引き算をするのは、の部分でを足してしまっている分を引かなければならないからです。
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