[AtCoder] ABC077 C – Snuke Festival

Snuke Festival

https://beta.atcoder.jp/contests/abc077/tasks/arc084_a

自分では解法が思いつかなかったので、解説を見ることにしました。

問題の意図は理解できたんですが、コードに落とし込むまでには至りませんでした。

考え方

題意

条件を満たす各パーツの組み合わせを答える問題です。具体的には、 \( A_i < B_j < C_k \) を満たす \( i, j, k \) の組み合わせを数え上げます。

方針

各パーツのサイズの配列が整列されていると、ある値より大きい又は小さい配列の要素数を二分探索で求めることができます。なので、始めにサイズの配列をソートしておきます。

どの値を基準にして要素を数え上げるかを考えます。例えば、 \( A_i \) の値を基準にして、 \( B_j, C_k \) の値を数え上げるには、条件を満たす \( B_j \) の値を固定し、\( C _k\) を二分探索する必要があります。

次に、\( B_j \) の値を基準にして、\( A_i,  C_k \) の値を数え上げるには、それぞれ二分探索を行うことで解決できます。どのような二分探索を行うかですが、 条件を満たす  \( A_i \) の中で配列の要素番号が最も大きいものを探します (upper bound) 。次に、条件を満たす \( C_k \) の中で配列の要素番号が最も小さいものを探します (lower bound) 。

上記の基準の二分探索を行ったときの、\( A_i \) の要素番号を \( i_a \)、\( C_k \) の要素番号を \( k_c \) とすると、組み合わせの数は、

$(i_a + 1)(N – k_c)$

となります。なお、配列の要素番号は0オリジンとしています。

二分探索については、

https://qiita.com/drken/items/97e37dd6143e33a64c8c

が参考になります。

ソースコード

感想

最初に考えたときは区間とかの数え上げかな?と思ったんですが、違いましたね。二分探索の上界と下界を求めるいう良い問題だと思いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする