Overall Editorial by maspy

ヒント集

A - Always Increasing

Hint 1

まずは $i$ を固定して，「常に $A_i < A _ {i + 1}$ となるのはどのようなときか」を考えてみましょう．

Hint 2

条件はある $c_i$ について，「初期状態で $A_i+c_i < A_{i+1}$ が成り立つこと」と言い換えられます．このような $c_i$ が求まれば， $A_1=1, A_{i+1}=A_i+c_i+1$ が成り立つように初期状態を定めることで総和が最小化されます．

Hint 1

どのような要素が削除されずに残るかを考えてみましょう．例えば $A_1, A_2, \ldots, A_N, B_1, B_2, \ldots, B_M$ のうちで最小のものは削除されることはありません．

Hint 2

最後まで削除されずに残るのは，小さい方から $N/2$ 個と，大きい方から $N/2$ 個の要素です．あとは基礎的なデータ構造の問題です．

Hint 1

上位の桁から答を求めていくというのが全体的な方針となります．

Hint 2

答が $10X+Y$ （$0\leq Y\leq 9$）であるとして，$X$ を求めることを考えてみます．すると，コイン $0$ を可能な限りコイン $1$ に両替した上で，コイン $1,2,\ldots,N-1$ に関する問題を解けばよいことになります．

Hint 1

小さいグラフで Bob が勝てるパターンを探しましょう．$N$ が奇数の場合の方が簡単です．

Hint 2

$N$ が偶数のとき，頂点数 $3$ のパスを $2$ つ含むならば Bob が勝ちです．また頂点数 $4$ のサイクルを含むならば Bob が勝ちです．

Hint 3

頂点数 $3$ のパスを $1$ つ以下しか含まず，また頂点数 $4$ のサイクルも含まないのはどのようなグラフでしょうか？解説では，次数 $3$ 以上の頂点の個数で場合分けをして調べています．

Hint 1

$i=1,2,3,\ldots$ 順に，$(A_1,\ldots,A_i)$ の部分和のソート列を求めていくという単純な解法があります．ただしこれをそのまま行うと部分和の種類が多すぎます．

Hint 2

部分和のうち，すべての値を正確に保持する必要はありません．正確な値が不要な要素について値を適当に変更するなどして，保持すべき部分和の種類数を少なくしましょう．

Hint 1

$ax_i+by_i=A_i$, $az_j+bw_j=B_j$ となる $x_i,y_i,z_j,w_j$ をひとつとってから考えるとよいでしょう．

Hint 2

適当なスワップによって $bs\geq at$ を仮定します．このとき，$\pm a$ 操作は高々 $b$ 回しか行われないとしてよいです．

Hint 3

矩形領域内にある値の和を求めるというタイプのクエリに帰着することで計算を高速化します．

posted:
last update: