AtCoder, 貪欲法

問題方針

実際にカードを書き換えていく方法は計算量が多くなるので、最終的なカードの値を考えていきます。

ある操作でカードを書き換えるのではなく、カードが増えたとして、上から \( N \) 枚選び、その和が答えになります。こ ...

AtCoder, いもす法, 累積和

問題方針\( 1 \) 枚のカードで全てのゲートを通過できるとは?

\( 1 \) 枚のカードで全てのゲートを通過できるとはどいうことかを考えます。ID が \( a \) のカードが全てのゲートを通過できるとき、全てのゲート \( i ...

AtCoder, 数学

問題方針問題の解釈問題文を理解すると、取り出した駒の順番は問題を解く上で関係ないことが分かります。まず初めに操作回数を表す関数を定義します。次にその関数の最小値を求めます。ある駒を別の位置に動かすための操作回数はマンハッタン距離であることが ...

Codeforces, 文字列

問題方針括弧列の対応

どのようなとき、括弧列の対応が取れるかを考えると、既に括弧の対応が取れている括弧列を連結させるとペアが一組できます。ここで、ある括弧列を S とします。括弧の対応が取れる括弧列は、S を先頭から調べていき、R ...

yukicoder, 実装

問題方針文字列の頻度

出現する文字列の頻度を考えます。国士無双が成立するには、同じ牌は最大でも \( 2 \) 個なので、頻度が \( 2 \) を超えると、Impossible となります。

また、文字列の頻度 \( 2 ...

AtCoder, 数え上げ

問題方針与えられたグラフにおいて、\( 2 \) 回の移動で距離が \( 2540 \) となるパスの合計を求めたいので、ある頂点に接続している辺の距離の本数を数えます。

例えば、\(G \) を頂点 \( i \) から延び ...

AtCoder, 動的計画法

問題方針どのような文字列を除くか

どのような部分文字列を取り除くかを考えます。

長さが \( 3 \) の文字列では、”AGC”, “ACG”, “GAC̶ ...

AtCoder, グラフ理論, ベルマン–フォード法

問題方針

グラフの問題では最短距離を答える問題が多いと思いますが、今回は違います。このような問題では、重みの符号を反転させ、最短経路問題に帰着させます。これは、\( y = f(x) \) の最大化問題を \( y = -f(x) \) ...

AtCoder, 数学

問題方針\( a_i \leq b_i\) のとき\( b_i – a_i \) 回 \( a_i \) と \( b_i \) に操作を施します。\( b_i < a_i\) のとき\( a_i – b_i ...

AtCoder, 数学

問題方針\( P \) は \( N \) 個の整数の積で表現したときに、その整数の最大公約数です。どのような整数の組み合わせと \(P\) が最大公約数を最大化することを考えると、\であることが分かります。このとき、\( a = a_i ...