UTPC2020 運営記

UTPC2020運営のidsigmaです。今回は問題に直接かかわることは少なかったですが、一応仕切り役をやっていました。適当に感想を書きます。

経緯

  • なんかのいみがやりたいと言い出す
  • 乗り気になってメンバーを集める
  • 今は亡きUtCoderでコンテストをやろうとしていたメンバーに声をかける
  • 足りないと思ったのでwriterを追加で募集する、あまりやりたくないがレートで制限をかけないと集まり過ぎると思ったのでしょうがなくレートで制限をかける
  • 集まる　原案募集開始

作問作業開始まで

  • 僕は簡単枠だけ投げて仕切りに徹しようと思い投げるつもりがなかった
  • 期待通りみんな投げてくれる
  • なんか全体的に難しくないか
  • ある程度集まった後恒例の空白期間

作業

  • セットを決める、いろいろあるがなんとか決まる
  • 心の中でこのセット難しいんじゃないかと思いつつ黙る
  • メンバーにgitとかrimeについて教える
  • 作業開始
  • 実はゆきこでtesterしていた問題がセット内にあったのだが、この時点では言えず、そのままゆきこで出たので没になる

  • みんなが頑張る
  • 途中で2問くらい爆破される、最初は15問だったが結果的に13問に
  • チーム戦のルールはノリで決まった、まあこの辺でこのセットだいぶ難しいという共通認識はあったっぽい

tester投入

  • AtCoderのtesterをやってることもあり信頼度の高いmaspyさんにお願いした
  • 問題文、テストケースなど、さまざまな観点にわたりご指摘、ご意見をいただきました。本当にありがとうございました。
  • risujirohにも何問か解いてもらう

直前期

  • 2日前に全員で問題文の読み合わせと校正をする、4時間かかる(ひえー)
  • のいみが論文の添削を受ける卒論生みたいで草だった(人は卒論を超えて強くなります)
  • 開始2時間前にJのTLEしやすいケースが入る

各問題について

A

  • 原案
  • 1問くらいは簡単なのを置かないとね
  • 1問くらいは東大ネタを入れておこうかなと思った
  • 実在するサークル勧誘イベントです
  • 僕はテント列には入らず横道から抜けて友達と遊びに行きました

B

  • 難しい数え上げ1
  • 原案時にはdiff2200とか言われてた(は？)
  • むずいやん
  • 是非考えてね

C

  • 構築
  • generator、テストケース作るのが大変だった
  • なんかtester勢が普通に解いてたのでそこまで難しくないのかあと思ってた
  • どうしてこんなことに

D

  • 2乗で提案されたのが高速化された
  • 問題文の表現が難しくて校正に時間がかかった
  • まあまあ解かれると思った

E

  • 難しい数え上げ2
  • 難しいので部分点を提案
  • testerをしたけどわからず想定解を見て感動
  • 是非考えてね2

F

  • さかな「簡単枠も置かないとね～」
  • のいみ「すぐ解けました」
  • なんか難しい気がするけど2人がそういうならそうなんだろう！
  • ばかやろう
  • さかなくんがケース生成をしっかりやっていてきっちり嘘が落ちていた(素晴らしい)

G

  • Alt3「これ難しいですかね」
  • 皆「難しいです」
  • ヒントをもらう
  • 「いや簡単やんけ」
  • でも解かれないという予想でした
  • 天才の多いこと
  • outputcheckerは気を付けようね

H

  • writerです
  • 簡単枠(とはいえABC-Eくらい？)
  • 1×1のケースがサンプルにあったが前日に消滅した
  • その結果結構WAが出ていていい感じの役割を果たしたようでよかった

I

  • グラフがなかったのでのいみが生やした
  • 卒論生のいみ1
  • マージテクの逆、言われてみないと気づけないな
  • toptreeを使ってくるbeetの提出を全力で落ちろと言っていた

J

  • 判定問題
  • 一回writer解とtester解が落ちることが他の人によって指摘される(危ない)
  • 開始2時間前にTLEしやすいケース(cornerだったかな)が追加される、このケースがすごい仕事をする
  • ハマりやすい問題で大変だったと思う

K

  • 原案はCを構築するだけだったがなんか非想定が通っちゃうので落とすためにこういう設定になった
  • 卒論生のいみ2
  • のいみちゃんとのいむくん
  • 無能な高橋先生
  • 読んで考えてみてね

L

  • 数論
  • tester達にあっさり解かれ数学系の人には一瞬なのかと思っていた
  • そうでもなかった

M

  • 大変な幾何
  • 考察は知識があるとだいぶ楽らしい
  • この見た目でセグ木とかになるのすごい
  • 実装が大変です
  • maroonさんありがとう
  • みんなもやってみよう！

セット全体に関して

  • こうなるとは思っていました
  • すいません
  • ルールで脅したからゆるして
  • やり応えのある問題が多いので是非upsolveしてみてください

まとめ

  • なんだかんだ楽しんでもらえたような気はしています、感想をツイートしてもらって、さらにupsolveしてもらえたりすることは運営としてはこの上ない喜びです
  • ご参加ありがとうございました
  • 仕切り役(admin)はレートが高い人の方がいいです
  • 個人的な反省が多かったので、近々作問作業tipsをまとめようかと思ってます

伝家の宝刀　クエリ平方分割について

はじめに

　本記事は、競プロアドベントカレンダー2020 の12/15分の記事です。ネタに困っていたんですが、Twitter上でクエリ平方分割に関する記事がほとんどないという声を見て、殴り書きではありますが本記事を作成することにしました。易しい問題を例にクエリ平方分割を使った解法の例を示した後、いくつか少し手間のかかる問題を見ていきます。実装量がある程度かさむことになりがちなので、自分で一から実装することをお勧めします。想定読者層としては水～青色を想定しています。

クエリ平方分割とは

　 クエリ平方分割というのは、その名の通り、与えられたクエリを(その数をQとします)O(\sqrt{Q})ごと1に分割してクエリをうまく処理すると、なぜか計算量がo(NQ)に落ちる2というテクニックです。例えば、長さが Nの配列に関するQ個のクエリが与えられたときに、次のような処理をしたとしましょう。

  • Q個のクエリをO(\sqrt{Q})個ごとに分割すると、全部でO(\sqrt{Q})個のブロックができる。
  • 各ブロックごとに、次のようにする。
    • まず、O(N)で何らかの前処理をする
    • 各クエリを、同一ブロック内のクエリだけを見てO(\sqrt{Q})で処理する。

このときの計算量を考えます。まず、O(N)の処理をする回数はO(\sqrt{Q})回です。さらに、各クエリの処理にO(\sqrt{Q})かけているので、クエリの処理自体にかかる計算量はO(Q\sqrt{Q})です。よって、全体の計算量はO(N\sqrt{Q}+Q\sqrt{Q})となり、たしかにo(NQ)となっています。ちょっとした工夫しかしていないのに、ちゃんと計算量が落ちるところがこのテクニックの面白いところだと思います。このテクニックを適用する際は、「ブロック内の処理の初めに どのような前処理をすれば、各クエリO(\sqrt{Q})で処理できるようになるか？」を考えることになります。
　それでは、クエリ平方分割の適用例を紹介していきます。

クエリ平方分割の適用例

ABC185 : Range XOR Query

　最近出題されたABCの問題を例にとります。この問題はSegment Treeを使って解くことができますが、あえてクエリ平方分割で解くことを考えてみましょう。

　各ブロックに対する処理を考えます。まずクエリの処理の前に、この時点での配列の累積xorを計算しておきます(O(N))。クエリの処理では、更新クエリでは元の配列を単に更新するだけです。解答クエリは、まず累積XORの情報から該当区間の値を取得します。その後、現在のブロック内における自分より前の更新クエリを見に行き、該当区間に更新があればその変更を答えに反映します(xorをとるだけ)。クエリを分割したことで、更新の影響を愚直にO(\sqrt{Q})かけて確認してよいところがクエリ平方分割の利点です。

　実装例はこちらですが、累積xorをブロックの処理の最後に取るなど上記の説明と少し順番を変えています。

　ところで、ブロック内の処理では次のような方法も考えられます。最初に累積xorをとるところは同じです。その後、ブロック内のクエリに登場するindexを覚えておきます。このindexとして考えられる値はO(\sqrt{Q})個しかありません。このindexたちを座標圧縮し、適切にもとの配列の情報を載せれば3、長さO(\sqrt{Q})の配列が完成します。ここまでやってしまえば、各クエリの処理を愚直に行っても毎回O(\sqrt{Q})で終わり、先ほどと同じ計算量のオーダーが達成されます(前処理の定数倍が重いですが)。実装例はこちら。

　このように、各ブロック内でクエリが関わる位置がO(\sqrt{Q})個しかないことを利用して、O(\sqrt{Q})個の配列に圧縮してからあとは愚直にやる、という流れもクエリ平方分割の適用の1つです。しつこいですが、どのような前処理をすればブロック内のクエリの処理を\sqrt{Q}で終えられるか？ということを考えるのは、クエリ平方分割の肝と言えるでしょう。

パ研合宿2019 Day-2-G:Bichrome Tree Connectivity

　クエリを平方分割し、ブロック内の処理を考えます。ブロック内ではクエリが飛んでくる頂点がO(\sqrt{Q})個しかないことに注目して、木を圧縮して頂点数がO(\sqrt{Q})個の森にすることを考えます。クエリが飛んでくる頂点はそのまま残します。そうでない頂点のうち、黒い頂点はそのブロック内では黒いままなので残しません。白い頂点は、まず白い頂点だけからなる各連結成分を1つに圧縮し、その元々のサイズを覚えておきます。そして、圧縮した1つの頂点と、その連結成分に隣接するクエリが飛んでくる点を辺で結びます。このようにすると森が完成しますが、ウニのようなケースで頂点がO(N)個になってしまう可能性があります4。そこで、圧縮した頂点のうち、次数が1のものは、その頂点と結ばれているクエリが飛んでくる頂点にマージしてしまいます。このようにすると、この森の頂点数がO(\sqrt{Q})になることが示せます。
　クエリの処理は、更新も解答も愚直にやるだけでO(\sqrt{Q})となります。実装例はこちらです。

困った時のクエリ平方分割

　想定解とは異なっていても、ブロックサイズの調整と定数倍高速化を頑張ることで、クエリ平方分割で通せる場合があります。

JOI2016春Day2 : 雇用計画

　想定解はO ( (N+Q) \log N)だったと思いますが、クエリ平方分割で解くことを考えます。
　両端に-\inftyを入れておきます。B_jが与えられたときの答えは、B_j以上の数からなる区間の個数ですが、代わりに区間の境界の数を考えることにします。クエリを平方分割し、ブロックごとの処理を考えます。N+1個の境界について、今のブロック内について区間の境界となり得るようなB_jの値は区間をなしているので、B_jをソートしておけば二分探索+imos法で各境界の解答クエリのへの寄与を加算することができます。あとは各更新クエリの度に、影響のある解答クエリの答えを再更新すればよいです。前処理にlogがつくこともあり、ブロックサイズの調整と定数倍高速化を頑張るとACできます。
　実装例はこちらです。TL5secなのでギリギリです。

その他の問題

　見つけたら随時追加します。

おわりに

　クエリ平方分割について簡単に紹介しました。クエリ平方分割が想定解という問題ももちろんありますが、非想定でもクエリ処理の問題で困った時になんとかする方法としても有力です。ご使用の際にはブロックサイズの調整にご注意ください。

  1. 実際はブロック内での処理にlogがついてるかとか、定数倍がどうかで1ブロックあたりのクエリ数をいくつにするかを調整したりします。 ↩

  2. o(f(n))というのはオーダーがf(n)未満というイメージです。↩

  3. 具体的には、クエリに登場するindexをソートした配列をb_1,b_2,\cdots,b_nとして、 A_{b_i}, \cdots , A_{b_{i+1} - 1}をxorした値を持っておきます。↩

  4. ウニの中心にしかクエリが来ていない状態でこれをやると…？↩

鹿島建設プロコン2020-D Binomial Coefficient is Fun

　公式解説とは異なる、経路数を考えることによる導出を紹介する。

考察

　とりあえず、各B_iを固定して考えよう。 _{B_i} C _{A_i}というのは、縦が B_i-A_iマス、横がA_iマスのグリッドにおいて、左下から右上に右移動と上移動だけで向かうときの経路の数に等しい。この値を掛け算するので、なんとなく大きなグリッドを作りたくなる。

f:id:sigma1113:20201206131454p:plain
これを...
f:id:sigma1113:20201206131623p:plain
こう！

　上図における橙と緑の長方形を通る経路の積がB_iの値を決めたときの答えへの寄与である。本来は\sum B_i \leq MにおけるすべてのBについての和を求めよ、という問題だから、縦を M - \sum Aマスにして、上に移動することがB_iの値を1大きくすることに対応させれば、縦が M - \sum Aマス、横が \sum Aマスのときの左下から最右列のいずれかの点への経路数が答えだ！と信じたいくなる。ところが、残念ながらサンプル1さえ合わない。縦の長さをB_iに対応させようという作戦だったが、上図の橙と緑の長方形の境界部分の点から上に移動することが、B_1に寄与するのかB_2に寄与するのかの対応が不明瞭になるのである。
　そこで、この間に1列足してみる。

f:id:sigma1113:20201206132522p:plain
これならどうだ

　この1列を横に移動することが、上に移動することをB_iへの寄与からB_{i+1}への寄与に変えるという役割を果たす。このようにすれば、左下から最右列へのいずれかの点への経路のとったときに、今足した1列をどこで通り過ぎたかを見ることで、Bとの対応をとることができる。
　従って、答えはS = \sum A_iとして、 M-Sマス、横がS+N-1マスのグリッドにおいて、左下から最右列のある点に右移動と上移動だけで向かうときの経路数に等しくなる。ところが、ゴール地点がO(M)個あるので、このまま計算しようとしても間に合わない。そこで、さらに右に1列足してみる。

f:id:sigma1113:20201206133703p:plain

1列追加する前のグリッドの「左下から最右列のある点に行く経路数」が答えだったが、赤い列を横に移動することが、この「ある点」を決めることに対応することがわかる。つまり、答えは「 M-Sマス、横がS+Nマスのグリッドにおいて、左下から右上の点に右移動と上移動だけで向かうときの経路数」となる。これは _{M+N} C _{S+N}であり、公式解説の述べる値に一致した。

HUPC2020 Day3 運営参加記

idsigmaです。HUPC2020 Day3の運営側の感想を書いていきます。 ちなみに解説リンクは以下になります。

https://drive.google.com/drive/folders/1zkt1cO4580zyypgXHAyxdIxiBBRM7TbZ?usp=sharing

A

  • この位置に何置くか難しいよね
  • 大学合宿をテーマにしてみた
  • Aだしこれくらいでいいよね

B

  • 原案はつぶあん
  • みんな「まあこういうのは300やろ」と思いながら300をつける
  • そのままBの位置へ
  • 直前に難しくね？という雰囲気になるが、直前なのでそのまま
  • ごめん....

C

  • 原案です
  • こどふぉdiv2-Cみたいな感じで出した
  • 既出だったらしい(こどふぇす)
  • やむなくがケース生成をめちゃくちゃ頑張っていたので結構落ちていた

D

  • やむなくらしいinteractiveの良問
  • 既出や名前のついているソートをするだけでできるみたいな話があって何回か改題された
  • ところで前日までジャッジが動かなかった
  • ジャッジの仕様はちゃんと確認しようね！

E

  • 幾何典型らしい
  • 幾何の典型、知らず...
  • 問題文に結構不備があったようでコンテスト中clar対応/修正で大変だった
  • ごめん...

F

  • AtCoder枠
  • これ結構難しいと思うけどみんな天才だから結構解かれるんだろうなあ
  • みんな天才でした

G

  • 原案です
  • カツサンド枠
  • カツサンド懐かしいね
  • 問題設定凝ったけどあんまり言及されなくて悲しい
  • それはそれとして操作の説明が少し足りなかったかもね
  • ごめん...
  • 見た目がいかついけどABCにも出そうな典型詰め合わせ問題です

H

  • umgくんがいるけど原案はてんぷらさん
  • 誰も準備をしたがらないので(それはそう)僕が準備をすることに
  • てんぷらを許すな
  • 愚直書いて合うまでキレながら準備をする
  • henoくんがtester解を書いてくれるが落ちまくる
  • てんぷらを許すな
  • ↑前日にコードを書いて通していたので許した
  • beetからジャッジが間違っていないか？と言われる
  • 愚直とも合わないので間違っていないと返す
  • beetにジャッジ合ってたわと言われる

f:id:sigma1113:20200917113855p:plain

I

  • 良い簡単枠
  • 微妙に見つかるのが遅かった

J

  • 原案です
  • ABC-Fくらいのつもりでした
  • なんでだよ
  • 順位表を見ながらなかなか解かれないのでなんでだよと言っていた
  • FAが2:35とかで後ろの方みたいな雰囲気になってしまった
  • この頃には30チームくらいには解かれてる予想だったんだよね
  • なんでだよ
  • FAが出て以降はそこそこ解かれたけど結局12チーム
  • 順位表は怖いね
  • お気に入りなので解いてない人はぜひ考えてね

K

  • 原案です
  • フレンeルスタリオっていうVtuberがいるんですがそのマリカ配信を見ながら設定を考えた(この情報要る？)
  • なんか解けた
  • 順位の期待値の言い換え面白くない？
  • 計算パートはちゃんと対策してる人にとってはおまたせだしそうでない人には大変という感じで難易度評価が難しい
  • まあ総合すれば難しめに入ると思ってます
  • risujirohにえでゅふぉのラストっぽいと言われる、そうだね
  • えでゅふぉを埋めましょう

L

  • やむなくらしいグラフの良問
  • 詰め切る直前までは割とスムーズに考察が進むので600点！w
  • 前日にやむなくがコーナーケースに気付きtester解がhackされる
  • 何が600点だよ
  • こんなことあるんやなあ
  • 結果的に前日に追加されたコーナーケースに結構ハマってくれる
  • やむなくはすげえよ

M

  • これまあまあ難しいと思うんだけど結構とかれてびっくりした
  • これもちょっと問題設定が変わるなどがあった
  • 北海道高校は実在しないらしい

全体

  • 飛びぬけた難問があるわけではないセットで全完が出たのは予想通り
  • 全体的な順位表の傾向としては予想していたものと結構外れた
  • けどまあ傾斜は結構よくていいセットだったんじゃないですか？

作業について

  • なんか問題文のhtml化とか先生とのやりとりとか振るのが面倒なので自分がやっちゃって勝手に破滅していた(破滅はしてないので大丈夫です)
  • 自分としても面白いかなという問題が出せて満足
  • rimeとかgitをまあまあ使えて開発力の向上を実感(ほんまか？)
  • 作業の進め方には結構反省点があった、実際前日前々日に熱烈作業をする羽目になった
  • 反省を生かせる日は来ないかもなあ

最後に

  • ご参加ありがとうございました。ぜひ復習してくれれば運営としては嬉しい限りです。
  • みんなも作問しよう！

ARC068-E : Snuke Line

　公式解説とは異なる解法を紹介。典型的な考え方を知っていると頭をあまり使わずに済むかも。

問題

atcoder.jp

考察と解法

　とりあえずdを止めておく。区間 [kd , (k+1)d]と重なる名産品の区間の数が答えなわけだが、異なるkの値について同じ区間が重なると数えるのが面倒である。しかし、区間 [kd , (k+1)d]に真に含まれる区間、つまり区間 [l,r]であって、 kd \lt l \leq r \lt (k+1)dを満たすものは異なるkの値について同じものはない。これはdに対して条件を満たさないような区間であるから、これを数えることにしてみる。

　このような状況は典型的で、区間[l,r]を2次元平面上の点(l,r)にプロットしてみよう。区間 [kd , (k+1)d]に対して kd \lt l \leq r \lt (k+1)dを満たす区間に対応する点は、2次元平面上において、(kd,(k+1)d)の右下に当たる点に対応する。このような点の数は、平面走査によて数えることができる。つまり、x座標(lの値)の大きい順に走査し、y座標(rの値)はSegmentTreeなどで管理すればよい。
　dを固定した場合は解けたが、d=1,\cdots,Mについて解く必要がある。しかし、考えるべき区間の数は調和級数によりO(M\log M)であり、すべてのdについて一度に平面走査を行えばよい。

実装

atcoder.jp

平面走査はやっていることの割に実装が軽い。

ARC066-D:Xor Sum

ある意味有名な(?)問題。解説と少し違ったので思うので書いてみる。

問題

atcoder.jp

考察

　とりあえず、xorと和の関係を表す式であるところの a + b = a \ \mathrm {xor} \ b + 2 (a\ \mathrm{and} \ b) \cdots (*)を書いてみる。この式は、2つの自然数の足し算というのは、桁ごとの和(xor)と繰上がりに分解できるということを言っている。この式から a + b \geq a\ \mathrm{xor} \ bがわかり、つまり問題文でいうところの v \geq uがわかる。つまり、 v \leq Nということだけ考えれば、N以下ということは自動的に満たされる。
　v \leq Nを固定したときに、条件を満たすuの数を数えたい。当然vをすべて試すわけにはいかないので、うまい方法を考える。(*)式を見ると、v = (a+b)と a\ \mathrm{and}\ bの値を決めれば、u (= a\ \mathrm{xor}\ b)の値も決まることがわかる。そこで、vの値を決めたときに、 a \ \mathrm{and}\ bとしてあり得るものを数えることを考えてみる。これはvの2進数表記の各桁が、0か1かを決めながら数えられそうである。そこで、vの上位の桁から決めていく桁dpを考えることにする。ところが、上から決めるにあたって、vの各桁の値を決めていくだけでは正しく数えることができない。それは、足し算に繰り上がりがあるからである。そこで、今の桁は下の桁からの繰上あがりを考慮するか？という情報を持つことにする。dp定義をまとめれば

  • dp _ {i,j,k} : a + bの値を上からi桁目まで決めたときのa\ \mathrm{and}\ bの通り数。ここで、jはa+b \lt Nが確定しているかどうかのフラグ、kはi-1桁目からの繰り上がりを考慮しているかどうかのフラグ。

dpの遷移は難しくない(実装参照)。例えばa+bの上からi+1桁目を1にするときを考える。a\ \mathrm{and} \ bを1にしたい場合、上からi桁目に繰り上がりが生じるので、dp _ {i,j,1}からの遷移が行われることになる。a\ \mathrm{and} \ bを0にしたい場合、上からi+1桁目への繰り上がりを考慮するかどうかで、遷移を場合分けすることになる。答えはNが2進数表記でn桁であったとして、dp _ {n,0,0} + dp _ {n,1,0}となる。

実装

atcoder.jp

この解法は思いつきやすいと思う。

CodeCraft-20 - F:Battalion Strength

解けたけど、コンテスト中のACは遠い...。

問題

codeforces.com

考察と解法

　期待値の代わりに総和を考えることにする。スコアが和の形をしているので、2つの数の積 p _ i p _ jが足される集合はいくつあるかを考えよう(0-indexedとする)。といってもこれは簡単である。あらかじめ pを昇順にソートしておけば、 iとjの間にある数は集合内に1つも存在してはならず、他のものは自由に決められるから、条件をみたす2 ^ {i + N-j-1}個である。クエリが1個の場合はなんとかなりそうだ。
　変更クエリが飛んでくるのが厄介だが、今述べた計算をセグ木に載せることを考える。左側の区間Lにはp _ 0, p _ 1,\cdots, p _ {n-1}という数列があり、右側の区間Rはq _ 0, q _ 1,\cdots, q _ {m-1}という数列があり、それぞれ昇順に並んでいるとする。また、2つの区間をマージした区間をIとする。
　各区間での答えval _ L,val _ Rがわかっていて、マージした後の答えval _ Iを知りたいとしよう。val _ Lについては、右側にm個だけ使える数が増えたので、val _ Iへの寄与は 2 ^ mになる。 val _ Rの寄与も同様となる。問題は、p _ i q _ jという形の項をどうするかで、これはval _ L,val _ Rだけでは計算できない。マージ後の区間については、 p _ i q _ jは2 ^ {i+m-j-1}回足されるわけだから、val _ Iへの寄与は p _ i q _ j 2 ^ {i+m-j-1} = p _ i 2 ^ i \times q _ j 2 ^{m-j-1}となる。これをi,jについて足し合わせるわけだから、 Lの \sum _ i p _ i 2 ^ iの値と Rの \sum _ j q _ j 2 ^{m-j-1}の値がわかっていればよい。これで答えを計算するのに必要な情報は揃った。結局、各区間にもたせる値は

これらの値のみで、マージ後のこれらの値も定数時間で計算できる。これでセグ木に載せる準備が整った。
　実装は、クエリを先読みし、重複する値も区別しながら各数にidを割り振るとよい。セグ木で管理する配列の長さがN+Q個になるので、定数倍には注意したい。

実装

codeforces.com