F - Score of Permutations 解説 by ngtkana
next_permutation の要領で自然数の分割を列挙することで \(O(N p(N))\) 時間で解くことができます。
解法
\(A\) が自然数 \(N\) の分割であるとして、\(A\) よりも辞書順で大きな辞書順最小の \(N\) の分割を求めましょう。
- 後ろから見て最初に増加する箇所を探し、\(A_i\) とおきます。(もう少し厳密にいうと \(A_i \gt A_{i + 1} = A_{i + 2} = \dots\)、ただし \(A_i\) は末尾ではありません。)
- \(A_i\) を \(1\) 増やし、あまりをすべて \(1\) にします。
逆順に走査することもできます。
pub fn next_partition(a: &mut Vec<usize>) -> bool {
let Some(mut sum) = a.pop() else { return false };
if a.is_empty() {
return false;
}
while let Some(x) = a.pop() {
sum += x;
if a.last().map_or(true, |&last| last > x) {
a.push(x + 1);
a.extend(std::iter::repeat(1).take(sum - x - 1));
break;
}
}
true
}
pub fn prev_partition(a: &mut Vec<usize>) -> bool {
let Some(i) = a.iter().rposition(|&x| x != 1) else { return false };
let max = a[i] - 1;
let mut sum = a.split_off(i).into_iter().sum::<usize>();
while sum >= max {
a.push(max);
sum -= max;
}
if sum > 0 {
a.push(sum);
}
true
}
参考記事: next_permutation と同様に列挙できるもの一覧
提出
Rust (118 ms): https://atcoder.jp/contests/abc226/submissions/47515126
投稿日時:
最終更新: