ABC-only 回です。E完でした。
AtCoder Beginner Contest 138
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
A - Red or Not
問題概要: 整数 a と文字列 s が与えられる。a が 3200 以上なら s を出力し、そうでなければ "red" を出力せよ。
A: 考察
a が 3200 以上かどうかで分岐すればOK。
if a >= 3200 {
println!("{}", s);
} else {
println!("red");
}
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc138/submissions/6993708
B - Resistors in Parallel
問題概要: N 個の整数が与えられる。各整数の逆数の和の逆数を求めよ。
B: 考察
与えられた式を計算すればOK。
let mut x = 0.0;
for &a in &A {
x += 1.0 / a as f64;
}
x = 1.0 / x;
println!("{}", x)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc138/submissions/6993361
iter を使ってもいいです。
let x = 1.0 / A.into_iter().map(|a| 1.0 / a as f64).sum::<f64>();
println!("{}", x)
C - Alchemist
問題概要: N 個の具材がある。価値が x, y である2つの具材を合成すると、価値が (x+y)/2 である具材を1つ得る。合成操作を N-1 回行うとき、最後に1つ残る具材の価値の最大値を求めよ。
C: 考察
価値が x, y, z (ただし x, y ≤ z) である具材が3つあるとき、操作手順は z を先に合成するか後に合成するかの2択です。
- x, z を合成してから y を合成する (x と y を逆にしても同様)
- $\frac{\frac{x + z}{2} + y}{2}$
- x, y を合成してから z を合成する
- $\frac{\frac{x + y}{2} + z}{2}$
下から上を引くと、
$\frac{\frac{x + y}{2} + z}{2} - \frac{\frac{x + z}{2} + y}{2} = \frac{z - y}{4} \geq 0$
となり、下の方が良いことが分かります。すなわち、価値の高い具材は後に合成した方が良いです。
したがって、具材をソートして、価値の低い具材から順に合成していく貪欲法により計算できます。
A.sort();
let mut x = A[0] as f64;
for i in 1..N {
x = (x + A[i] as f64) / 2.0;
}
println!("{}", x)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc138/submissions/6992759
C: 正当化
具材の合成は木で表すことができます。
w w: x と y を合成して得た具材
/ \
x y x, y: 元になる具材
上述の比較から、以下の木の組み換えが考えられます。(x, y ≤ z)
* *
/ \ / \
x * --> * z
/ \ / \
y z x y
最適解を得られる木を1つとり、それに組み換えを再帰的に行うと以下の形にできます。(ただし A: 単調増加)
*
/ \
.. A(N)
/
*
/ \
* A(3)
/ \
A(1) A(2)
これは貪欲法による手続きでの合成の過程と同じです。組み換えにより価値は減らないので、これが最適解であるといえます。
D - Ki
問題概要: N 個の頂点を持つ木が与えられる。頂点 1 を根とする。各頂点は初期値 0 のカウンターを持つ。以下の Q 個の操作を行った後、各頂点のカウンターの値を求めよ。
操作 (j 番目): 頂点 p(j) を根とする部分木に含まれる各頂点のカウンターを x(j) 増やす
D: 考察
加算なので操作の順番は無視します。また、頂点 p(j) が等しい複数の操作は x(j) の値を合算して1つにまとめます。
つまり、頂点 v を根とする部分木の各頂点のカウンターをそれぞれ y(v) 増やす、という操作が一斉に行われると言い換えます。
各頂点 v から見て、どのくらい自身のカウンターが増やされるか考えます。頂点 v を含む部分木の根は v 自身のほかに、v の親と、v の親の親、……、すなわち v の祖先全体です。
したがって、操作後の v のカウンターの値は (各祖先 a の y(a) の総和 + y(v)) です。ただし祖先の総和は v の親のカウンターの値に一致します。そのため、v のカウンターの値は単に (親のカウンターの値 + y(v)) です。累積和ですね。
a
/ \
p ..
/ \
v ..
結局、BFS または DFS で根から順番にカウンターの値を計算していけばよいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc138/submissions/6995384
E - Strings of Impurity
問題概要: 英小文字からなる文字列 s, t が与えられる。s を ${10}^{100}$ 個連結した文字列を s' とおく。以下の条件を満たす i が存在するか判定し、存在するなら最小値を求めよ。
条件: s' の前方 i 文字が t を部分列として含む。
E: 考察
入力例1にある通り、s=contest, t=son では以下のように s' の前方10文字が t を部分列として含み、これが最小です。
0123456789
contestcontestcontest..
s on
最小値が存在しないことの条件は s に含まれない文字を t が含んでいるケースです。そうでなければ s を |t| 個連結した文字列が t を部分列として含むため。
文字列 s, t が十分に短ければ、以下のように t の各文字が出現するまで繰り返し s を走査する手続きで最小の i が求まることが直感的に分かります。
// O(|s| |t|)
fn solve_slow(s: &[char], t: &[char]) -> Option<usize> {
let mut i = 0;
for ti in 0..t.len() {
// t の ti 文字目を探索
while s[i % s.len()] != t[ti] {
i += 1;
if i >= s.len() * t.len() {
return None; // 最小値なし
}
}
i += 1;
}
Some(i)
}
s' から文字 t[ti] を探す部分が遅いので高速化しましょう。文字 t[ti] が26通りしかないことに注目します。各英文字 c が次に出現する位置を事前に計算しておけば探索をスキップできます。
例えば s=abaab のとき、文字 a, b が次に出現する位置の表は以下のようになります。
| 0 1 2 3 4
s | a b a a b
--+----------
a | 0 2 2 3 0
b | 1 1 4 4 4
この表は、各文字が最後に出現した位置を記録しながら後ろ向きに2回ループを回すと計算できます。
この表を見て飛ばし飛ばしに i を増やしていくと O(|s| + |t|) 時間で最小値が求まります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc138/submissions/7001784
上記の本番で提出したコードは実装が場当たり的だったので、以下の通り書き直しました。
解説 PDF にある通り s を2個つなげた文字列を考えると、折り返しの処理が楽です。