20200119_ABC152/

README

ABC152 感想

Dで思いっきりやらかしてしまって4完98分パフォは1000弱。

• Aは同値判定のif文。
• Bは文字列連結をしてからif文で辞書順判定。
• Cは先頭からのminを記憶しておけば良い。
  • セグ木使って解き直してみたい。
    • セグ木でも通った。
    • 初めて気づいたが、区間の長さ0で Query を呼ぶと、単位元が返ってくる。
      • 直観的ではないので、なるべく変な区間でのクエリメソッドは呼びたくないが。。
• Dは色々と悲しいことになった。
  • 素直に各 A に対して条件を満たす B の個数を数えようとしたが、実装が闇で良くなかった。
    • 正しくやれば通せるはずだが、最後まで気づけず。
  • 終了6分前に別の方法を考えついた。2次元配列で先頭と末尾の情報をメモしておけば良い。
  • 最初こどふぉっぽい重実装を要求する問題かと思ったが、結果を見ればAtCoderらしい単なる数え上げに過ぎなかった。
  • 一応、ゴリ押し解法の間違っているポイントは発見しておきたい。

D問題の反省

どうすればよかっただろうか？

想起したかったところ。注意したかったところ。

• A, B の集合をもう少し意識すべきだった気がする。
• そもそも踏み出した実装が闇すぎることはわかっていたので、踏み出す前にもう少し俯瞰して幅広く考えるべきだった。

E問題の復習（@2020-01-23）

かなり簡単だった。。

サンプルから解法を予測するのは簡単なため、あとはどのようにして計算量を落とすか？に集中しやすい。

基本的には素因数分解が鍵となる問題だと思っていて、 素数と指数のペアを使いやすい形で持っておくと対処しやすい。

自前の素因数分解が2以上の自然数しか受け付けない（panicする）ことはちゃんと覚えておいたほうがいい。