自分がよくやりがちなミスをまとめてみました。 このようにまとめておくことで、 よくやるミスをやらかさないよう注意深くなる 解法は合っているはずなのに何故かWAする、といった場合に疑うべき場所が明確になる という効果を期待しています。D言語特有の仕…

No.752 mod数列 - yukicoder 問題 数列 が与えられる。個のクエリに対して を求めよ。 制約 解法 まずおなじみの累積和テクニックの考え方からが成り立つので、任意のに対してを求めるにはどうすればよいか？を考えることにします。ここで程度までであれば単…

問題 を求めよ。https://beta.atcoder.jp/contests/abc103/tasks/abc103_c 解法 まず任意のについて、であることから、の上限はであることはすぐに分かります。そして、サンプルなどを見ているとmを上手くとればをこの上限に一致させることが出来るのではな…

久しぶりにブログを更新します。今回は解説記事ではなく自分語り系の記事です。twitterを見ていたら「pythonで競プロをやるってどうなの？」みたいな話が出ていたので、私も元python競プロerとして考えを述べてみたいと思います。（もともとこのブログのタイ…

問題概要 集合が与えられる。 各整数k = 1, 2, ..., Mについて、kと互いに素であるAの要素の個数を求めよ。 制約 解法 愚直にやると少なくともO(N*M)かかってしまうのでまとめて数え上げるなどの高速化が必要になります。kを固定したときに、kとa_iが互いに…

https://beta.atcoder.jp/contests/dwacon2018-final-open/tasks/dwacon2018_final_bニコ生の公式解説でちらっと触れていた解法が凄くスマートだったので復習を兼ねて書いておきます。 解法 与えられた[v_1, v_2, ..., v_n]を(K+1)倍に拡張した次のような配…

No.643 Two Operations No.2 - yukicoder 考察 xとyの比を取って、p = x/yと置くとx=yにするということはp=1にするということと同値であることが分かります。 （ただし、y=0のときはp=∞であると考えることにします。また(x, y) = (0, 0)は少し特殊なので無い…

No.642 Two Operations No.1 - yukicoder 考察 とりあえず整数を頂点、操作を辺としてグラフにしてみると以下のような感じになります。頂点数はNで辺の数は2Nなので、N 最短距離（最小操作回数）が求められますが、今回はN 頂点iへの最短距離をdist(i)と書く…

https://beta.atcoder.jp/contests/abc056/tasks/arc070_b 考察 要素の順番は関係無いので、考えやすくするためにとりあえずa_iは昇順ソートされているものだとします。まず、「カードiが必要であること」とはどういうことかと考えてみると、条件の否定を考…