AtCoder Beginner Contest 103 - 情報妖精の競プロ日記

AtCoder Beginner Contest 103 (ABC103) の解説です。
AtCoder Beginner Contest 103 旧版
 AtCoder Beginner Contest 103 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 103
rated 1200
7/21(土) 21:00 ～ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分

方針

全完

A - Task Scheduling Problem

まず、順番を並び替えても問題は無いので $A_1 \leq A_2 \leq A_3$ とします。
最初に $A_1$ を選ぶものとします。
この時、 $A_2$ を次に選ぶと $|A_2 - A_1| + |A_3 - A_2| = A_3 - A_1$ のコストとなり、 $A_3$ を次に選ぶと $|A_3 - A_1| + |A_3 - A_2| = A_3 - A_1 + |A_3 - A_2| > A_3 - A_1$ のコストとなることから、必ず $A_2$ を選ぶべきです。
また、最初に $A_2$ を選んだ場合、次にどちらを選んでも $|A_3 - A_1|$ のコストは掛かり、 $A_3$ を最初に選んだ時のコストは絶対値の関係上 $A_1$ を最初に選んだ時と等しい話になるので、結局最適に選んだ時のコストは $A_3 - A_1$ になります。
つまり、答えは $\max (A_1, A_2, A_3) - \min (A_1, A_2, A_3)$ です。
ちなみに、この答えは $A$ が3個の時だけでなく任意の個数について成り立ちます。

B - String Rotation

まず、文字列 $U = S_1S_2 \cdots S_{|S|}S_1S_2 \cdots S_{|S|}$ とします。
この時、回転を1回行った $S$ の文字列は $S_{|S|}S_1S_2 \cdots S_{|S|-1} = U_{|S|}U_{|S|+1} \cdots U_{2|S|-1}$ として表すことができます。
つまり、回転を $n$ 回行った文字列は $U_{|S|-n+1}U_{|S|-n+2} \cdots U_{2|S|-n}$ として表すことができます。
後はこれが $T$ と一致するか比較すれば良いです。

C - Modulo Summation

整数 $m = a_1 \times a_2 \times \cdots \times a_N - 1$ とします。
この時、 $m$ を $a_1$ で割った余りは $a_1 - 1$ になります。
同様に、 $m$ を $a_2$ で割った余りは $a_2 - 1$ になり……ということは $f(m) = a_1 - 1 + a_2 - 1 + \cdots + a_N - 1 = \sum_{i=1}^{N} a_i - N$ となります。
また、これ以上大きな答えはあり得ないので $\sum_{i=1}^{N} a_i - N$ を出力すれば良いです。

D - Islands War

まず、全ての橋を落としてしまえば自明に条件は達成できるので、少なくとも答えは $N-1$ 以下であることが分かります。
また、 $a_i \leq x < b_i$ を満たす $x$ 番目の橋について、少なくとも1つの橋を落とせば要望は達成できるので、全部落とす必要はないことも分かります。
そこで、なるべくなら同時に複数の要望を達成できるような橋を落としたいですよね？
そこで、まずは $a_i$ についてソートすることにより、 $a_1 \leq a_2 \leq \cdots \leq a_M$ となっているものとします。
この時、 $a_M$ 以上の橋を落とさないと少なくとも $M$ 番目の要望は達成できないので、この要望を達成するための橋をどこで落とせば良いか考えます。
この時、少なくとも落とす橋は $b_M$ 未満であることは自明です。
また、なるべく多くの橋を落としたいことを考えると、 $a_M$ 番目の橋を落とした方が良いことが分かります。
この時、 $a_M < b_i$ を満たす全ての $i$ について $i$ 番目の要望が達成できたので、これを除外します。
後は要望を満たしてない $a_i$ のうち最も大きいものについて再帰的に同じことを繰り返せば答えが求まります。
どの要望が達成できているか否かを保持しておくと、計算量はソートに $O(M \log M)$ 、大きい方から順に橋を落とすのに $O(M)$ で求められるので $O(M \log M)$ で導出できます。
ソートにバケットソートを用いれば $O(N + M)$ で解けますね。

結果

oooo 4完(1000点) 2:08-8:31-13:23-27:48 / 27:48
93位

感想

最初のジャッジが壊れていて提出が全てWAになったのは恐怖でしたが、サンプルすらWAなことを見てジャッジミスを確信し先へ進んだので軽微な被害で済んだのは良かったです。
アルゴリズム的な知識をあまり問わず数学的な問題セットなので、ちゃんと図などを書いて考察すると解きやすい問題でしたね。
今回の問題セットが理解できなかった人は、ちゃんと図を書いて考察してみましょう！