Overall Editorial by maspy

ヒント集

A - Colorful Intervals

Hint 1

$A_{L}, A_{L+1},\ldots, A_{R}$ が相異なることから，$R-L+1$ 種類以上の正整数が必要です．

Hint 2

$d = \max_j(R_j-L_j+1)$ として，$d$ 種類の正整数で条件を満たすようことが可能です．インデックス順に要素を見たときに，同じ正整数が $d$ 回に $1$ 回以下しか登場しないように正整数を並べましょう．

Hint 1

敗者が連続して並ぶ場所で区切って考えてみましょう．

Hint 2

A が勝者となるパターン，B が勝者となるパターン，C が勝者となるパターンそれぞれが一度以上現れるかどうかで場合分けをします．

Hint 3

答が合わないときは，ランダムテストを書いて，どのようなケースで間違えているかを確認すると良いでしょう．

Hint 1

Bob は Alice の操作を戻すように動けるため，Alice が勝つためには Bob の移動先が常に白マスとなるようにしなければいけません．

Hint 2

Bob が上方向に移動し続ける場合，下方向に移動し続ける場合の戦略について考えることで，Alice が勝つための必要条件が得られます．

Hint 1

$X_i$ を定めた時点で，$10^9$ の位より下位の桁は $2^9$ 通り以下です．また上位の桁は，この時点でおおよそ確定しています．つまり，基本的には $10$ 進法表記がそのままの形でシフトしていきます．

Hint 2

ただし上位の桁は，今後繰り上がりの影響で $+1$ まで増加する可能性があります．「上位桁の桁和最小値」に加えて「上位桁に $+1$ した値の桁和の最小値」を求める形で dp をしましょう．

Hint 1

$A$ に現れる整数の種類が少ないときの解法について考えてください．

Hint 2

同じ整数が $A$ に現れる回数が少ないとき（例えばすべての $A_i$ が相異なるとき）の解法について考えてください．

Hint 1

この問題の難しさは，$x,y,z$ の大小によって $4$ 種の変換のどれが適用されるかが変わることです．しかし実は $4$ 種の変換すべての共通点があり，その共通点を見出すことが解法につながります．

Hint 2

共通点のひとつは，$4$ 種の変換いずれもが $x+y+z$ を変えないことです．これに加えてもうひとつの共通点を見つけることが重要です．

Hint 3

$S=x+y+z$ として，変換後の値を $\pmod{S}$ で観察します．

posted:
last update: