ABC 170 D - Not Divisible - sky’s 雑記

エッジケースを通すコードを書く技術がまだまだ足りない．ネストが深くなったり変数定義が増えるときは大体考察が足りていなくて，そういうときはアクセプトしない．

ネストを浅くしたり変数定義を減らせばアクセプトするのは事実だと思うが，それができるのは考察が正しいからという前提があるのを忘れてはいけないと思う．

回答時の方針

本番ではエラトステネスの篩は頭に浮かんだがエラトステネスの篩の高速化について理解していなかったのでTLEしてしまった．コンテスト終了後は高速化した上で提出を繰り返したが全てのテストケースを通すのにかなり苦労した．

結果だけ見るとそんな難しいことはしていないがいくつか詰まった点をまとめる．

入力例1で考える．ナイーブに考えると各 Ai について Aj を試すことになるので計算量は O(n^2) になる．

5
24 11 8 3 16

要素Aiで割り切れる要素を取り除きたいとき別途リストDPを利用すると高速化できる．リストAを昇順ソートした上で要素Aiの倍数要素についてDP[Aj]=trueとすれば改めて要素Ajを試行するまでもなく倍数判定が可能となる．

for(ll j = 2*ar[i]; j <= max; j+=ar[i]) {
  s[j] = true;
}

これは書いてあるとおりで例えば入力例1の場合要素の最大値は24なのでDP.size=24あれば十分なのだが，このあたりを厳密にやるよりは与えられた制約の最大値で初期化したほうが問題が起きないことが多いように思う．DP(200000, false)