ABC 403 F — Shortest One Formula

考察

文法上、加算を含む式はそのまま乗算の因子にできない。最短の任意の <expr> と最短の乗算可能な <term> を別状態にする必要がある。値 i は、十進表記がすべて 1 のリテラル、j+k=i の加算、j×k=i の乗算から構成でき、加算の部分値と 1 でない乗算因子はいずれも i より小さい。dpExpr は dpExpr[j]+'+'+dpExpr[k] で更新できる一方、積は dpTerm 同士に限る。dpTerm には積のほか '('+加算式+')' を候補として渡す。乗算で因子 1 を除けば依存先は真に小さくなり、i の昇順計算で循環しない。最短文字列の長さは O(log N) に抑えられるので文字列コピー込みでも制約内である。

採用する候補: 値 i ごとに最短文字列 dpExpr[i] と最短の <term> 文字列 dpTerm[i] を持つ構文対応 DP

repunit を初期値とし、全加算分割と約数対の乗算で更新する。加算を term にする場合だけ括弧 2 文字を加えるため、文法と長さを同時に保証できる。

棄却する候補: 長さ順に文字列を生成して構文解析し、値 N が現れるまで探索する

利用可能な文字からなる候補数は長さに対して指数的で、同じ値・同じ構文カテゴリの膨大な式を区別してしまう。

各 i を昇順に処理し、repunit に一致すれば両状態を初期化する。j=1..i-1 の加算分割から expr と括弧付き term を、j|i かつ j,i/j>1 の因数分解から term 同士の積を両状態へ緩和し、dpExpr[N] を出力する。

典型の発動条件

構文カテゴリ DP

発動条件: 同じ値でも、親演算子の中で括弧なしに使える式の種類が異なるとき。

<expr> と <term> の最短表現を分け、BNF の生成規則だけを遷移にする。

構成付き最短化 DP

発動条件: 最適値だけでなく、その最適値を達成する文字列を一つ出力するとき。

各緩和で長さを比較し、採用した式文字列または復元元を保存する。

整数分割と約数遷移

発動条件: 式の最上位演算が加算または乗算に分類できるとき。

和は全分割、積は約数対だけを列挙して値 i の候補を漏れなく調べる。

問題固有の要素

括弧は単なる見栄えではなく <expr> を <term> に昇格させるコスト 2 と捉えると、演算子優先順位を二状態の最短路として扱える。

別の問題へ持ち帰る視点: 式最短化では「値」に加えて親構文から要求される非終端記号を状態にすると、不正な式を後処理で除く必要がない。

正当性

任意の式の最外演算は加算、乗算、括弧付き式、または1のみの literal である。加算を含む式を乗算因子にするには括弧が必要なので expr と term を分ける。加算両項の値と1でない乗算因子は対象値より小さく、昇順 DP がそれらの最短表現を取得する。因子1を掛ける表現は短くならないため除外できる。全構文分類を遷移で覆い、長さ加算には演算子・括弧を含めるので文法に従う最短式を得る。

実装上の注意

  • 未到達を十分大きい長さで初期化し、積で 1 を因子にしない。括弧と演算子の 1 文字を長さ比較へ必ず含め、同長候補はどれを選んでもよい。

復習の核

  • N=1、repunit、素数、平方数について、出力を構文解析して値と長さを確認し、小さい N では長さ別全探索の最短値と照合する。

計算量と制約

時間

上限値 N。加算分割 O(N²)、約数分割を各 i で平方根まで調べ O(N√N)。式そのものを毎回コピーせず長さ・復元元を保存すれば全体 O(N²+L)、L は出力式長。

空間

二文法状態と復元元で O(N)、最終式 O(L)。候補文字列を全状態へ直接保存する実装はその総長ぶん増える。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \le N \le 2000; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Shortest One Formula の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: DPの最小十分状態

    補助タグ: 構成解・witness復元 素因数・約数分解

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 最小十分状態からDPを設計する

    • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

    先に読む単元:

    この解説で扱わないこと:

    • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題