AtCoder Regular Contest 092
Updated:
rng さんの解説放送はあとで見ます。今日は寝ます。
Source codes
Solutions
C - 2D Plane 2N Points
貪欲法。赤点と青点をまず同時に vector<tuple<int, int, int>> V に入れていく。 $x$ 座標の小さい方から順に見ていく。赤点なら vector<int> W に $y$ 座標を格納する。青点なら W から、青点の $y$ 座標よりも小さいもののうち最大のものをとって消し、カウンターを足す。これで答えが出る。
計算量は $O(N^2)$ だが W を set に変更すれば $O(N \log N)$ でもできる。また最初から座標圧縮がかかっているので $O(N)$ ももしかしたらあるかも？
ポイント
priority_queue かと思ったけどそうではなかった。
某ゲームの謎のヒロインで頭がいっぱいで、赤と青は決して仲良くなれないと思った(どうでもいい)。
D - Two Sequences
30 分くらい考えて、「繰り上がり」をどう処理するかが全く分からず。
ポイント
E - Both Sides Merger
まず、「要素を，選んだ要素の両隣の要素の和に書き換える。そしてその後，両隣の要素を削除する」という操作を「ある要素を『削除』する。その後両隣の要素で『置き換える』」と表現する。すなわち、以下の言葉遣いで、「削除」するのは真ん中の要素であるということを強調しておきたい。面倒なので $0$-indexed とする。
答えは必ず、ある $I \subset N = \{ 0, 1, \dots, N-1 \}$ を用いて $\sum_{i \in I} a_i$ と書けるはずである。ではどのような $I \subset N$ が操作の結果としてありえるのか考察する。次のことがわかる。
- 「ある $i$ が存在し $i, i+1 \in I$」はありえない。隣り合う $2$ つの要素は、どのように操作しようとも、必ず片方は消さざるを得ない。
- 「$i, i+2 \in I$ かつ $i+1 \not \in I$」はありえる。 $i+1$ を選ぶだけでいいからである。
- 「$i, i+3 \in I$」はありえない。最初の条件から $i+1, i+2 \not \in I$ であるが、真ん中の $2$ つを消去しつつ $a_i, a_{i+3}$ を実現することはできない。
- 「$i, i+2, i+4 \in I$ かつ $i+1, i+3 \not \in I$」はありえる。 2 番目の応用。
- 「$i, i+4 \in I$ かつ $i+1, i+2, i+3 \not \in I$」はありえる。最初に $i+2$ を選んで $a_i, a_{i+1}+a_{i+3}, a_{i+4}$ を作ってから真ん中を消去すれば良いからである。
ここまで考察すると、ありえる $I \subset N$ は以下の条件を充すもの全てであることがわかる。
- $I$ の元の偶奇が揃っている。
- $I \neq \emptyset$ 。
これにより、(基本的には) index の偶数奇数別に $a_i$ を見ていき、非負の元を貪欲に選んでいき、偶数奇数で大きい方を選ぶ。 $I \neq \emptyset$ の条件は大事である。 全て $i \in N$ に対し $a_i < 0$ のときは、最も $a_i$ が大きい $i$ を選んで $I = \{ i \}$ とするのが答え になる。ここは私は間違えてしまった。 allneg のケースで落ちているのがこれ。
最大値は貪欲法で求まった。足すべき $i$ に「印」もつけた。あとは vector<bool> を用いてシミュレーションをする。次のようにするのが一例。削除したら一番最初に戻り、要素が 1 つになるまで繰り返す。
- まず 3 つ以上印がついていないのが連続しているやつは、真ん中を選び、 2 要素削除する。
- 先頭に印がついていない場合は、先頭を選び、先頭を削除する。
- 末尾に印がついていない場合は、末尾を選び、末尾を削除する。
- この時点で
true, false, true, false, ....., trueのようになっているから $1$ 番目を選び、先頭 2 要素を削除する。
ポイント
1WA だったけれども、時間内にクリアできていたのでセーフだろう。
F - Two Faced Edges
ポイント
Others
C - sample: 5, tle: 2.000, time: 08:16, from_submit: 130:06
D - sample: 4, tle: 3.000, time: 00:00
E - sample: 4, tle: 2.000, time: 78:29, from_submit: 51:37
F - sample: 3, tle: 5.000, time: 51:37