貪欲法に関するカテゴリーです。

Codeforces,整列,貪欲法

問題方針

\( h \) を昇順に整列させて考えます.\( h_{i + 1} -h_{i} \) を最小化する最小の \( i \) を \( j \) とします.ここで,\( h_j \) を先頭にして,\( h_{j+1} \) ...

AtCoder,貪欲法

問題方針

価値が高い荷物からその大きさに最も近い箱に入れます。

コード#include <bits/stdc++.h>using namespace std;typedef long long ll;struct Data ...

AtCoder,数学,整列,貪欲法

問題方針

まず初めに演説を行わなかったときを考えます。青木君得票数は \( A_i \) の総和なので、その得票数を \( s_0 \) とすると、

\

となります。また、高橋君の得票数を \( t_0 \) と ...

AtCoder,文字列,貪欲法

問題方針

\( T_i \) の先頭から貪欲に辞書順の最小の文字から構成できるかを調べます。これは文字の頻度を管理することで、高速に計算することができます。文字列 \( S \) の \( i \) 文字目から \( j \) 文字目ま ...

AtCoder,二分探索,整列,累積和,貪欲法

問題方針

\( H, W \) を昇順に並び替えても一般性は失われないので、昇順に並び替えます。例えば、\( 2n \) 人の児童の最適なペアは

\

であると考えられます。これを問題に当てはめて考えると、\( N ...

AtCoder,文字列,貪欲法

問題方針

\( S \) が ‘a’ だけの文字からなるとき、’atcoder’ \( < S\) とあることはありません。また、’atcoder’ R ...

AtCoder,実装,貪欲法

問題方針

カコモンジムに通うことを操作1、AtCoder ジムに通うことを操作2とします。

\( i \) 回目の操作を行ったときの高橋君の強さを \( X_i \) とします。操作1を行うと、\( X_{i + 1} = ...

AtCoder,貪欲法

問題方針

山 \( i \) に積まれている一番上の重さを \( v_i \) とします。初期値は、\( v_1 = w_1 \) です。段ボール \( j \) が全ての山に対して \( v_i < w_j \) を満たすとき、 ...

Codeforces,尺取り法,貪欲法

問題方針

あまり理解していませんが、操作 1. で選ぶ文字は、同じ文字が連続する部分文字列のなかで一番左のものを選ぶみたいです。

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

AtCoder,貪欲法

問題方針

まず初めに仮の最小値 \( d \) を \( d = 0 \) とします。\( i \) 番目の最小値は、\( d \) が \( p_1, \cdots, p_i \) のいずれとも一致しなければ良いので、一致しなくなるま ...