20190427_ABC125

README

ABC125 感想

62分0ペナで全問完答。パフォーマンスは1500ちょい。 DよりもCのほうが難しく（Dもめちゃくちゃ簡単だったとは思わないが）、D2000人、Cは1000人くらいの回答者数だった。

• A問題はちゃんと整数で閉じた演算にすること。
• B問題は制約が全探索を匂わせるが、実は貪欲法で良い。
  • なぜか 2^20 がTLEする数値に思えてしまい、当時は貪欲を考えるしかなかった。
• C問題は40分くらい悩んで、Dを10分くらいで解いたあと、戻ってきて ipad でお絵かきをしていたらひらめいた。
  • ありがとう、 ipad pro 12.9 インチ。
  • 左右からGCDをとったものを、各 idx に対してメモをとっておくことで、1つの値を書き換えたときのGCDの計算が O(1) で可能となる。
  • twitter で見かけたところによると、両端を書き換える場合は番兵を考えるより、素直に例外処理したほうがいいとのこと。よかった。
  • 典型: 前方からだけでなく、後方からも累積操作のメモを取る。
• D問題はフリップ系の問題の簡単な部類、といった感じ。フリップの操作がシンプル。
  • 典型: 範囲を1個ずらして操作を繰り返したときの変化に着目する。
  • 結局、大部分の負数は正数に変えることができる、ということがわかる。
  • あとは、偶奇性で場合分けして値をはじき出す。
  • DPをやるのが確実。
  • 後日DPで解き直したが、-inf に相当する初期値の設定が悪く（無限に程遠く）、WAに苦しんだ。
    • オーバーフローに気をつけつつ、正当な値を検討しなければならない。
    • math.MaxInt64 が大体 9*(10^18)なので、単に 10^18 という数を用いるときは特に悩む必要はなさそう。