yukicoder contest 376 C
解き方
※ ここに書く解き方は、解説に書かれている方法とは異なり、計算量が$ O(N \log^{2} N) である方法である。 ※ また、余談として少し改善して計算量が計算量が$ O(N \log N) となった方法についても述べている。
$ 1 以上$ N-1 以下の整数$ i について、次の条件を満たす整数$ S_{i} を考える。
$ A_{i} \lt A_{i+1} のとき、$ S_{i} = 1
$ A_{i} = A_{i+1} のとき、$ S_{i} = 0
$ A_{i} \gt A_{i+1} のとき、$ S_{i} = -1
このとき、$ 1 \le i \lt j \le N を満たす整数$ i と$ j について、次が成り立つ。
$ i 以上$ j 未満の任意の整数$ k について$ S_{k} = 0 であるとき、$ X_{i} と$ X_{j} は等しい
数列$ S_{i},S_{i+1},\ldots,S_{j-1} が$ 0 以外の要素を持ち、$ 0 以外の要素で最も先頭に近い値が$ 1 のとき、$ X_{i} は$ X_{j} より大きい
数列$ S_{i},S_{i+1},\ldots,S_{j-1} が$ 0 以外の要素を持ち、$ 0 以外の要素で最も先頭に近い値が$ -1 のとき、$ X_{i} は$ X_{j} より小さい
以上より、$ 1 \le i \lt j \le N を満たす整数$ i と$ j について、上のどれであるかを判定することで$ X_{i} と$ X_{j} の比較ができる。
よって、このような判定を行う処理をセグメント木で実装すれば、$ O(\log N) の計算量で$ 1 回の比較ができる。
$ O(N \log N) の計算量で実行できるソートアルゴリズムと合わせれば、$ O(N \log^{2} N) の計算量でソートできる。
ソートができれば、その$ K 番目を確認することで答えが求められる。
以下余談
ちなみに、上ではセグメント木で実装すると書いたが、途中で更新されるわけではないためセグメント木である必要性は小さい。
ほとんど同じことだが、長さが$ 2 の累乗に等しい区間全てに対して前計算しておくという方法でも同じようなことができる。
（Sparse Table というものがあるらしい？ それを使えば$ O(N \log N) の計算量で計算できそう）
それ以前に、各$ i について、$ i 以上の$ j で$ S_{j} \neq 0 となるもののうち最小の$ j を計算しておくだけでも、$ O(1) で比較できる。
この計算は$ O(N) で可能であるため、全体としてはやはり$ O(N \log N) の計算量で計算可能である。
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
また、さらに下には余談として述べた、$ O(N \log N) の計算量で計算する方法で実装したものについても記載している。
code: C
int size = 1;
void set_segt (int *t, int idx, int val, int size) {
idx = idx+size-1;
while (idx > 0) {
idx = (idx-1)/2;
} else {
}
}
return;
}
int add_segt_rec (int *t, int a, int b, int k, int l, int r) {
int ans = 0;
if (r <= a || b <= l) {
return 0;
}
if (a <= l && r <= b) {
}
ans = add_segt_rec(t, a, b, 2*k+1, l, (l+r)/2);
if (ans == 0) {
ans = add_segt_rec(t, a, b, 2*k+2, (l+r)/2, r);
}
return ans;
}
int add_segt (int *t, int a, int b, int size) {
return add_segt_rec(t, a, b, 0, 0, size);
}
int cmp_idx (const void *ap, const void *bp) {
int a = *(int *)ap;
int b = *(int *)bp;
if (a == b) {
return 0;
}
if (a > b) {
return (-1)*cmp_idx(bp, ap);
}
return add_segt(t, a, b, size);
}
int main () {
int n = 0;
int k = 0;
int res = 0;
res = scanf("%d", &n);
res = scanf("%d", &k);
for (int i = 0; i < n; i++) {
res = scanf("%d", a+i);
}
while (size < n) {
size <<= 1;
}
for (int i = 0; i < n-1; i++) {
int val = 0;
val = 1;
val = -1;
}
set_segt(t, i, val, size);
}
qsort(ans, n, sizeof(int), cmp_idx);
for (int i = 0; i < ansk-1; i++) { }
for (int i = ansk-1; i < n-1; i++) { }
for (int i = 1; i < n-1; i++) {
}
printf("\n");
return 0;
}
下は余談に記載した方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
int cmp_idx (const void *ap, const void *bp) {
int a = *(int *)ap;
int b = *(int *)bp;
if (a == b) {
return 0;
}
if (a > b) {
return (-1)*cmp_idx(bp, ap);
}
return 0;
}
}
int main () {
int n = 0;
int k = 0;
int res = 0;
res = scanf("%d", &n);
res = scanf("%d", &k);
for (int i = 0; i < n; i++) {
res = scanf("%d", a+i);
}
for (int i = 0; i < n-1; i++) {
}
}
} else {
}
for (int i = n-3; i >= 0; i--) {
} else {
}
}
qsort(ans, n, sizeof(int), cmp_idx);
for (int i = 0; i < ansk-1; i++) { }
for (int i = ansk-1; i < n-1; i++) { }
for (int i = 1; i < n-1; i++) {
}
printf("\n");
return 0;
}
私の提出一覧
table: submissions_yukicoder_contest_376_C
提出のURL 提出時刻 結果 備考
感想
この問題は解くのに30分間以上かかっていて、解いているときもかなり悩んだ覚えがある。
きちんと整理すれば$ O(N) で計算する方法がありそうな気がするが、なかなか考えがまとまらなかった。
結局、上に書いた条件を思いついたので、難しいことは考えずにqsort 関数を使ってソートすることにした。
ただ、単純に実装すると間に合わないかもしれなかったので、セグメント木を使った。
余談で書いた通り、セグメント木を使う必要はなくて、$ O(N) の前計算をしておけば良いだけだった。
これはコンテスト中に気づくべきだった気がする。