cplusplusonly's memo

Atcoder: https://atcoder.jp/users/cplusplusonly

AtCoder ABC128 参戦記

AtCoder の ABC 128

atcoder.jp

結果 5 完 50 分 でまずまずスピード出せたかな?と思って終了時に順位表見たら驚きの 106 位。
5 完までに難しいところがなかったので早解き合戦で 500 位ぐらいだと思ってたのでびっくりしました。
パフォーマンスが判明したところ驚愕の 2332...。レーティングも一気に引きあがりました。

f:id:y_r:20190526232831p:plain

感想

A 問題

瞬殺

B 問題

これは B 問題にしては難しい。結局 string -> vector (要素 : struct {int index; int p; }) みたいな map を作って、

  • map を昇順にまわす
    • 内部の vector は p で降順ソート
    • ソート済みの index を出力

とした。

C 問題

電球に応じてスイッチをグループ化して...と考えるとめんどくさいが n, m はせいぜい 10。bit 全探索にかければ終了。
このコードを最初からバグなし (初回ビルドがテストケースを全部通る) で書けたのでうれしかった。

D 問題

宝石を戻す手順は最後に固めてよいので、

  • 宝石を取る手数を選ぶ。ここで宝石を戻せる最大個数が決まる
    • 宝石を左右からとってくる
      • マイナスの宝石をマイナスが大きいものから捨てておく
      • 残った宝石の価値の最大値が答え
E 問題

実は出発時にはどこで工事にぶつかるかわかる。したがって

  • 工事開始時刻 (を出発地点の時刻に直したもの)
  • 工事終了時刻 (を出発地点の時刻に直したもの)

を用意してやれば、Di が出発しようとしたときの工事状況がわかるので、工事地点の X が一番小さいものが答えになる。工事してなければ無限に歩けて -1。

D が単調増加しているので助かった。単調増加してない場合はソートして答えの時に戻す手順が必要。

F 問題

 (A - B) = X とおくと、ゴール時の制約により、 X によって  B mod X] は一意に決まる。すると、 X のとりうる値の範囲  [1, 2/n) に対して、

  •  X * k の累積和
  •  X * k+ B の累積和


の 2 個の累積和ができ、前者は前から n 個取ったときの和、後者は後ろから n 個取った時の和を足した値で最大になる値が答え。
ただし、B mod X が 0 のときは n に制限がかかる (池ポチャになる n はとれない) のでその場合を除外する。

ぐらいまで考察して 1:40:30 *1 ぐらいに提出したところ WA。あと少し足りなかったらしい。

*1:当然時間オーバー