AtCoder, 文字列

問題方針同じ文字が連続する文字列のコスト

長さが \( n \) の単一の文字からなる文字列をどの隣り合う \( 2 \) 文字を相異なる文字列にするために必要なコストは、

\

となります。例えば、\( n = ...

yukicoder, 区間系

問題方針

\( x \) 座標の正の方向と負の方向に向かって声が届く範囲を更新していきます。一方向に対して更新していくのではなく、同時に両方向に更新していくことがポイントです。

正の方向と負の方向に対してそれぞれ添え字を更新 ...

AtCoder, bitDP, 動的計画法

問題方針考察

鍵 \( i \) は \( b_i\) 種類の宝箱を開けることができるので、鍵は鍵束であると見ることができます。全ての宝箱を開けられないときは、全ての鍵の集合に対して対応できない宝箱があるということなので、先にそれのチェ ...

AtCoder, 数学

問題方針

\( A \) と \( B \) の公約数を考えるので、\( A \) と \( B \) の最大公約数を考えます。最大公約数を素因数の数が求める答えとなります。

コード

 

AtCoder, 整列

問題方針

\( i \) 番目の生徒が教室に来た時の教室にいる生徒の人数が \( A_i \) なので、\( i \) 番目の生徒は \( A_i \) 番目に教室に来たことになります。よって、\( A_i \) について昇順に整列させ ...

AtCoder, データ構造, 整列, 貪欲法

問題方針チケットの使い方

チケットを一度に複数枚使うことと一枚ずつ使うことが同じであることを確認します。\( 2 \) の指数を用いて整数を表現することを考えます。例えば、\( 31 \) は、

\

と表現できま ...

AtCoder, データ構造

問題方針

\( i \) 番目の人の正解数を \( p_i \) とすると、その人のポイントは、\( K + p_i – Q \) と表すことができます。よって、正解数の頻度を計算します。

コード

&nb

AtCoder, 文字列

問題方針

幸福でない人に着目して考えます。幸福でない人の文字列は、”RL” または “LR” となっているので、同じ文字が連続する文字列は幸福である人を含んでいるので、\( S \) を圧 ...

AtCoder, 数学

問題方針

条件を具体的に書き出すと、

\

となり、\( A_1 \) と \( A_N \) は不等式の制約が一つであることが分かります。よって、\( A_1 = B_1 \), \( A_N = B_{N-1} ...

AtCoder, 数学

問題方針制約から考える

\( N = 10^9 \) と制約がきついので、計算量は \( O(\sqrt{N})\) や \( O(1) \) などが考えられます。また、こういった問題は、\( N = 1 \) から実際にシミュレーショ ...