SRM628 Div1 Medium "CircuitsConstruction"
問題
TopCoder Statistics - Problem Statement
訳
ヤヌシュは若い物理学者だ。彼は現在電気回路で実験をしている。
最も単純な回路は単一の導体によって構成されている。そのような回路は"X"という文字列で表される。
ヤヌシュは2つの方法を用いて、回路を2つ繋げ、より複雑な回路を1つ作ることにした。ここでいう2つの方法とは、標準的な2つの方法(直列 or 並列)ではない。そのため下記説明を注意して読んで欲しい。
もしヤヌシュがタイプAの接続を使えば、新しい回路の抵抗は元々の2つの回路の抵抗の合計値となる。
もしヤヌシュがタイプBの接続を使えば、新しい回路の抵抗は元々の2つの回路の抵抗の最大値となる。
元々の回路がC1, C2だとする。タイプAの接続を使用するときは、"A"+C1+C2と表記され、タイプBの接続を使用するときは、"B"+C1+C2と表記される。例えば、"AXX"は2つの導体をタイプAの接続を使用して繋げることを意味する。
あなたには回路を表す、String circuitが与えられる。また、circuitに含まれる'X'の文字の数と同じ要素数を持つint配列 conductorsが与えられる。conductorsの要素はあなたがcircuitによって表された回路を構築するときに使用する全ての導体の抵抗値を表している。それぞれの導体は1回しか使用することができない。それぞれの導体は'X'の位置に使うことができる。回路を構築したときの抵抗値の最大値を返せ。
制約
1 <= conductors.size <= 2000
1 <= conductors[i] <= 10^5
考えたこと
circuitの回路はリーフノードが'X'で、それ以外が'A'または'B'の、二分木みたくなる。'X'が最大でいくつ合計することができるかをルートノードからdfsで探る。あとはその数だけconductorsの大きいほうから順次使用していけばよい。
ソースコード
struct Node { char type; int cid1; int cid2; }; Node nodes[4040]; class CircuitsConstruction { public: int maximizeResistance(string circuit, vector <int> conductors) { int n = circuit.size(); // 二分木構築 stack<int> vals; stack<int> conds; for (int i = n - 1; i >= 0; i--) { char c = circuit[i]; Node node = { c, -1, -1 }; nodes[i] = node; if (c == 'X') { vals.push(i); } else { conds.push(i); while (vals.size() >= 2 && !conds.empty()) { int id = conds.top(); conds.pop(); nodes[id].cid1 = vals.top(); vals.pop(); nodes[id].cid2 = vals.top(); vals.pop(); vals.push(id); } } } // 'X'は最大でいくつ合計することができるか? int use = dfs(0); // conductorsの大きいほうから順次使用していく sort(conductors.begin(), conductors.end()); reverse(conductors.begin(), conductors.end()); int ans = 0; for (int i = 0; i < use; i++) { ans += conductors[i]; } return ans; } int dfs(int id) { if (nodes[id].type == 'X') { return 1; } if (nodes[id].type == 'A') { return dfs(nodes[id].cid1) + dfs(nodes[id].cid2); } if (nodes[id].type == 'B') { return max(dfs(nodes[id].cid1), dfs(nodes[id].cid2)); } return -100; } };