AtCoder,二分探索,探索

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

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

AtCoder,幅優先探索,探索

問題方針幅優先探索

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

AtCoder,数学

問題方針食材の価値

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

\

となります。 ...

AtCoder,動的計画法

問題方針

下記の方針は間違いを含んでいるので追記を見てください。

文字列 \( S \) の部分文字列に、それぞれの隣接する部分文字列が異なるように分割したときの最大値を求めます。このとき、部分文字列は最長でも \( 2 \ ...

AtCoder,データ構造,整列

問題方針

「明日できることは今日するな」ということで、締め切りから考えていきます。残り \( i \) 日あるとき、まだ請け負っていないアルバイトに対して \( A_j \leq i \) を満たすものの中で報酬が一番大きいものを選びま ...

AtCoder,数え上げ

問題方針

各文字列を構成する文字の種類と数が同じであれば、同じ文字列を構成できるので、文字列の文字を整列させマップなどでカウントすれば良いです。構成要素が同じ文字列の個数を \( v \) とすると、アナグラムの個数は、

\ ...

AtCoder,整列

問題方針

元の配列と昇順に整列させた配列を比べて、異なる箇所が \( 2 \) 箇所以下であれば、昇順にすることができます。

コード#include <bits/stdc++.h>using namespace std ...

AtCoder,データ構造

問題方針子どもの移動の挙動

どのような文字列でも十分に移動を行うと、’RL’ または ‘LR’ という二つのマスを行き来することになります。また、’RL’ という文 ...

AtCoder,実装

問題方針

あるマス \( i \) について、\( H_{i – 1} > H_{i} \) ならば、単調非減少とはなりません。\( H_{i-1} = H_{i} \) ならば、何もせず、\( H_{i – ...

AtCoder,動的計画法

問題方針動的計画法

\( d(i, j) \) を \( i \) 桁目までの調べた時、余りが \( j \) となるものの個数とします。初期値として、\( d(0, 0) = 1 \) とします。

\( S_i = ?\) のと ...