ACM-ICPC 2017 国内予選 に参加しました
ACM-ICPCとは(公式サイト)
感想(ほぼ箇条書き)
去年と同じメンバーで出ました、この3人で出られるのは今年で最後。
模擬国内前までは、特にPCを制限したりせず、3人で集まったら何かの問題セット選んで一緒に考えるみたいなことをやってきてたら、模擬国内で爆死し、1台での立ち回りがヤバいみたいな感想になり、今回の国内予選は前半で詰まらないことをかなり意識しました。意識した結果2時間座ってしまった。
本番はABCと交代しながら、ほぼノータイムで実装が完了し(おそらく3完最速)、Dもそこまで悩まずにできて、あと2時間はEFGを見ながら自分は主にGを考えてたけどフローに行ってしまいおわり(未だにフローのどこがまずいのか分かってない(フローの勉強が足りなすぎる))
あとは、今回自分と同じ大学から参加してるチームが認識できてないけどかなりあって、他大とかを見ているとサークルとか、そういう学内交流の場があって世代が切れること無く参加してる大学がたくさんあって見習いたいです(自分が他人を指導できるご身分なのかというアレ)(これ去年も書いた気がする)。
本番はシステム的にトラブルとか障害もなくて良かったと思います(模擬みたいになってたら結果次第ではグチグチ言ってしまいそうなので)。
コーチや監督も引き受けて下さってありがとうございました。
去年(25位)より順位が落ちた(26位)が、†運営の慈悲†により通過できそうです…なんとも言えない感情すぎて、
より一層、精進しようという気持ちになった
今年こそ、JAG夏合宿とか参加したいなあと思っています
CS Academy #14 - Subarrays Xor Sum
問題
問題概要
長さの数列
が与えられる。長さが
以上
以下の部分列に対して、xorを取った値の和を
で割った余りを答えよ。
アイデア
ビットごとに独立に考えていく。今、ビットを固定する(とする)と、もとの数列
は01の数列として見なすことができるようになる(
(a[i]>>b)&1)。
こうなると、このビット列の中の部分列の中で、xorの値が1になる個数を数えるという問題に答えれば良いということになる。
さて、一般的な数列の部分和と同じように数列の部分に対してxorをとったものも同様に計算できる。から
の部分和が欲しければ、prefix sum(
)を用意しておいてその
と
に注目すれば良い。
次に、この部分列の長さに対する制約(以上
以下)をどのように対処するかを考える。 個数を数えるにあたって、部分列の区間の右
を固定して考える。すると、この部分列の制約から区間の左のindexは
から
ということになる。つまり、
の値に注目して、区間
]のpreに対して0と1の値が何個ずつあるかを保持しながら、
を増やしていくことで、この更新の処理を尺取的にできるので１つのビットに対して
で計算ができ、十分に間に合う。
