ヤマカサの競技プログラミング

問題方針

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

問題方針

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

\

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

問題方針制約から考える

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

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

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

コード#include <bits/stdc++.h>u ...

問題方針転倒数

転倒数を求めるアルゴリズムはマージソートを利用したものや BIT を使ったものがありますが、今回はデータ数が小さいので、\( O(N^2)\) の計算量が間に合います。\( A \) の転倒数を \( s_1 \) とし ...

問題方針両者が散歩の途中で出会う座標

両者が散歩をしているときに出会う座標を求めます。これは、既に立ち止まっている国民に出会う点ではないことに注意して考えます。どのようなときに、両者が散歩をしているときに出会うかといいうと、東側に進む国 ...

問題方針ビット全探索

派閥の組み合わせはビット列で表現できるので、ビット全探索を用いて最大の派閥に属する議員数を求めます。派閥が成り立つときその派閥のグラフは完全グラフになっている必要があります。完全グラフかどうかの確認は、人間関係を隣 ...

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

\( t \) に含まれる文字が \( s \) に存在しなければ、条件を満たす整数は存在しません。そうではないとき、\( t \) の \( i \) 文字目 \( t_i \) について、\( s̵ ...

問題方針幅優先探索

頂点 \( 1 \) から幅優先探索を行って全ての頂点のカウンターの値を計算します。そのために、頂点 \( i \) が最初のカウンターの値をあらかじめ計算します。最初のカウンターの値とは、ある頂点 \( u \) ...

問題方針食材の価値

\( 1 \) 回の合成で使用された食材の価値は半減します。食材 \( i \) が合成に使われた回数を \( a_i \) とし、最終的な価値を \( f \) とすると、

\

となります。 ...