AtCoder Regular Contest 092

Updated:

AtCoder Regular Contest 092

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)$ だが Wset に変更すれば $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 つになるまで繰り返す。

  1. まず 3 つ以上印がついていないのが連続しているやつは、真ん中を選び、 2 要素削除する。
  2. 先頭に印がついていない場合は、先頭を選び、先頭を削除する。
  3. 末尾に印がついていない場合は、末尾を選び、末尾を削除する。
  4. この時点で 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