ABC103 参加記

Tasks - AtCoder Beginner Contest 103

みなさんおつかれさまでした。僕は69(+10)分4完で429位でした。ちょっと苦しかったです...

A - Task Scheduling Problem

A₁,A₂,A₃ のうち最大値から最小値を引くと答えになります。

B - String Rotation

実装問題です。sを2回重ねた文字列を作っておくと楽だと思います。

C - Modulo Summation

m = (a₁ * a₂ * a₃ * ... * a_n) - 1 とすれば (m mod a_i) = a_i - 1 (1<=i<=n) なので Σ(a_i-1) を求めれば答えになります。

D - Islands War

a < b の組 (a, b) に対して (a, b) が分離されているならば(a, b+1)も分離されています。つまりaを固定したとき、aに対するbの最小値を b_min として(a, b_min)を満たせばその他の(a, b)も条件を満たしていることになります。
解法はaを1から順に見ていき if( (今見ているa) == (今まで登場した b_min の最小値) - 1) のときここの橋を取り除きます。このように操作するのが最適です(?)。この回数が答えになります。計算量はO(n)です。

コメント

D解法がうまく説明できないですね... Dは途中まで累積和的な方法で考えていたのですがWAをもらったので方針を転向させられました。