AtCoder Beginner Contest 189 反省 - 文学徒が競プロをするブログ

めちゃくちゃ不甲斐ない。Dが通せなかったのは本当にひどかった。早い段階で方針分かってたのに通せないの最悪すぎて言葉も出ません。

A問題 Slot

if文を書きます

B問題 Alcoholic

$\sum_{i=1}^{k} V_i \times P_i \times \frac {1}{100} > X$ となる最初の添え字を求める問題。こういうのが誤差で死亡しがちなのは経験上(去年のパナソニックコンなど)知っていて、適当に式変形をするといい。

$\sum_{i=1}^{k} V_i \times P_i > X \times 100$ となる最初の添え字を求めればいい。

C問題 Mandarin Orange

$N \leq {10}^{5}$ とかならDに置かれていても違和感ない問題。普通に初手困った。
良い解法がぱっと思い浮かばなかったから、セグ木貼って $O({N}^{2} \log N)$ ワンチャンお祈りしたけどダメだった。

よく見るとTLが1.5secだったし流石に反省して速い解法考えたけど $O({N}^{2})$ 許すなら許してほしいね。

結局Minimum Sumみたいに小さい順にソートしてsetでindexを管理するやり方で解いた。聞くところによると最大長方形なるアルゴリズムで解けるんですね。初めて知りました。

D問題 Logical Expression

今回の反省の本題。まあANDとORでどう考えても数えるやり方が変わってくるからDPするしかないんですね。
敗因は何故か80分もあってこの簡単そうな遷移を詰め切れなかったこと。85分後に通せました。

え、文字にすると意味の分からなさがすごいな。このDP、バグやらで時間かけるとしても10分くらいの見た目じゃないですか？

このDPの遷移を時間通りに詰め切れないのは明らかにおかしいので、原因と対策を考えていく。

今回の件は、「サンプル等からフィーリングで何となくDPの状態の持ち方や遷移を考えていく」という論理的思考弱者ならではの思考パターンが招いた失敗だった。
この問題はたまたまサンプルが少なく、またサイズが小さかったために考慮漏れが頻発してしまった。また手で大きめのサンプルを作ろうとして時間を食ってしまった。それらがこの失敗を生んだと結論するのが妥当である。

実験が大切な問題とか、サンプル見ないと意味が分からない類の問題では確かにサンプルからエスパーしていくこともあるけど、それ以外の問題でやるべきことではない。

DPに限らず、今日を境として脱却することを誓います。

さて、改めてどうすべきかと考えると、やはり数式ベースで場合分けを考えていくという方針が良いように思う。
自分は何となくで問題が解けるほど地頭が良くないので、出来るだけ扱いやすい統一的な構造で問題を捉えていく癖をつけていかないと本当に水色に戻れなくなる。

数学的な考え方だとmaspyさんのDPに関する考え方がシンプルでかっこいいので、参考にしたいなあ。

ひとまずありがちな状態の持ち方として $f(i)$ を $y_i$ がTrueとなるものの個数とおく。そして場合分けを考える。

明らかな場合分けとして $S_i$ がANDかORかを考えると

ANDの場合

ANDの時は $y_{i-1}$ の値がTrueでかつ $x_i$ もTrueの場合しか $y_i$ でTrueになることはないので

$f(i) = f(i-1)$

となる

ORの場合

ORの時は更に場合分けをする必要がある。 $x_i$ をTrueとした場合とFalseとした場合である。
ちなみに本番ではここで $y_{i-1}$ がTrueの場合とFalseの場合を考えてしまい、混乱して時間をロスした(その場合分けだと $y_i$ がTrueとなる数とFalseとなる数両方を持つ必要がある)。そもそも定義からしてそんな場合分け考えるなよ。

$x_i = True$ のとき