hogecoder

tsutaj 競技プログラミングの記録

分割統治法メモ

はじめに

これは自分の備忘録的に書いているだけであり、体系的に書いているわけではありません。ご了承ください。

ちなみに蟻本 +α くらいの情報をまとめている資料が以下にあります (ダイマ)

https://hcpc-hokudai.github.io/archive/algorithm_divide_and_conquer_001.pdf

オフラインにおける分割統治

Rollback をするテク

いくつかのデータ構造では、そのデータ構造がサポートしている操作の「逆」は難しいという話があります。たとえば UnionFind では辺の追加は普通に行えますが、削除は難しいといった問題があります。では、以下のようなクエリが要求されたときはどのように解けばよいでしょうか?

$$N$$ 個の頂点があり、はじめは辺がひとつも存在しない。以下のクエリを $$Q$$ 回処理せよ。($$N, Q \leq 10^{5}$$)

  • 頂点 $$u, v$$ 間に辺が存在しないなら辺を追加する。
  • 頂点 $$u, v$$ 間に辺が存在するなら辺を削除する。
  • 頂点 $$u, v$$ が同じ連結成分に属するかどうかを判定する。

クエリがオフラインであるとき、これは普通の UnionFind と分割統治を用いて処理できます。なお、これの類題が Educational Codeforces Round #22 F: Bipartite Checking です。

クエリで与えられるそれぞれの辺 $$(u, v)$$ について、その辺がクエリ全体においていつ存在したかを区間として覚えておきます (要するに奇数回目に出てきたときに開いて、偶数回目に出てきたときに閉じるようにして区間を作る、ということです)。こうしてできた区間の数は明らかに高々 $$O(Q)$$ 個です。以降の説明ではこれを「辺区間」と呼ぶことにします。

この区間それぞれを分割統治法で処理することを考えます。クエリのインデックスの区間 $$[L, R)$$ を分割統治するとき、$$[L, R)$$ を完全に覆うような辺区間は UnionFind に反映させて、より細かい区間 $$[L, \mathrm{mid}), [\mathrm{mid}, R)$$ について再帰的に解きます。

再帰的に解くことが終わったら、$$[L, R)$$ を完全に覆っていた辺区間の情報を UnionFind から削除します。こうすることで Rollback の機能を実現できます。ここで、UnionFind から辺区間の情報を削除するときにはどうすればよいのでしょうか?これは、UnionFind における有名な計算量改善テクのひとつである、「小さい連結成分を大きい連結成分にマージ」のみをやることで実現できます (経路圧縮をやると壊れることに注意します)。実は、UnionFind ではひとつ前の状態に戻ることは簡単にできるため、これを活用すると Rollback ありの UnionFind を実現できます。

マージテクのみを用いるとき、UnionFind の中の配列であって unite の前後で値が変化しうるのは、頂点 $$u, v$$ の代表元のみです。なので、unite の前における代表元に関する値を覚えておき、削除したいときにその覚えた値に戻すことで、削除操作が実現できます。

条件の一部を強制的に満たすテク

条件を満たすペアの個数を求める問題で、満たすべき条件がひとつではなく複数存在する場合があります。この場合、分割統治法で処理できる可能性があります。

問題例はいっぱいあるので以下を解いてください (雑)

オンラインにおける分割統治

正直これは分割統治かどうか微妙なんですが・・・

区間全体に対しては簡単に解け、さらにそれぞれの要素が独立に処理できる (ある要素が他のある要素による影響を受けない) 状況で、区間の一部 $$[L, R)$$ に対して問題を解いてほしいというときに、区間をいくつかのより小さい区間に分割することで処理できる場合があります。これはオンラインでもできるため一応「オンラインにおける」分割統治と書いておきます。

以下の問題を解いてみましょう。なお、紹介している問題は Educational Codeforces Round #26 G: Functions On The Segments です。

場合分けありの一次関数 $$f_i(x)$$ が $$N$$ 個与えられ、それぞれの関数は $$1$$ から $$N$$ まで番号付けられています (詳しい一次関数の形は元の問題を読んでください)。$$l_i, r_i, x_i$$ が $$Q$$ 回与えられますので、それぞれについて $$\sum_{k=l}^{r} f_k(x)$$ の値をオンラインで求めてください。

クエリにおいて区間の範囲の制約がなく、全部に対して $$f_k(x)$$ の値を足し合わせる場合、$$x_1$$ 以下であるもの、$$x_2$$ を超えるものを求めて適当に計算すれば良いです。これと同じ発想で、与えられた区間を $$O(\log N)$$ 個の区間に分割し (そのうちのひとつを $$[L, R)$$ とします)、番号インデックスの区間 $$[L, R)$$ について、その区間に含まれる関数のみを考慮して計算する、ということをやって値を合計すれば良いです (Segment Tree と同じような発想で区間を区切ってやります)。

備忘録なので説明が雑ですみません。もし質問があれば聞いてください。

HCPC のホームページを移行した話

この記事は Competitive Programming (1) Advent Calendar 2019 の 12 日目の記事として書かれました。

2019 年 11 月に、北海道大学競技プログラミングサークルのホームページを FC2 から GitHub Pages へと移行しました。移行していろいろと便利になりましたので、今後競技プログラミングサークルでホームページを作ることを検討している方への参考になればと思い、記事を書くことにしました。

TL; DR

GitHub を使って、資料管理・ホームページ作成をするやり方を説明します。資料管理用・ホームページ用リポジトリをそれぞれ作り、GitHub Pages + Jekyll (+ CI) でページをビルドします。

ホームページのコンテンツ

弊サークルのホームページの主なコンテンツは以下が挙げられ、これらを便利に見れるようにすることを重視してホームページを構成しました。

  • ICPC 参加報告
  • スライド
    • 弊サークルでは「勉強会」という、予め決定されたテーマについてスライドを通じて勉強する活動があります。今まで作られたスライドがどこかにまとまっていれば、新しくサークルに興味を持ってくれた方にも勧めやすいですし、勉強もしやすいです。
    • 大学サークル主催の競技プログラミング合宿で出した問題やその解説についても、どこかにまとめる必要があります。
  • 連絡先

従来のホームページの構成、その問題点

従来の構成は以下のようになっていました。

ですが、この構成にはいくつか問題点があります。

  • ホームページを三ヶ月以上更新しないと広告がつく
    • これは FC2 のホームページ側が課している制約です。無料だし仕方ないですが、できればこの制約はなくしたいところです。
  • SlideShare でスライドをアップロードしても日本語が見れない
    • フォントが埋め込みされていない、などが理由の場合もあります。
    • しかしながらフォントを埋め込んでいるのに見れない場合もあります。こういった場合はなぜかフルスクリーンにすると大体は見れるのですが、わざわざフルスクリーンにするのは不便です。
  • SlideShare でスライドを差し替えられない
    • SlideShare にはスライドを編集して再アップロードする機能はありません。いったんスライドを削除して全く同じものをアップロードしても、スライドへの URL は今までとは異なるものになってしまいます。
    • スライドの中身を変更した場合、URL の変更を何らかの形で周知しなければならないことを考えるとこれも非常に不便な点です。

これらの問題を解消するために、以下で説明する構成に変更しました。

移行後のホームページの構成

GitHub Pages では広告が付きません。また、今時 PDF が見れないブラウザを使用する人はそうそういないだろう・・・ということで、資料はリポジトリに直接入れて Web 上で見れるようにしました。ファイルを編集して再アップロードする機能は当然 GitHub に備わっていますので、日本語が見れない問題や再アップロードができない問題は解消されました。

それでは、実際にこの構成でホームページを作成してみましょう。資料管理・ホームページ作成について、どう設定すればよいかを以下で詳しく説明します。

資料管理について

資料管理用に、archive というリポジトリを作ったとします。

まず、master ブランチに各種資料を push します。次に、GitHub Pages を有効にするために以下を設定します。

  • リポジトリのページに飛び、「Settings」タブを押す
  • 「Settings」の中に「GitHub Pages」という項目があるので、Source を「master branch」に設定

f:id:tsutaj:20191207204800p:plain
生成元ブランチ選択画面

これで、資料が Web 上から参照できるようになります。

GitHub Pages について

ここに書くと記事が非常に長くなるので、別途リポジトリ tsutaj/pages-example を用意しました。Jekyll や CI について簡単に知ることができる構成にしたつもりです。

上に示したものを fork するかリンク先のコンテンツを含んだリポジトリを自分で作成するかして、説明を読んだり、ビルドしたものがどのように見えるか試してみたりしてください。

サンプルはこちらにあります: tsutaj.github.io/pages-example/

f:id:tsutaj:20191207205024p:plain
用意した pages-example リポジトリ

まとめ

GitHub Pages + Jekyll は少しの設定で便利にホームページを構成できます。また、CI と組み合わせることで Jekyll への機能追加にも柔軟に対応できます。

この記事に関して質問がありましたら tsutaj までご連絡ください。

宣伝?

現在、kimiyuki さんと beet さんと自分で kmyk/online-judge-verify-helper を開発中です。これは CI と連携して C++ のライブラリリポジトリを自動で verify し、その結果を GitHub Pages で可視化するというものです。まだ現在進行中で開発をしているところですが、よろしければぜひお試しください。

f:id:tsutaj:20191211235923p:plain

ICPC の現役を引退した

今年の ICPC アジアの大会参加記 にも書いたとおり、今回をもって ICPC の現役を引退しました。それと同時に、北海道大学競技プログラミングサークルの運営 (部長的立場なんですが、役職という概念が存在しないため適切な用語がない) も退くことになりました。

完全にポエムなんですが、ここまでの一年間で自分がやったことを雑にまとめました。

普段の活動をとりまとめた

弊サークルは週 2 回活動しておりますが、活動があるごとにいつ・どんな活動を行うか (例えば「今日は練習会を AOJ でやります」とか) を他のメンバーに共有する必要があります。今まではそれをメーリングリストで行っていたのですが、サークル外から気まぐれに殴り込みにいきたい (?) 需要などもあるようで、Twitter で共有する方式に変更しました。

とりまとめたといっても大したことはやっておらず、バチャを建てたりスライドを作ってもらったりという感じでした。なんだかんだバチャは (普段の活動だけで) 年 40 回弱建てることになるので、すでに使った問題を避けるとかは当然必要ですが、そのへんは勘でやってました (は?)

合宿 (RUPC, ACPC) に問題セットを提供した

これは結構大変でした (それはそう)

作問担当になっている大学どうしで連絡をとりあったり、提供する問題セットの Writer / Tester / 最終確認 などなどをしました。特に最終確認は骨の折れる作業ですが、しないと問題セットがボロボロのまま出題する羽目になってしまうので、そうならないようにかなり気を遣った気がします。

RUPC のためにまた問題つくらないとなあ

HUPC を開催した

なんか開きたくなってしまって結局本当に開催しました。具体的に何をしたのかについて、詳しくは HUPC 参加記の記事 をご覧ください。

JAG 夏合宿に問題セットを提供した

HUPC Day2 の Writer 陣が優秀すぎて問題が余りまくったので、not さんからの提案もあり夏合宿で出させていただくことになりました。ACPC の作問と並行してやっていたので正直余裕がなく、自分は簡単枠を作るのと担当の部分をこなすのと体裁チェックくらいしかできなかったので他のスタッフには頭が上がりませんね・・・

ホームページを改修した

フリーサーバーで動いているゆえにホームページを長期間放置すると広告が付いたり、SlideShare の調子が悪すぎたり、などなど状況として良くなかったので改修しました。

GitHub Pages + Jekyll + Travis CI という連携で動いています (アドベントカレンダーでこの辺の話をまとめる予定です)

ICPC アジア地区大会に行った

やはり ICPC の国内予選を今年も通過できたのは良かったです。それに今年も 2 チーム出れたし。

2 チームで出るとなると 7〜8 人で一緒に遠征するということになるのですが、宿泊する場所をまとめたりしてわいわいやっていました。楽しかったです。

所感

振り返ってみるとかなり色々やった気がします。個人的には、今後も ICPC 国内予選通過が安定してできるようになってほしいなあという思いがあったので、特に練習会の難易度設定はかなりこだわっていましたし、結果的に実力の底上げは達成できつつあってよかったなあという感じです。また、弊サークルは作問機会に非常に恵まれていて、そこでも得られたものがたくさん (作問ノウハウとかマネジメントとか) あったなあと思います。

約 1 年間運営できてしあわせでした。ありがとうございました。来年度以降も活動楽しんでね。