CS Academy #20 - Palindromic Concatenation
問題
問題概要
文字列が個与えられる。番目の文字列をと表す時、との連結(この順番に並べて結合した文字列)が回文になるような組の個数を求めよ。
- は英小文字のみで構成される
- とは区別される
アイデア
が回文になる時、どのような状況になれば条件を満たすかを考えてみる。この条件は文字列の長さに依存するので、以下のように3つに条件を分けて考える:
1のときに満たすべき条件はシンプルで、をreverse
したらに一致することである。
次に、2のときに満たすべき条件を考えてみる。の方が短いので、回文の中心はの途中の位置に来ることになる。よって、それぞれの文字列の長さをとおけば
- を
reverse
した文字列との末尾から文字が一致 - の先頭から文字が回文になっている
という2つの条件を同時に満たす必要があることが分かる。
3についても対称に考えれば、
- を
reverse
した文字列との先頭から文字が一致 - の末尾から文字が回文になっている
という2つの条件を同時に満たす必要があることが分かる。
の制約から、それぞれのペアをとってきて比較するということは間に合わなさそうなので、別の方針を考える必要がある。 そこで、ハッシュ値を利用して各とペアを作ることが出来る文字列の個数を探す。
条件1に関しては、各文字列をreverse
したときのハッシュ値をカウントしておけば簡単に計算できる。以下では2,3について考える。
まず、個の文字列は長い方から順に処理していくことにする。そして、mapにハッシュ値をカウントしていく。そのときに、先頭から文字が回文になっていれば残りの末尾の文字のハッシュ値を+1し、末尾から文字が回文になっていれば残りの先頭の文字のハッシュ値を+1とする。
この、「回文になっているかどうか」という判定は、各文字列に対して元の文字列と、reverse
した後の文字列でそれぞれローリングハッシュを構築し、そのハッシュ値の比較をすることでで判定することが可能になる。
各文字列に対して、ペアを作ることが出来る文字列の個数はこのをreverse
したもののハッシュ値のカウントに一致する。
実装(C++)
続きを読むCF 798 D - Mike and distribution
問題
問題概要
長さの数列とが与えられる。
いま、数列のindexを個選ぶことが出来る。選んだ個のindexをとするとき、次の条件を満たすように個のindexを選べ:
このような条件を満たすを答えよ。
アイデア
まず、は多いほうが得だから限界まで増やすことにする。
そして、このとのペアを、残っている中で、aが最大
→bが最小
→aが最大
→…と交互にルールを適用していって並べていく。例を示すと、の時は次のようになる。
このように並べることで、局所的に大小関係が発生するので、奇数番目に現れるものを選んでいけば必ず全体の和の半分より大きい値を得られる。が偶数の時は、最後のindexを1つ前に詰めておけばよい。
乱択でも通ってしまうっぽい…(submission)。