キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）E,F,G問題メモ

キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）

E - Sensor Optimization Dilemma 2

• ある製品の製造には $1,2,\dots,N$ の番号が付いた $N$ 個の工程が必要です。
• 各工程 $i$ について、それを処理する $2$ 種類の機械 $S_i,T_i$ が売られています。
  • 機械 $S_i$ : $1$ 台につき $1$ 日あたり製品 $A_i$ 個分の処理ができ、 $1$ 台 $P_i$ 円で導入できる
  • 機械 $T_i$ : $1$ 台につき $1$ 日あたり製品 $B_i$ 個分の処理ができ、 $1$ 台 $Q_i$ 円で導入できる
• それぞれの機械は $0$ 台以上何台でも導入できます。
• 製品の製造能力は、以下で定義されます。
  • 機械の導入の結果、工程 $i$ を $1$ 日あたり製品 $W_i$ 個分処理できるようになったとします。
  • このとき、製造能力を $W$ の最小値、すなわち $\displaystyle \min^{N}_{i=1} W_i$ と定義します。
• 全体の予算が $X$ 円のとき、達成可能な製造能力の最大値を求めてください。

• 入力は全て整数
• $1 \le N \le 100$
• $1 \le A_i,B_i \le 100$
• $1 \le P_i,Q_i,X \le 10^7$

大枠は二分探索っぽい。とすると、以下の問題が解ければよいことになる。

• $M$ 個の製造能力を確保するとき、コストを $X$ 以下にできますか？

愚直には、以下のようなデータを揃えることで、この問題に $O(N)$ で答えることができる。

• $C[i][w]:=$ 工程 $i$ で、$w$ 個分の処理能力を確保するのに必要な最低金額

$\displaystyle \sum_{i=1}^{N}C[i][M]$ が $X$ 以下なら可能、と判定できる。

$C$ は、各 $i$ につきナップサックDPのようなことをすれば、とりあえず作ることはできるが、、、
ただ、製造能力（$w$ の次元）は上限 $10^9$ になり得るので、前計算したり、メモリ上に持つことはできない。

機械が2種類しか無く、また処理能力 $A_i,B_i$ の上限が小さいことに着目する。
$A_i \times B_i$ 個を「1ユニット」として、1ユニット分の処理能力を確保する事を考えると、以下のコストがかかる。

• 機械 $S_i$ だけなら $B_i$ 台を導入することになり、コストは $B_iP_i$
• 機械 $T_i$ だけなら $A_i$ 台を導入することになり、コストは $A_iQ_i$

この2つは相互に置き換え可能なので、例えば $T_i$ の方がコスパが悪いのに $A_i$ 台以上導入しているケースがあったら、 全て $S_i$ が $B_i$ 台に置き換えれば確実に安くなる。

よって、以下の $A_i+B_i$ ケースを試せば十分となる。

• $S_i$ を $j$ 台（$0 \le j \lt B_i$）導入し、残りは全て $T_i$ を導入するコスト
• $T_i$ を $j$ 台（$0 \le j \lt A_i$）導入し、残りは全て $S_i$ を導入するコスト

$\mathrm{LCM}(A_i,B_i)$ を1ユニット $U_i$ とし、コスパのいい方の1ユニット分のコストを $E_i$ とする。

$C[i][w]$ を $0 \le w \lt 2U_i$ の範囲まで前計算する。

$M$ を $U_i$ で割った商と余りをそれぞれ $d_i,m_i$ とする。
$d_i \ge 1$ なら、$d_i-=1,m_i+=U_i$ とする。

$\displaystyle \sum_{i=1}^{N}E_id_i+C[i][m_i]$ が、$M$ 個分の処理能力を確保するのに必要な最低金額となる。

1ユニット単位で計算できない端数は、 $S_i$ が $U_i/A_i$ 個未満、$T_i$ が $U_i/B_i$ 個未満使われているケースなので、 $0 \le w \lt 2U_i$ の範囲で調べれば十分となる。

Python3

F - Shipping

• この問題において、暦は $1$ 日、 $2$ 日、 $3$ 日、 $\dots$ と続いています。
• 注文 $1,2,\dots,N$ があり、注文 $i$ は $T_i$ 日に発生することが分かっています。
• これらの注文に対し、以下のルールに従って出荷を行います。
  • 出荷は注文 $K$ 個分までまとめて行うことができる。
  • 注文 $i$ は、 $T_i$ 日以降にしか出荷できない。
  • 一度出荷すると、その出荷の $X$ 日後になるまで次の出荷が行えない。
    • すなわち、 $a$ 日に出荷を行った時、次の出荷ができるのは $a+X$ 日である。
• 注文から出荷までにかかった日数 $1$ 日につき、不満度が $1$ 蓄積します。
  • すなわち、注文 $i$ が $S_i$ 日に出荷されたとき、その注文によって蓄積する不満度は $(S_i - T_i)$ です。
• 出荷するタイミングを上手く定めた時、全ての注文において蓄積した不満度の総和として達成可能な最小値を求めてください。

• 入力は全て整数
• $1 \le K \le N \le 100$
• $1 \le X \le 10^9$
• $1 \le T_1 \le T_2 \le \dots \le T_N \le 10^{12}$

注文は順番通りに処理することとして良い。
もし $T_i \lt T_j$ なる2つの注文で $j$ の方を先に出荷するような解があったとして、$i$ を先に出荷することにして損しない。

$\mathrm{DP}[i]:=$ 注文 $i$ までを処理したときの最適な○○、という感じにしたいが、 最適にしたい要素が2つあり、「前回の出荷日」と「不満度合計」が絡んでくる。

「前回の出荷日」は早い方が次の出荷の自由度が増えて良い。「不満度」はもちろん小さい方が良い。

もしあり得る（前回出荷日, 不満度合計）$=(s,c)$ の可能性を全て残す （つまり、$\mathrm{DP}[i]$ の中身を $(s,c)$ のリストにする）と、 リスト内の要素数は最悪 $O(2^i)$ にもなってしまう。

だが、2つの候補 $(s_1,c_1),(s_2,c_2)$ があり、$s_1 \le s_2$ かつ $c_1 \le c_2$ なら、 $(s_2,c_2)$ は完全下位互換なので捨てて良い。
もし、非効率なのを捨ててリストの中身が少なくなるようであれば、 例えば平均 $\alpha$ 個程度に抑えられるなら、計算量は $O(N K \alpha)$ で済む。
$\alpha$ がだいたい $O(N^2)$ くらいまでなら、なんとかなりそう。

ところで出荷日 $s$ として取り得る値は、 いずれかの出荷日から $X$ の倍数経過した日（$T_i + kX$ と表せる日）のみである。
出荷できるのに無駄に1日休む必要は無い。

この時の $T_i$ は、「最後に即日出荷をキメた注文（$T_i$ 日に来た注文を $T_i$ 日に出荷）」といえる。

$\mathrm{DP}[i]$ を求めようとしている時、 注文 $i$ から見て最後に即日出荷をキメた注文を $j$ とすると、 次の注文 $j+1$ から $i$ までは 「$X$ 日経過ごとに溜まっている注文を最大限（$\min(溜まってる個数, K)$）ずつ処理する」 のが最適で、他の出荷方法は必ずこれより効率が悪くなる。
つまり、$\mathrm{DP}[i]$ のリストに含まれる $(s,c)$ のうち、 同じ $j$ を由来とする $s$ は多くとも1つまでであり、 他の（$j$ が同じ）$s$ はそれと比べ必ず非効率になる。

よって、$\mathrm{DP}[i]$ での有効な $(s,c)$ の個数は 「最後に即日出荷をキメた注文がどれか」の候補数で抑えられ、 $O(N)$ と見積もれる。

$\mathrm{DP}[i]$ から非効率なのを選別する過程で ソートに $O(NK \log{(NK)})$ かかるが、 全体 $O(N^2K \log{(NK)})$ で間に合う。

Python3

G - Only One Product Name

• キーエンスの商品名はすべて 英大文字 $2$ 文字 からなります。
• すでに $N$ 個の商品名を使用しており、$i$ 個目 $(1\leq i\leq N)$ の商品名は $S_i$ です。

• 一度使用した商品名は再び使うことができないので、過去に使用した商品名の一覧がすぐわかるように NG リストを作ることにしました。
• NGリストは次の条件をみたす必要があります。
  • $1$ つ以上の文字列からなり、各文字列は英大文字のみからなる。
  • すでに使用されている商品名それぞれについて、その商品名を（連続する）部分文字列として含む文字列が $1$ つ以上存在する。
  • リスト内のすべての文字列は、すでに使用されている商品名でない長さ $2$ の文字列を（連続する）部分文字列として含まない。

• NG リストの文字列の数としてあり得る最小の値を求めてください。

• $1\leq N\leq 26^2$
• $N$ は整数
• $S_i$ は英大文字のみからなる長さ $2$ の文字列
• $S_1,S_2,\ldots,S_N$ はすべて異なる。

例えば新しく “AB” という商品名を付けようと思ったとき、 「この $n$ 個の文字列を検索して、いずれかに“AB”が含まれてたら既に使われてるよ！ 含まれてなかったら使われてないよ！」 というNGリストを作る際に、可能な最小の $n$ を求める問題。

文字列を頂点、しりとりの関係性を辺としたグラフ $G$ を作る。

AB→BC→CD→DE    XX┐
 ↖↙   ↓        ↑│
  CA    DF        └┘

NGリストの文字列は、この $G$ 上のウォーク（同じ頂点を何回通ってもいい経路）と見なすことができる。

元の問題は、以下に言い換えられる。

• 全ての頂点が少なくともいずれか1つのウォークに含まれるようにするには、最低何個のウォークが必要か？

これは、以下の2ステップで解ける。それぞれの実装は検索で出てくるため略。

• 強連結成分分解をおこなう。
  • 1つの強連結成分を縮約して1頂点と見なしたグラフを $G'$ とする。$G'$ はDAGである。
• DAG上の最小パス被覆問題（パス間で頂点が被ってもいいver.）を解く。
  • 推移律を満たす（$a→b,b→c$ に辺があったら $a→c$ にも辺がある）ように $G'$ を加工する。
  • 二部グラフの最大マッチングを解く。

最小パス被覆はうっすら記憶にあったが、細かな使用条件を覚えてなかった。以下を確認する必要がある。

• DAG でないといけない
• 二部グラフの最大マッチングによる解法で求まるのは「点素な」パスの数である

「点素な」とは、パス間で頂点が被らないこと。

例えば以下で、1→2→3→4→5, 6→7→3→8→9 とすると
最小パス被覆は「2」で済むが、
二部グラフのマッチングによる解法では頂点3を重複して使えないため、
6→7,8→9 に分割され、最小パス被覆は「3」と求まる。

1→2→3→4→5
    ↗ ↘
6→7     8→9

点素でないものを求めたい場合は、推移律を満たすように加工するか、「最小流量制限付き最小費用流」で解く。

• 最小流量制限付き最小費用流でのDAGの最小パス被覆の解き方
  • $G'$ の各頂点 $v$ を $v_{in},v_{out}$ に倍加し、超頂点 $s,t$ を用意する。
  • $s→v_{in}$ に、コスト1の辺を張る。
  • $v_{in}→v_{out}$ に、最小流量1、コスト0の辺を張る。
  • $v_{out}→t$ にコスト0の辺を張る。
  • $G'$ の辺 $(u→v)$ に対し、$u_{out}→v_{in}$ にコスト0の辺を張る。

つまり、$s→v_{in}$ を通ることが新たなパスを開始することに相当し、その時のみコスト1かかる。
$v_{in}→v_{out}$ に、最小流量付きの辺があることで、全ての頂点を通ることを強制する。

Python3