AtCoder Beginner Contest 103

Updated:

AtCoder Beginner Contest 103

正しく題意を把握できず 1WA も出してしまった。

Source codes

Solutions

A - Task Scheduling Problem

sort した後 $\lvert A_0 - A_1 \rvert + \lvert A_2 - A_1 \rvert$ を出力。

ポイント

ジャッジに誤りがあったらしい。私の答案もリジャッジがかかっていた。

B - String Rotation

これは指示通りやるだけである。全探索。

ポイント

文字列の回転を正しく理解していなかった。 1WA した。

C - Modulo Summation

答えは $\sum (a_i - 1)$ である。実現するとすればこれが最大値であるが、 $m = a_1 \cdot \dots \cdot a_N - 1$ がこの最大値を実現する。

D - Islands War

$(a, b)$ を $b$ の昇順にソートしておく。今まで切られた橋のうち一番大きい番号 $x$ を持っておく。もし $a \leq x$ ならばすでに切断されている。 $x < b$ は勝手に保障される。そうでないならばどこかを切断する必要があるが、 $x = b - 1$ を切断するのが最善である。何故ならばそれまで検討した組については切断が完了しており、それ以降検討する組については $b$ が大きくなっていく一方だから、今は最も大きいところで切断しておいたほうが得であるからである。以上でシミュレーションをする。

ポイント

数え上げテクニック集 by DEGwer 氏の 3.3 節には 区間は終点でソート と書かれている。これを知っていると一撃である。

区間がいくつか与えられ、そのうちのいくつかを選んで特定の被覆条件を満たすようにする方法は何通りか、という問題はしばしば出題されます。このような問題では、与えられた区間たちを終点座標の昇順に見ていくのが非常に強力です。これには、区間スケジューリング問題が貪欲法で解けることと同様の性質を使っています。

類題は以下がある。

Others

A - sample: 3, tle: 2.000, time: 04:54, from_submit: 05:55
B - sample: 3, tle: 2.000, time: 08:00, from_submit: 00:00
C - sample: 3, tle: 2.000, time: 01:14, from_submit: 14:57
D - sample: 3, tle: 2.000, time: 05:58, from_submit: 08:59

最初から正しく全部実装できていれば 10 位だったかもしれない。