裏紙

ほぼ競プロ、たまに日記

ACM-ICPC 2017 国内予選 に参加しました

ACM-ICPCとは(公式サイト)

3分でわかるICPC

感想(ほぼ箇条書き)

去年と同じメンバーで出ました、この3人で出られるのは今年で最後。

模擬国内前までは、特にPCを制限したりせず、3人で集まったら何かの問題セット選んで一緒に考えるみたいなことをやってきてたら、模擬国内で爆死し、1台での立ち回りがヤバいみたいな感想になり、今回の国内予選は前半で詰まらないことをかなり意識しました。意識した結果2時間座ってしまった。

本番はABCと交代しながら、ほぼノータイムで実装が完了し(おそらく3完最速)、Dもそこまで悩まずにできて、あと2時間はEFGを見ながら自分は主にGを考えてたけどフローに行ってしまいおわり(未だにフローのどこがまずいのか分かってない(フローの勉強が足りなすぎる))

あとは、今回自分と同じ大学から参加してるチームが認識できてないけどかなりあって、他大とかを見ているとサークルとか、そういう学内交流の場があって世代が切れること無く参加してる大学がたくさんあって見習いたいです(自分が他人を指導できるご身分なのかというアレ)(これ去年も書いた気がする)。

本番はシステム的にトラブルとか障害もなくて良かったと思います(模擬みたいになってたら結果次第ではグチグチ言ってしまいそうなので)。

コーチや監督も引き受けて下さってありがとうございました。

去年(25位)より順位が落ちた(26位)が、†運営の慈悲†により通過できそうです…なんとも言えない感情すぎて、

より一層、精進しようという気持ちになった

今年こそ、JAG夏合宿とか参加したいなあと思っています

CS Academy #14 - Subarrays Xor Sum

問題

CS Academy

問題概要

長さNの数列aが与えられる。長さがA以上B以下の部分列に対して、xorを取った値の和を10^9+7で割った余りを答えよ。

  •  1 \le A \le B \le N \le 10^5
  •  0 \le a_i \le 10^9

イデア

ビットごとに独立に考えていく。今、ビットを固定する(bとする)と、もとの数列aは01の数列として見なすことができるようになる((a[i]>>b)&1)。

こうなると、このビット列の中の部分列の中で、xorの値が1になる個数を数えるという問題に答えれば良いということになる。

さて、一般的な数列の部分和と同じように数列の部分に対してxorをとったものも同様に計算できる。iからjの部分和が欲しければ、prefix sum(pre)を用意しておいてそのpre_jpre_{i-1}に注目すれば良い。

次に、この部分列の長さに対する制約(A以上B以下)をどのように対処するかを考える。 個数を数えるにあたって、部分列の区間の右jを固定して考える。すると、この部分列の制約から区間の左のindexはj-B+1からj-A+1ということになる。つまり、pre_jの値に注目して、区間 [j-B, j-A]のpreに対して0と1の値が何個ずつあるかを保持しながら、jを増やしていくことで、この更新の処理を尺取的にできるので1つのビットに対してO(N)で計算ができ、十分に間に合う。

実装(C++)

続きを読む

CS Academy #20 - Palindromic Concatenation

問題

Archive

問題概要

文字列がn個与えられる。i番目の文字列をs_iと表す時、s_is_jの連結(この順番に並べて結合した文字列)が回文になるような組(i,j)(i \neq j)の個数を求めよ。

  • 1 \le n \le 10^5
  • 1 \le \sum_{i=1}^{n} | s_i | \le 10^5
  • s_iは英小文字のみで構成される
  • (i,j)(j,i)は区別される

イデア

s_i + s_jが回文になる時、どのような状況になれば条件を満たすかを考えてみる。この条件は文字列の長さに依存するので、以下のように3つに条件を分けて考える:

  1.  | s_i | = | s_j |
  2.  | s_i | \lt | s_j |
  3.  | s_i | \gt | s_j |

1のときに満たすべき条件はシンプルで、s_ireverseしたらs_jに一致することである。

次に、2のときに満たすべき条件を考えてみる。s_iの方が短いので、回文の中心はs_jの途中の位置に来ることになる。よって、それぞれの文字列の長さをI , Jとおけば

  • s_ireverseした文字列とs_jの末尾からI文字が一致
  • s_jの先頭からJ-I文字が回文になっている

という2つの条件を同時に満たす必要があることが分かる。

3についても対称に考えれば、

  • s_jreverseした文字列とs_iの先頭からJ文字が一致
  • s_iの末尾からI-J文字が回文になっている

という2つの条件を同時に満たす必要があることが分かる。

nの制約から、それぞれのペアをとってきて比較するということは間に合わなさそうなので、別の方針を考える必要がある。 そこで、ハッシュ値を利用して各s_iとペアを作ることが出来る文字列の個数を探す。

条件1に関しては、各文字列をreverseしたときのハッシュ値をカウントしておけば簡単に計算できる。以下では2,3について考える。

まず、n個の文字列は長い方から順に処理していくことにする。そして、mapにハッシュ値をカウントしていく。そのときに、先頭からx文字が回文になっていれば残りの末尾の文字のハッシュ値を+1し、末尾からx文字が回文になっていれば残りの先頭の文字のハッシュ値を+1とする。

この、「回文になっているかどうか」という判定は、各文字列に対して元の文字列と、reverseした後の文字列でそれぞれローリングハッシュを構築し、そのハッシュ値の比較をすることでO(1)で判定することが可能になる。

各文字列s_iに対して、ペアを作ることが出来る文字列の個数はこのs_ireverseしたもののハッシュ値のカウントに一致する。

実装(C++)

続きを読む