taki["blog"] = 2020 (R2)

社会人5年目(東京2年目)の日常

2020/9/19 ABC179

f:id:takilog:20200922120325p:plain

今日もABCEの4完でした.

  • Aはそのままです.
  • Bはそのままです.
  • Cは少し時間がかかってしまいました.どれかを止めたら全探索の計算はできますが,rangeの範囲をうまく探れずnaiveでも計算が怪しかったです.最終的には普通に10万ぐらいまで探索して条件探索してときました.
  • Dをチラ見してからEにいきました.
  • Eは悩みました.Mが106オーダぐらいなので,ここは全探索できます.同じ余りが出てくると,そこの2乗してmodとる計算はループするので,同じヤツです.これは最近のABCでたまに出てくるダブリングもしくはρ法になります.ρ法を時間をかけて実装したら解けました.最初はρの回転残りの部分の計算が間違っていてWAでした.ρ法,こんなやつ.

f:id:takilog:20200922120623p:plain

mathtrain.jp

DもDPっぽくて,naive解は解けていたのですが,TLEが取れませんでした.残念ですが,レートが上がったので良いとしましょう.