AtCoder ABC128 参戦記
AtCoder の ABC 128
結果 5 完 50 分 でまずまずスピード出せたかな?と思って終了時に順位表見たら驚きの 106 位。
5 完までに難しいところがなかったので早解き合戦で 500 位ぐらいだと思ってたのでびっくりしました。
パフォーマンスが判明したところ驚愕の 2332...。レーティングも一気に引きあがりました。
感想
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 問題
とおくと、ゴール時の制約により、 X によって ] は一意に決まる。すると、 のとりうる値の範囲 に対して、
- の累積和
- の累積和
の 2 個の累積和ができ、前者は前から n 個取ったときの和、後者は後ろから n 個取った時の和を足した値で最大になる値が答え。
ただし、B mod X が 0 のときは n に制限がかかる (池ポチャになる n はとれない) のでその場合を除外する。
ぐらいまで考察して 1:40:30 *1 ぐらいに提出したところ WA。あと少し足りなかったらしい。
*1:当然時間オーバー