sankantsuのブログ

技術メモ・競プロなど

ABC253 感想・反省

atcoder.jp

結果

atcoder.jp

ABCDE5完 (91:15+4WA) 5完で1147しかパフォ出ないのは正直しんどい (レート微減)

Eが比較的簡単だったために解答時間でかなり差がつく回だったか.

最近WAが多いのと,そもそも速解きがやや弱い気がするので改善する必要がある.

コード

github.com

各問題の振り返り

A

3つの数の中央値を考える問題

問題自体は簡単だが,なぜか中央値の定義をど忘れして少し引っかかった.

しばらく後からAC

開始からの経過時間 62:29 (D問題より後)

B

2点間の移動距離を求める問題

マンハッタン距離を出せばいいだけなので簡単. 入出力に少し手間取る (cin から char に入力したとき改行が吸収されて変になったりしないか少し心配になった.実際は改行は区切り文字として処理される) stringで入力したほうが迷いがなかったかも?

5分ぐらい消費?

開始からの経過時間 8:36

C

与えられた数を1つ増やす操作と指定された個数消去する操作を繰り返しながら,各時点での最大値と最小値を管理する問題

一見してmultisetらしく見えたので実装してみたがTLE. よく見てみると,指定された個数の消去に最悪 O(N) になっていることに気づく.

追記: 解説を読んで気づいたが,実際の問題は要素の消去自体ではなく count メソッドの計算量だったらしい.これを改善すると通った (c-2.cc)

実際は map で数の個数を管理したほうが書きやすい

multiset を少し調べながら書いたことで時間がかかったのと,TLE 出た後の対応などでやや手間取って21分+1ペナ消費

開始からの経過時間 29:15

D

特定の数の倍数を除いた和を求める問題

高校数学みたいな問題. 愚直に和を計算するのでは間に合わないので,和の公式を使う.

1 から N までの和を求めてから A,B それぞれの倍数の和を引くが,公倍数の和は2度引いてしまうので1回足す.

公倍数は  A,B の最小公倍数の倍数として考えなければいけないが,勘違いして単純に  A\times B を使ってしまい 1WA. 冷静に考えると一番もったいないミスだったかも.

10分消費

開始からの経過時間 39:59

E

となりあう値が K以上離れた数列の個数を求める問題

個数自体は数列の添字と最後の値をテーブルにした dp で求めればよいが,単純にやると更新に  O(M) かかるので更新を累積和を使って高速化する.

方針自体はすぐ思いついたのだが,提出してみると2ケースでWA 怪しそうなところを1つ直してみるも変わらずもう1回WA

原因は  K=0 のコーナーケースの見逃しだった. コンテスト終盤になってようやく気づいて修正.

コーナーケースに気づくのに時間かかりがちな気はするのでこのあたりの注意力やデバッグ力はもっと鍛えなければいけない気がする.

51分ぐらい消費 (途中でA問題の提出を挟む)

開始からの経過時間 91:15

F

行列のいくつかの行にまとめて値を足すクエリと1行の値を特定値にセットするクエリに対し,各要素の値を計算する問題

遅延セグメント木とか使うのかな?と思ったが,時間もなく全然まとまらず.