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 \) から実際にシミュレーショ ...

AtCoder, 実装

問題方針シミュレーション

数列 \( H \) の先頭から実際にシミュレーションをしていきます。現在の最大の移動回数と現在の移動回数を保持しながら探索をします。

コード