SRM628D1Med CircuitsConstruction
せいぜい300ptsですねこれは…
問題概要(原文)
以下の $3$ 種類の抵抗がある
- 'X' : $1$ つの抵抗を表す．
- 'Axy': 回路 $\text{A}$ を使って $2$ つの抵抗 $x,y$ を連結する．抵抗 $x,y$ の抵抗値を $f(x),f(y)$ として抵抗値は $f(x)+f(y)$ となる．
- 'Bxy': 回路 $\text{B}$ を使って $2$ つの抵抗 $x,y$ を連結する．抵抗 $x,y$ の抵抗値を $f(x),f(y)$ として抵抗値は $max(f(x),f(y))$ となる．
回路の組み方は決まって，あとはどこにどの抵抗を入れるかだけである．最適な入れ方を決めて，抵抗値を最大化せよ．
考察
この回路はポーランド記法のようになっており， $2$ 分木で書ける．
ここでどのような順序で入れるか，ではなくて，この抵抗の抵抗値は全ての抵抗値が $1$ であったとき，何になるか？という値を求める．
これはつまり，最終的に生き残る抵抗の数がいくつあるか？ということを求めている．
最終的な答えは降順に並べた数列の先頭から生き残った抵抗の数だけ取った数列の総和．
計算量は $O(N)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class CircuitsConstruction
{
public int maximizeResistance(string circuit, int[] conductors)
{
var ptr = 0;
var n = dfs(circuit, ref ptr);
return conductors.OrderByDescending(x => x).Take(n).Sum();
}
public int dfs(string s, ref int ptr)
{
switch (s[ptr++])
{
case 'A':
{
var u = dfs(s, ref ptr);
var v = dfs(s, ref ptr);
return u + v;
}
case 'B':
{
var u = dfs(s, ref ptr);
var v = dfs(s, ref ptr);
return Math.Max(u, v);
}
case 'X': return 1;
default: throw new Exception();
}
}
}
コメント
- これは簡単すぎてびっくりした
