AtCoder Beginner Contest 250 参加記
三連続で冷えてるのでいい加減温まりたいな～って思ってたら少し温まりました
本番では4完1491位、パフォーマンス1220でした
C - Adjacent Swaps
右端のボールは左端と交換してよ
N,Qどちらも2×10⁵以下なので愚直にシミュレーションで良さそう、ちょっと実装が面倒
本番では「整数iのボールがある場所」と「左からi番目にあるボールの整数」の2つの配列を持ってこねくり回した。
本番ACコード
D - 250-like Number
p×q³≤10¹⁸であることを考えるとp,qとして考えられる素数は10⁶までを考えておけば十分っぽい感じがするので、まずは10⁶までの素数を列挙しておく
こういう「数式と制約から新たな制約範囲を考える」手法、ABC246 - Dで学んだのが役に立ってる（よく見たらどっちの問題も物理好きさんWriterじゃん）
コンテスト直後のTLではpを決め打ちしてqを二分探索する解法しか流れてこなかったけど（そんな解法思いついてないけど？）、素数定理より10⁶以下の素数の個数は17万未満（実際は78000程度）なので全探索で間に合うんですよね
本番ACコード
余談：最初100万までの素数を埋め込もうとしたらAtCoderに怒られました（それはそう）
E - Prefix Equality (本番未AC)
実行時間制限が4秒だということにコンテストが終わってから気付きました
2WAで分からん～ってなってたけど方針は合ってたみたいで、setを3つくらい使って集合を比較する方法でやってた、んですがクエリを何故かソートして先頭から処理すればええやん！という思考に至りWAと。（xで昇順ソートしましたが、x_i < x_(i+1)のときにy_i > y_(i+1)だと破滅します）
総評
E、勿体ね～のお気持ち（Dまで50分なので十分時間はあった上に基本的方針は合っていたので）あとはDも実装に時間かかりすぎ（34分）ですね（最初OEISでググったらなんかヒットしたのでそれに食いついたのが明らかにロス）
まあ温まったので良いです、また頑張ります
