AtCoder ABC 140 参戦記
AtCoder の ABC 140
に参加しました。
結果は 91 分で ABCDEF の全完 (2 WA)。はじめて F 問題が解けて早解き以外でもパフォーマンスを出すことに成功しました。
116 位パフォーマンス 2279 の黄パフォを出すことに成功し、レートも大きくあがっています。
気が付けば青色の半分より上に到達しました。
感想
A 問題
やるだけ。
B 問題
最初最適化するのかと思ってびっくりした。その分時間を少し消費した。
C 問題
やるだけだが、端に番兵を置くのは思いつかなかった...
D 問題
- 幸せ数は人数から "L" または "R" のかたまりの数を引いたもの。
- 1 回の操作でかたまりは 2 個減らせる
- "L" または "R" のかたまりひとつを逆にすればよい
- 最後のかたまりだけはつぶせない
と考察して AC。
考察難易度結構あったような。そのわりに 1600 人以上に通されていてびっくり。
E 問題
- 数が大きい順に処理して、大きい数リストに数のインデックスを記録しておく
- ある数に対して、その数が 2 番目に大きくなるのは以下の 2 通りなのでそれを数え上げる
- (i が大きくなる方向に対して、大きい数リストの 1 番目および 2 番目の間) x (i が小さくなる方向に対して大きい数リストの最初の i)
- (i が小さくなる方向に対して、大きい数リストの 1 番目および 2 番目の間) x (i が大きくなる方向に対して大きい数リストの最初の i)
を実装して AC。境界の処理とかがめんどくさかったが実は左右に番兵を置いておけばよかった模様。
F 問題
貪欲にいけばよいのはすぐに気が付いた。
最初、
- 数の大きな順にソート
- 同じ数の個数を数えて今の数より大きなスライムの分裂回数以下ならその数は処理できる
みたいな実装をなげて 2 ケースのみ WA、Yes/No のどちらが WA なのかを調べるために全 Yes を投げて 2 WA 目を出した。
ダメなケースを考えているうちに、全体が木になっていて子は親の数未満という制限があることに気が付き、以下の実装を投げつけて AC した。
- 数の大きな順にソート
- 座標圧縮しつつ同じ数の個数をカウント
- 数ごとに今までのスライムの個数を保存する領域を作成
- 各日ごとに
- 保存領域の各スライムに対してその数未満のスライムを割り当てる
- 割り当ては数の大きいものから
- 本日のスライム数を保存領域に足す
- スライムが割り当てられなかったら NG
- 保存領域の各スライムに対してその数未満のスライムを割り当てる
