atcoder.jp 解説にある方法で簡単に解くことができますが、勉強のためにスタックで解いてみます。 文字列の i 文字目を c としたとき、 ・c と スタックの最初の値 が異なるとき → スタックをpopする ・c と スタックの最初の値 が同じ or 空のとき → スタッ…

AtCoder Beginner Contest 120 に参加しました。 結果は ABC 3完、順位は 753 位でした。 A - Favorite Sound atcoder.jp B/A（切り捨て）回聞けます。ただし、 C 回以上聞く必要はありません。 よって、min(B/A, C) が答えになります。 B - K-th Common Div…

atcoder.jp 私にとってはかなり難しい問題でした。よって、何段階かに分けて理解します。 剰余の式を理解する まず、以下の式変形を見てください。 ・(a+b) % K = (a+c) % K ・b % K = c % K 以前も何かの問題で見た気がしますね。a=5, b=4, c=8, k=4 のとき…

atcoder.jp 数直線上に N 個の座標がある。最初、立っている座標は x=0 である。 N 個のうち K 個の座標を訪れるとき、移動距離の総和の最小値として考えられるのはいくつか、という問題です。 訪れる K 個の座標は、連続していたほうがよいです。わざわざ1…

atcoder.jp 区間が N 個与えられる。 最も多くの区間に被覆されている値の、その区間の数を求めよ、という問題です。 解説にあるように、imos法を使うみたいです。 imos法は累積和を応用したアルゴリズムで、実装はとても簡単です。 区間の最小値～最大値に…

atcoder.jp 累積和の問題です。 ある人 i をリーダーに選んだとき、向く方向を変える必要があるのは、 ・i より左側にいる W ・i より右側にいる E です。この2つの合計が最小になるようにリーダーを選びます。 長さ N+2 の配列 W と、同じく長さN+2 の配列 …