20190224_ABC119

README

ABC119感想

十分に全問完答可能なセットだったが、Dで二分探索の習熟度の甘さが露呈してしまい、のがしてしまった。

• A問題は文字列を分解して数字だけにしたが、辞書順判定でそのままif文に放り込んでよかった説がある。
  • Dの復習とともに試す。
• B問題は文字列→浮動小数点数の変換が必要で、忘れていたため慌ててググった。
  • 流石にこれぐらいは備えておきたい。
• C問題は30分ぐらい溶かしてしまったが、「使うか使わないか」という文章を紙に書いていたら全探索が浮かんでそのまま実装できた。
  • 最後のサンプルが優しくて、無から竹を伸ばす例外が検出されたので優しかったが、自力で気づきたいところがある。
• D問題は悔しい思いをしただけにとてもいい経験になった。
  • これをきっかけに 手持ちのライブラリ、Go公式ともに二分探索について十分に理解を深める事 。
  • 周辺を全探索する考えが曖昧だった部分もあるので、解説PDFも丁寧に読み込むこと！
    • 。。よくよく観ると8通り全てを数えようとはしていなかったので、どのみち正しく実装できていても1度はWAしていたと思われる。
      • アルゴリズムの基本は全探索

自作の LowerBound, UpperBound について

今回得た知見を言語化しておく。 2分探索ライブラリに対する誤解がだいぶ大きかったので、解消できたものは解消しておく！

1. 探索する配列中に、同じ値の要素が複数ないのであれば、lowerboundもupperboundも同じ。
2. 探索キーと同じ値がない場合は、探索キー値を挿入する位置が手に入る

• この記事の図をみるとそのことが理解できるはず。
• なので最小値は0で最大は len(A) となる。

1. 得られたインデックスを使ってもとの配列にアクセスしたい場合は、今回のように -inf と inf を先頭・末尾に挿入したものを使うときれいになることがあるらしい。

• 番兵というやつらしい。

1. 解析学の下界・上界は一旦忘れて、 lowerboundはギリギリ左の挿入位置を、upperboundはギリギリ右の挿入位置 を返すものと覚えておく。

• なので上述の2は当然。
• upperbound引くlowerboundで一致する個数、というのは知識としてしまってもいいかも
  • あるいは、探索キーに一致する要素がない場合はちゃんと0が計算されることなどもヒントになるかも

クエリ系⇔前処理？

各クエリに回答する前に前処理して情報を持っておくと楽になる場合、というのはたしかにありそうな気がしたので、記憶の片隅に置いておく。