20190720_ABC134/

README

ABC134 感想

Dまで40分ほどだったが、計算量的に確信が持て無かったため、Eができたら提出しようと思ったが、 結局EもできずにNoSubしてしまった。

翌日Dまで一気にそのまま提出してみたらストレートに通ってたとはいえ、 時間的には自分の速度だとパフォーマンスが1200弱というところだったので、 レートだけ見るとその判断もやむなし、というところだった。

• A問題は真のやるだけ。
• B問題は制約もなんか不思議な感じでちょっと考えるが、普通に整数の除算で切り上げを考えれば良い。
• C問題は見た瞬間にいつぞやの累積GCD的なやつに似たやつだ！と思ってその方法をとった。
  • 冷静に考えると、殆どの場合は最大値で、最大値を取り除くケースだけ2番手、というのでよかった。
    • 解答PDFでの模範解答の1つ。
    • めんどくさいことを考えなくても降順ソートしてしまうだけで良い。
• D問題は後ろから決める方針で必ず決まったボールの入れ方がある。
  • 注目する箱にボールを入れるか入れないかだけで自由に決められる感じになる。
  • 1/1+1/2+1/3+...+1/n の計算量部分に不安を感じて提出できなかった。
  • 数3でこれの極限が logN になることは知っていたが、本番中は n=100000 程度で極限とみなしてよいのか自身が持てなかった。
  • 実際はエラトステネスの篩のアルゴリズムがこれと似たようなことをやっており、計算量も O(nlogn) と解析されているため、事前にこれに取り組んでおくことがとても重要だった。。
  • やはり蟻本は進める必要がある。。
• E問題は天才解法と愚直な貪欲手法のシミュレーションによる解法の2つがあるっぽい。
  • 愚直な手法の解説はKazune Takahashiさんのブログ解説がとてもわかり易かった。
    • なぜか本番中は気づけなかったが、挿入・塗替えはソート順序を保ったまま行うことはたやすく、可変長配列＋二分探索で十分だった。
    • これは解けないとだめな問題だった。大反省。
    • やろうとしている操作を具体的に紙に書き出してみたら気づけたかもしれない。
    • C++のmultisetを使う必要があるとかの声も聞こえてきたが、その方法はよくわからない。
      • 今回もC++への移行は見送り。。
  • 天才解法についても後日ゆっくりまとめたい。
  • 尺さんがいろいろと関連問題を投げてくれていたので。
    • 700点
    • 太古のARC