AtCoder Regular Contest 139

　A、Cの二完。

コンテストへのリンク

コンテスト後のツイート

B 拡張ユークリッドの互除法を使うんじゃないの？　色々式を書いて頑張ったけど分からなかった。
C 右上と左下の要素を重ねながら、3*3の正方形を連ねていく。Bが無理だと思って焦ってたとき、Cのグラフを描いたらこれが見えて、助かった。

— titia (@titia_til) April 24, 2022

B - Make N

　解説AC。

　計算量解析は難しいけれど、

・Y=min(Y, X*A), Z=min(Z, X*B)

　として、+Aや+Bをやる回数を探索するという方針は思いつけても良かった。これを10^5回程度（ちゃんと計算量解析すれば√Nで抑えられる）やればACできる。

　証明はできなくても、これくらい思いつけたんじゃないかと思う。反省。

D - Priority Queue 2

　解説放送を見てAC。

・最後にx以上の数が何個残っているか？

　を考えるのは典型処理。思いつくべきだった。

　その後の処理も典型といって良い気がする。DPの高速化と考えると多少発想が必要だけど、こういった問題では二項係数を使いそうなので、「x以上の数が何回出たか？」に着目するのは自然。

　ABCのG問題として出てもそれほど不思議はない（EXとして出たら簡単め）問題だと思う。コンテスト中解けなかったのは時間がなかったから仕方ないけれど、時間があれば解けるようにはしておきたい。