sankantsuのブログ

技術メモ・競プロなど

ABC257 感想・反省

atcoder.jp

結果

atcoder.jp

ABCD4完(74:55 + 4ペナ)

  • Performance: 1175
  • Rate: 1293 -> 1280 (-13)

しょうもないWAが多く冴えない回だった

コード

github.com

各問題の振り返り

A

特定のパターンの文字列の X文字目を取り出す問題

文字列を実際につくらなくても,割り算して何種類目の文字か数えればいい.

いきなり1WA.原因は大文字を出力しなければいけないのに小文字にしてしまったこと

6:42 (+ 1WA)

B

コマの動きをシミュレーションして最終配置を求める問題

コマが追い越さないことを利用して問題を読み変えると少し楽になる.

ここで3WAも出してしまう.原因は, Qの値だけ制約が少し大きいのを見逃して,メモリの確保が足りていなかったこと. 原因に気づくのに時間がかかりかなりロスしてしまった.

22:24 (+ 3WA)

C

単純なしきい値を用いた判定器の正解率を最大化する問題

一番簡単なのはしきい値で全探索することだが,候補が[tex: 109]程度あるので無理. 実際にはしきい値は与えられた体重のどれか(または体重の最大値より大きい値)だけ考えれば十分なので,これで候補数を O(N)に減らせる. ただし,各しきい値に対して正解数の計算は安直にやると O(N)かかるのでまだ少し工夫がいる. 大人,子供それぞれの体重をソートしておいて,各しきい値の候補に対して正しく判定される大人と子供の人数をそれぞれソート済みの配列に対する2分探索で計算することによって O(N \log N)で解いた.

16:16

D

任意のジャンプ台の間を移動できるようにするための条件を求める問題

  • 訓練の回数を増やすと,飛び移れるジャンプ台の数が増えることはあっても減ることはない
  • 訓練回数を固定すれば,条件を満たすかどうかは比較的簡単に判断できる

という点を考慮すると,訓練の回数について2分探索するのが良さそうである. 実際条件を満たすかの判定については,ジャンプ台 iからジャンプ台 jに飛び移れるときに i\to jの辺を張ったようなグラフを考えて,すべての始点からDFSなりBFSなりして到達可能性を調べることでできる([tex: O(N3)]).

デバッグのためにいれた出力自体が間違っているというしょうもない理由で手間取り,ここでも時間ロスした.

30:33

E

与えられた予算で最大の数字をつくる問題

はじめ,残っている予算に対してその時点でつくれる数字の最大値をDPで求めていけばよさそうと考えた. 一見すると O(N)で良さそうなのだが,整数の桁あふれが問題になる. 多倍長整数を使えばできそうに見えるが,整数の桁が O(N)になるので,整数の計算やコピーに O(N)かかることになり実は全体で[tex: O(N2)]になってしまう.

解決策が思い浮かばず時間切れ.

終了後解説を見て通した. 桁数に注目するという考察ができていなかった. 以前もD - At Most 3 (Contestant ver.)で失敗したが,10進の桁に注目する考察が苦手なのかもしれない.