Xmas Contest 2016

Xmas Contest 2016 にご参加いただいた皆様、ありがとうございました&お疲れ様でした。

難易度が高すぎて順位表が大変なことになっていましたね。。
1問をじっくり考えるのに慣れていない方には少しつらいセットだったかもしれないです。
でも、なんだかんだ出来ることはあって座るだけにはならなかった方が多く、その点は良かったかなぁと思っています。

それでは解説を...のつもりだったのですが、解説をガッツリ書く体力が残っていないため、ヒントだけで失礼いたします。

*追記:解説情報です。 ABCFHI

ヒント

A (原案:snuke)
N=15のとき、8,4,2,1と取っていくと4回ですが、a=[0,8),b=[7,15),c=[7,8)とすると3回の質問で総和(a+b-c)が求められる。
このように引き算を駆使すると、二進数での桁数/2回くらいの質問で総和が求められる。
ちなみに10回必要になる最小のNは二進数で11010101010101011です。
B (原案:snuke)
50点を超える最も簡単な解法は、スターンブロッコット木を、分母をx分子をyとしてそのまま埋め込む解法だと思います。
70~90点はフラクタルっぽい図形を頑張って構成すれば良いです。
満点は64*64に収めなければなりません。余白は1点しか許されません。
これは図を使って説明しないと行けないので後で。
C (原案:japlj)
二分探索すると01列を切ったり捨てたりして1を残したら勝ちというゲームになります。
0,1のかわりに-1,1で考えます。
累積和をとります。
全体の累積和が0でない場合、正なら勝ち、負なら負けです。
0の場合は、累積和が0となっているような切れ目の個数が奇数個なら勝ちです。(先に切る番の場合)
戦略は上記の結果を証明しようとすると自然と導かれます。
D (原案:japlj)
簡単枠のはずでした(自明ではないですが)が昼の部ではなかなか解かれませんでした。
各サイクルに注目すると、
サイズが2なら1回でいい。
サイズが3以上なら2回必要になる。
サイクルに出てくる数たちを列としてみると、全体をreverseするのと1狭い区間をreverseするのをやると1shiftが作れます。
例えば234561→[165432]→1[23456]という感じです。reverseは複数のswapを並列に行うだけで実現できますね。
E (原案:japlj)
まずはクラスタリングしましょう。
クラスタリングは超高精度でできます。
各人に対して、その人と同じ選択肢が選ばれている回数を求めて、その順でソートして10,10,10と区切ってやればいいです。
あとは各問題について最尤値推定をすればいいです。(2/3の人で多数決をするだけでも通ります)
F (原案:snuke)
見掛け倒しです。
実は操作は対称性が高く、K次回文はreverseしてもK次回文になります。
mod2で答えればいいので、もともと回文であるようなK次回文の個数さえ求めれば良いことになります。
K=0のときは回文の個数を求めればいいです。
K>=2のときは追加、置換*K-2、削除とすればもとの文字列に戻すことが出来るので、これも回文の個数を求めればいいだけです。
K=1のときは「もとが回文」かつ「1長いものまたは1短いものも回文」でなければならず、どの文字とどの文字が同じでなければならないかを考えると、すべての文字が同じ文字列しか条件を満たさないということがわかります。
G (原案:snuke)
最大流に落としましょう。
そのグラフは平面グラフになっているので、最小カットを最短路で求めることができます。
有向グラフの場合は逆辺としてコスト0の辺を張らないといけない点に注意。
H (原案:snuke)
二分探索した後、結構シンプルな貪欲法で解けます。証明が面白いです。
証明は後で。
I (原案:snuke)
いろんな塗り分け方をして偶奇性を見ると各テトロミノ特有の性質というのが検出できます。
後で。
J (原案:japlj)
条件を満たすように数列を作ってくださいとしか解説のしようがあまりない気がする。
(1)はなんと、全部満たせます!
(2)は後のことをあまり考えずに貪欲に置ける数の中で最も大きいものを置いていくだけでいいです。変態的なパズルです。

open all / close all


generated by indenter

ACC2016 24日目「色塗り2」解説

Advent Calendar Contest 2016 24日目の問題「色塗り2」を出題させていただいたので、その解説
問題はこちら。

解説
まずは「葉が b 個根に付いた根付き木の頂点を c 色で塗り分ける場合の数」を考えてみます。
コラム
根付き木の同型性に関して扱うときの常套テクとして、各子に何らかの順序をつけてソートすることによって標準化をします。
つまり、「葉に塗る色の番号は左から見たときに昇順になっていなければならない」というルールを付けて数え上げることにすると良いです。
そうすることで、重複無く数え上げることができます。
立式をしてみましょう。
よく見るとまんま重複組み合わせですね。
 {}_c H_b*c = {}_{c+b-1} C_b*c
 _c H_b は葉の塗り分け方、 *c は根の塗り方。
元の問題に戻って考えてみます。
「葉が b 個根に付いた根付き木の頂点を c 色で塗り分ける場合の数」を d とします。
すると、元の問題の場合の数は「葉が a 個根に付いた根付き木の葉を d 色、根を c 色で塗り分ける場合の数」と同じです。
式にするとこうなります。
 {}_d H_a*c = {}_{d+a-1} C_a*c
dを展開した式はこうなります。
 {}_{({}_c H_b*c)} H_a*c
式の計算方法を考えます。
 {}_{({}_c H_b*c)} H_a*c の偶奇を求めたいのですが、何も考えずにmod 2で計算してしまうとおかしなことになります。
例えば、 {}_5 C_4 \equiv 0 \ne 1 \equiv {}_1 C_0 という具合です。
さてここで、 {}_x C_y\ mod\ 2 の性質について思いを馳せます。
結論から言うと、 x\&y = y なら 0、そうでないなら 1 です。
パスカルの三角形の偶奇を眺めてみたりすると分かるかもしれません。
ここで重要なのが、y を超えるような2冪数を T としたとき、 x\&y = (x\%T)\&y であることです。
つまり、x の正確な値が分かっていなくても、 x\ mod\ T の値さえ分かっていれば  {}_x C_y\ mod\ 2 が計算できます。
 a \lt 2^{20} なので、 {}_c H_b*c\ mod\ 2^{20} が求められれば良いことになりました。
あとは剰余演算に慣れた人ならそれほど難しくありません。
剰余演算パート
 {}_c H_b*c\ mod\ 2^{20} の求め方を考えます。
 {}_c H_b = {}_(c+b-1) C_b = (c+b-1)!/b!/(c-1)! なので、階乗どうしの割り算が出来れば良いです。
階乗は前計算しておけばいいのですが、そのまま計算すると割り算で詰むので、工夫が必要です。
値を「奇数*(2冪)」という形に分解し、「奇数」と「指数の肩」の組  (O,E) を計算しておきます。
すると  x/y = O_x/O_y*2^{E_x-E_y} という形で計算ができます。
残る問題は奇数での割り算ですが、一般にmodの値と互いに素な数には逆元が存在するため割り算が可能です。
xのmod mでの逆元は  x^{\phi(m)-1} と計算できます。
 \phi(m)オイラー関数(mと互いに素なm以下の整数の個数)で、 \phi(2^{20}) = 2^{19} です。
詳しくは蟻本を読むと良いでしょう。更に詳しくは群論とかの本を読むといいかも。
おまけ
元ネタ
KUPC2016のI問題「色塗り」で、本番でそのままmodで計算していってもいいのか考えて、mod 2だとダメだよなぁと思ったのがこの問題を作ったきっかけです。
mod 10億7だとコンビネーションの分母がmodと互いに素になるのでOKっぽい。
発展課題
この問題ではmod 2までで諦めてしまいましたが、 {}_x C_y\ mod\ 2^z を高速で計算できたりしませんかね?→sigma氏からnCm mod 素べきの計算法の論文を教えてもらいました

open all / close all

generated by indenter

IOIへの出題について - 解説編


部分点1
部分点制約:N ≦ 8
並び替えを全部試せばいいです。
部分点2
部分点制約:N ≦ 16
巡回セールスマン問題に落としてbitDPでできます。
部分点3
部分点制約:答えが 0 かどうかだけを判定すれば良い
これが想定通りに解ければ満点はすぐそこです。
ただ、よく分からずに貪欲を頑張って考えるとこの部分点までは取れたりするようです。

まず、(A,B) = (INF,1) のトンネルを新たに作り、トンネルをループ状に繋げられるようにする問題だと考えたほうが少し考えやすくなります。
INFはmax(A_i)で十分です。

各トンネルは「体が A_i 以下なら入れる」ではなく、「ちょうど A_i なら入れる」+「好きなタイミングで何回でも体を 1 大きくすることができる」と考えたほうが考えやすくなります。
A_i, B_i を数直線上にプロットし、A_i→B_iの有向辺を張ります。
このとき、以下のようなサイクルが存在すれば答えは 0 となります。
- トンネルの辺をちょうど1回ずつ通る(下図の赤辺)
- 数直線を右に進むのは自由(下図の緑辺)

f:id:snuke:20161202204003p:plain

例えば、1-緑->2-緑->3-赤->1-緑->2-赤->5-緑->6-赤->8-赤->1 というサイクルがあるので、このケースの答えは 0 です。

トンネルを頂点ではなく辺にしたことにより、ちょっとオイラー路っぽい問題になりました。
しかし、緑辺を通る回数がよく分からないのでまだオイラー路問題ではないです。

さて、各緑辺を通る回数は自由なのですが、実は一意に定まります。
各頂点に、赤辺の「入次数ー出次数」を書き込み、左から累積和を取れば、各緑辺を通るべき回数が求まります。
緑辺を通るべき回数が負になった場合はその時点で答えは 0 ではないと言えます。

f:id:snuke:20161202204256p:plain

これで完全に(有向)オイラー路問題に帰着できました。
あとはオイラー路の条件「入次数=出次数」と「連結である」をチェックすれば良くなりました。
次数条件は緑辺を通る回数を求めた時点で自動的に満たされているので、連結性のみを判定すれば良いです。
連結性条件は無向グラフだと思って判定しても大丈夫なので、適当にやればOKです。

あらかじめ座標圧縮をしておかなければならない点だけ注意して下さい。
満点
スモールライトについて考えなければなりません。
スモールライトは下図の青辺のような、数直線を左に進む辺に対応します。

f:id:snuke:20161202210048p:plain

この問題は、青辺を追加する本数を最小化する問題ということになります。

青辺が必要になる状況は以下の2通り考えられます。
- 「緑辺を使う回数」が負になる箇所を相殺する
- 青辺と緑辺をセットで追加して2つの連結成分をつなげる

まずは負の箇所の相殺をします。このとき、相殺した箇所は連結になる点に注意して下さい。
次に、全体を連結にすることを考えます。
連結成分の形は下図のように結構複雑な形になることがあるので単純には行きません。

f:id:snuke:20161203093707p:plain

数直線上で隣接する頂点の間に青辺(+逆向きの緑辺)を張ることにより、それらを連結に出来ます。

さてここで、連結性判定時には辺を無向だと思って良いことを思い出すと、以下のように辺を張ったグラフのMSTを求めればいいことになります。
- 赤辺と緑辺と負を相殺するための青辺(コスト=0)
- 数直線上で隣接する頂点間を結ぶ青辺(コスト=距離)

これで解けました。
まとめ
ハミルトン路がオイラー路になり、MSTになりました。

open all / close all


generated by indenter

IOIへの出題について

※この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの2日目の記事です。
IOIにあまり興味が無い方は、下の方の僕が出題した問題の方だけをお読み下さい。

IOIとは

IOIとは"International Olympiad in Informatics"の略で、日本語で言うと「国際情報オリンピック」のことです。

IOIの大会としての特徴は以下のとおりです。

  • 高校生以下が対象の世界大会
  • 1989年から開催されており、2016年に第28回が行われた
  • 各国で国内選抜があり、日本はJOIが選抜を行っている
  • 日本から選手団が派遣されたのは1994~1996と2005~現在
  • 2018年に日本(つくば)で開催予定

競プロのコンテストとしての特徴は以下のとおりです。

  • 5時間で3問程度のコンテストが2回開催され、その合計得点で順位が決まる
  • 誤答/時間のペナルティはなく、そのかわり大量の部分点が存在する
  • マラソン的な問題や、リアクティブなどの変わった形式の問題も出題される
  • 最近は完全フィードバック(ジャッジ結果がすぐに分かる)
  • 選手はコンテスト中に順位表を見ることが出来ない

IOIへの問題の応募

毎年、その年の公式サイトに「Call for tasks」という形で問題募集の情報が公開されます。
今年のものはここです。
近年は問題の集まりがあまり良くないらしく、毎年応募期限が延長されています。
今年の期限は12/15に延びたので、まだ間に合いますよ!

IOIは時間ペナルティなどのないコンテストなので、部分点が多い問題が求められています。
簡単枠ならその限りではないかもしれません。
また、5時間3問なので、実装は重くてもOKです。
ただし、シラバスの範囲内からしか出題できないので注意してください。
IOIで求められている問題の傾向は以下のとおりです。(多分)

  • 意味のある部分点の多い難しい問題
  • 部分点はそれほど多くないが、面白い問題
  • 変わった形式の面白い問題(ここ2年は出題されていない)
  • 簡単枠の面白い問題(恐らく競争率が高い)
  • 汎用的でかつ珍しめのテクニックを使う問題は好まれる傾向にありそう

応募する際に送る必要のある情報は以下のとおりです。
問題に自信があれば、なるべく親切にいろいろなファイルを作っておくと採用率が上がって良いのではないかと思います。

  • 問題文(英語)
    • 運営がストーリーを変えたりすることもあったりするので、原案を伝える程度のもので大丈夫だと思います。
    • 過去問が公式サイトで公開されているので、構成はそれを参考にすると印象が良くなるかもしれません。
    • 自分はmarkdownファイルとそれをpdfにしたものを用意しました。(txtでもなんでも良いと思います。)
  • 解説
    • 部分点を含めた解法を書いた文書を用意する
  • 解答ソースコード
    • IOIの形式は少し特殊なので、過去問のデータを取ってきてそれに合わせて書くと良いでしょう。
  • テストデータ
    • 必須ではありませんが、あるとかなり印象が良くなると思うので用意することを推奨します。
    • ジェネレータも置いておくとなお良いと思います。
  • プロフィール
    • 作問者が何者なのかを書きます。協力者がいる場合はその人も。
    • 連絡先、氏名、所属、国籍、情報オリンピックにおける立場(選手のトレーナー/委員会の役員/無関係等)を書きました。
  • readme
    • フォルダ構成を書いておくと親切だと思います。

もし実際に応募する場合は公式サイトを読んでもらうのが良いと思います。
応募を真剣に検討している方は、僕に声をかけてもらえれば、参考として僕が送ったファイル類を渡します。

IOIに問題が採用された時の流れ

2015にも1問送ったのですが、落ちました。落ちた場合は何も連絡は来ないので少しさびしかったです。

去年秋のある日大学に向かうバスで思いついた問題が自信作で、部分点もある程度つけられそうだったのでIOIに送ってみることにしました。
この年のCall for tasksの期限は年始すぐくらいで、帰省中にも作業してたような記憶があります。
1/11に提出し、しばらく経っても音沙汰がなかったので少し落胆していると、5/31に採用通知が来てめちゃくちゃ嬉しかったです。

問題が採用されると、shortlistという9問くらい(?)の問題候補の中に入ります。
実際に使われるのはこのうちの6問くらいで、残りは予備・来年に繰り越しになります。

問題が採用されてshortlistに載ると、IOIに招待され、IOIにguestとして参加することが出来ます。
もちろん、断ることも出来ます。
現地では特に仕事がないので、日本選手団と行動するなり、guest用の観光に行くなり、自由にしていればいいです。
ただし、問題が実際に使われて公開されるまではあらゆる情報が秘密なので注意が必要です。
現地に行く場合は、現地についてから「え、なんでいるんですか?おっ、writerか〜?」となるのは仕方ないので問題なしです。

IOI 2016に採用された問題

Code Festivalの本戦の問題を作ろうと、風船釣りを元ネタとした問題を作ろうとしていたときに原型が出来ました。
結局これは風船が全く関係ない問題になり、その後風船ツリーが出来ました。
その後、少し問題設定をいじると、自作問題の中でも 1, 2 を争うくらい好きな問題になりました。

さて、送った問題ですが、ドラえもんガリバートンネル(とスモールライト)を知っていると理解しやすいと思います。

問題

ガリバートンネルが N 個あります。
トンネル i の入口のサイズは A_i、出口のサイズは B_i です。
snuke君はこれらのトンネルを1列に並べ、順番に通り抜けていこうとしています。

トンネルの入口に入るには、体のサイズが A_i より小さくなくてはなりません。
トンネルの出口から出てくると体のサイズはちょうど B_i になります。

snuke君の体のサイズは最初 1 です。
snuke君はスモールライトを持っていて、これを 1 秒使うと体のサイズを 1 減らせます。

トンネルの並べる順番を工夫したときの、スモールライトを使う必要のある秒数の最小値を求めて下さい。

実際に出題されたときは、ジェットコースターの侵入速度制限付きのレールユニットを組み合わせる設定になりました。

制約

  • 2 ≦ N ≦ 200,000
  • 1 ≦ A_i,B_i ≦ 10^9

入力例

4
1 7
4 3
5 8
6 6

(1,7) (6,6) (4,3) (5,8) の順で並べれば、1個目→2個目で1秒、2個目→3個目で2秒使えば良くて3秒で済み、これが最小なので答えは3。
体のサイズは、1-tunnel->7-light->6-tunnel->6-light->4-tunnel->3-tunnel->8 という感じで変化していくことになります。

部分点

1. (11点): 2≦n≦8.
2. (23点): 2≦n≦16.
3. (30 点): 答えが 0 かどうかだけ判定すれば良い
4. (36点): 満点

解説は別記事で紹介します。
また、ここのday1の2問目でonline judgeが利用できます。

IOIの大会中のコンテスト以外のイベント

1. 到着日
2. register、開会式
3. コンテスト1
4. エクスカーション1
5. コンテスト2
6. エクスカーション2
7. 閉会式
8. 出発日

というスケジュールです。
1週間と長いですが、あっという間です。

毎年、JOIから問題文の翻訳等をするための随行員が派遣され、各コンテスト日の前日夜に問題文の翻訳をします。
あと、大会期間中何度か開催される全体会議にも出席したりします。
僕はIOI 2015の随行員で、カザフスタンに行っていました。
そして今年はguestであって随行員ではなかったのですが、暇なので翻訳のお手伝いをしました。

大会期間中撮りためた写真をtumblrにまとめたので、IOIの様子が気になる方や、わふれるかが見たい方はどうぞ。
JOIの写真速報もあります。

IOI後

IOI2016の優勝者jcvb氏と帰りの空港で会ったので少し話しました。
結構前なので記憶が曖昧ですが、名前の由来についての話題をきっかけにして話しかけた気がします。
"jc"は本名のイニシャルで、それだと短すぎてIDが取れなかったので適当に2文字つけたと言っていたと思います。
出題の件に関しては「ロシア人が作ったのかなと思っていたが、コーチから日本人が作ったらしいという話を聞いた」みたいなことと、問題に関する良好なフィードバックがもらえて嬉しかった憶えがあります。

その数ヶ月後、CodeFestival 2016でksun氏に「are you snuke?本戦のwriterだよね、reverseの問題良かったよ。」的な感じで話しかけられました。
ksun氏はIOI2016にもカナダ代表で来ていたのでIOIの話題を振って「IOIの問題も書いたよ。」「ま?あの問題面白かった。本番中は解けなかったけど後で解いたよ。」的な話ができて嬉しかった。

IOIへの出題は、こんな風にIOI後に海外勢と話すときに話題に出せるという特典もありますよ。

まとめ

今後のIOIの開催国は、イラン、日本、アゼルバイジャンシンガポールです。
IOIは世界最大級の規模の大会に招待される絶好の機会です。
実は問題が不足気味で穴場だったりするのでチャンスかもしれません。
IOIに問題を送って普段行かないような国への旅行を楽しんでしまいましょう。
あるいは、IOI2018に良問を送りまくってTsukuba大会を最高のコンテストにしましょう。

Advent Calendar、明日はehaさんの「hackerrankがくれたビットコインの使い道について」とyurahunaさんの「競プロを初めて1年になるので振り返ります」です。

ICPC Tsukuba 2016 参加記

慶應義塾大学のチーム「Running」として参加し、3位の銅メダルでした。
メダルを取ることが出来たのは初めてで、とても嬉しいです。

時系列順で感想を羅列していきます。

コンテスト前日

つくばエクスプレスの車内で合流して、つくばのリンガーハットでご飯を食べた。

プラクティスでは、キーボードの癖の把握とスタックサイズの調査をすることにしていました。
キーボードは重めでびっくりしましたが、打ちやすくとても良かったです。
いつもはMacで⌘→で行末に移動しているので、Endキーを押さないと行末に移動できない環境には少し戸惑いましたがそんなに大きな影響はなかったです。
時間はあと15~30分ほど長いと嬉しいなと感じました。
会場の配線は、人が通る場所に線が、去年より心なしか少なかった気がする?

懇親会は帰りのバスを待つ時間が長くて、寒かったのもあってつらかったです。

ホテルについたら真っ先に大浴場に入った。
それから、peryaudoと近くのショッピングセンター的なところで買い物をした。
レジが半自動ですごかった。
ホテルに帰るときにライトアップされた変な建物を見つけた。
だいたいこういうのってラブホテルとかいうやつなんですが、それにしては大きいなぁと思って調べてみると、近くに保育園があって、教会系の結婚式場なのではという結論になった。納得した。

夜は結局寝れなかった・・・
結構眠気が強かったので寝れそうだと思っていたんですが、2時間ほど浅い睡眠をしたあとに廊下の声とかで起きてしまって、そこからは絶望の時間が始まりました。
なんか今年も1時くらいに暴走族がいたんですが、これIOIやったときにもいたら日本の印象的な意味でアレそう。
結局1~2時間くらいしか寝れなかった。

コンテスト当日

わりと眠かったですが、プリン食べてユンケル飲んで乗り切りました。(去年もそうした)
入場する前にタイピングソフトをやってみたところ、そこまで悪くない速度だったので少しだけ安心しました。
(これが遅かったら脳の回転速度が相当低下しているということで、やばかった)

コンテスト中の動向

うちの体制は、A,B をperyaudoに投げて、その間に先の問題を読んだり解法を考えたりしておくという感じです。
その後は2人に問題を読んでもらって、ライブラリ写してもらったりサンプル図示してもらったり手計算を投げたりとかする感じです。

A

開始直後peryaudoに投げたら一発で通してくれた。

D

Cが簡単だったのでperyaudoに投げてみて、Dからやった。
1回WAを出して直して投げたら、map<vector<int>,int>のせいでTLEしてしまった。

C

ジャッジ待ちの間にperyaudoに聞くと少し自信がなさそうだったので、自分でやることにした。
出力を改行区切りにしてしまって1WA食らった(だめやん)

D2

ハッシュに書き直して投げたけどWA。もうちょっとちゃんとハッシュを組まないといけなかったっぽい。

B

Cやってる間にperyaudoに読んでもらっていたので、やってもらった。1発ACいいぞー。
罠があったっぽいですが、少しのデバッグで乗り切ってたのはさすがっすね。
コーディングしてもらってる間に問題文を聞いたりした。

D3

vector<pair<vector<int>,int>>をsortすることにしたら通った。
TLEでハマるのはかなり泥沼なので、この程度のロスで済んだのはよかった。
ただ、ペナルティを結構食らったので、以降はペナルティをあまり意識しない方針にした。

G

E,Fがパッと見では分からず、順位表見たらGが解かれていたのでGに行く。
はじめsetを書こうとしたけど使わなかった。
細かいバグを何回か埋め込んで、3WA食らった。

E

Iが見た目簡単そうに見えたけど、WAしてるチームがあったしやめといた。
(そのとき考えてた方針は結局計算ミスしてて全然ダメだった)
次にやるものがないなーと思っていたけど、Eは同じ記号を違う文字に割り当てられないのに気づいて、それならただの実装問題やんとなり、これをやることにした。
再帰下降構文解析は頭を使わずに書くだけでいいので楽ですね。
末尾に'$'とかをつけておくと配列外参照とかを防げて楽でした。
イテレータを正しくインクリメントするのだけは気をつけないといけないけど)
文法が正しいかまで含めて式を評価しないといけない問題だったので少し不安だったけど、1発で通ってびっくりした。

F

Jが解かれていたけど幾何だし、通してた中国チームはなにか類題を見たことがあったっぽい雰囲気を感じたのでやめた。
とりあえずFに取り組んだ。
問題設定がなかなか独特で、どうアプローチすればいいのかに悩んだ。
2-SATっぽい雰囲気のある設定だったけど、全然そんな形にはできなさそうだった。
mineとサンプルの具体例を構成してみた。
sample3がなぜYesなのかを考えていると、大体の条件はfalseにして置けばOKなことに気づいたので、その方向で考えていくと解法がわかった。
計算量は適当でも間に合いそうだなーと思っていましたが、BFSで次の辺を見つけるパートを合計O(N^3)でやらないといけないことに気づき、少し考えたけど、すぐ分かって良かった。


あとで聞いた話だと、64bit高速化とかで乗り切ったチームとかもいたっぽいですね。
解法の証明は甘々にしかしてなかったので怖かったですが、1発で通ってびっくりした。

この問題不思議な問題で、なんかプロコン慣れしてる人ほど苦しんでたんじゃないかと思います。
解法自体のユニーク性、O(N^3)に落とすパート、面白い問題だと思いました。
少し感動して気持ちが上がった。

この時点では2位だっけ。

H

とりあえずIの両辺が10^9の正方形のケースでの解答の構成をチームメイトに依頼して、Hを考えた。

なかなか一筋縄ではいかないなぁと思った。
とりあえず、無限判定について考えてみると、無向辺で繋がってる頂点を縮約してやるといい感じになることに気づいた。
無向辺だけ見たときにサイクルがあればダメで木になるので、木を頂点としたDAGで最長経路を求められれば良さそうとなる。
木の最長経路パートは、

「木に分解」「DAGを作る」「DFSする」「DFS内でダブルスイープ」とやることを分かりやすいパートに分割出来て、あまり頭を使わずに実装できるので量は多めだけど楽な実装だった。
それでも量は多い実装なので、1発で通ってびっくりした。

「木を頂点としたDAGにすればいい!」って気づいたときは感動しました。

また、グラフを変換する方針があるらしいです。


面白い方針だと思ったのですが、少し実装の見通しが悪くバグのリスクが高いこともあり、僕なら木に分解する方針を選びます。
一般に「自分の書き慣れた形」を組み合わせてコードを書いていくとバグを出しにくくなる気がしています。

I

Hやってる間にmineが一辺10^9の正方形の構成を思いついてくれて、それを長方形に拡張したときに何が問題になるかとかの部分まで考えてくれていて、それを聞いたら解法を思いついた。
制約からルートで分割しそうなオーラは感じていたんですが、どういう分割をするのかは思いついてませんでしたが、チームメイトと議論してるうちに正しい解法へとたどり着けました。チーム感を感じたり、そもそも解法が面白くて感動したりで、気持ちが上がった。
extgcdあんまり使い慣れてなかったので不安でしたが、1発で通ってびっくりした。

この時点では4位と2完差の3位だったし、9完が出てもペナルティで勝てそうだったので3位を確信して少し肩の荷が降りました。

K

上にも下にも差があったので解いてもあまり変わらなさそうでしたが、1時間弱あったしやりました。
気が抜けたこともあり、睡眠不足が効いてきて意識朦朧としてました。
peryaudoと話してたら和んだ。

結局解けず終了。

      • -

とりあえず解けなかった問題に関しても感想を書きます。

J

三角形と円の共通部分面積のライブラリは持っていたのですが、探索方法が思いつきませんでした。
解説でいろいろアルゴリズムが紹介されていてすごかった。
きゅうりに教えてもらった解法を上げておきます。

x軸方向とy軸方向で独立に3分探索をします。
というのも、多角形が凸多角形なため、x軸方向だけで中心を動かすと凸関数になっています。y軸方向もしかりです。
なので、x軸で3分探索をして、その評価関数内でy軸方向の3分探索をすれば良いです。

補足:まず、例えば長方形のときとか凸関数ではない。(ただ値が変化しない区間は必ず最大値を取るということは証明できるかもしれない)
あと、面積が0になる区間はうまく避けないと三分探索が機能しないので注意しないといけない。

K

唯一不満を持った問題です。理由は思いつきようがないようなマイナーな知識を要求するだけの問題だからです。(申し訳程度の半分全列挙はありますが。)
いや「こんな知識を知ってるなんて、よく勉強してるなぁ」という風に、一応一理はあると思うんですが、デメリットの方が多いと思います。
あまりマイナーな知識を要求されると大会に対する対策のしようがなくなり、モチベーションが下がります。
また、ICPCはネット検索などもできず論文を検索したり出来るような大会ではないので、「出典:〇〇」のような問題は少し場違いに感じます。
参加者のフィードバックとして参考にしていただけると幸いに思います。

ただ、この知識自体はとても興味深いものです。
もしブログなどで出会ったとすれば素直に感動したりしそうです。
出典の本に関しても関心が高く、ぜひ読んでみたいと思います。

コンテスト後

体調最悪で、解説まではだいたい寝てました。
PFN勢がたくさん来ててすごかった。
解説は結構じっくりやってました。
順位表解凍はネイティブな感じでいい感じでした。
終了時の予想通り、前述の通り3位でした。
ただ、1位が全完していたのは予想外でした。SJTUさすがだなぁ。
3位はつくば賞とPFN賞をもらえました。

まとめ

日本のICPCは本当に上質なコンテストで、今年も本当に良い大会でした。
去年の参加記にも書いたことと少し被りますが、他のアジア地区よりも、クオリティが高いと思っています。
会場設営、スケージュール、コンテンツ、問題セット、運営・進行、スポンサー、放送、などなど、全てにおいてコンテストに関わる人の熱意がすごく感じられ、参加している私自身とても幸せな気持ちになりました。本当にありがとうございました。

他にも書きたいことはありますが、とりあえずまずは11/6あたりのジャカルタ大会頑張ります。

最小流量制限付き最大流

SRMで最小流量制限付き最大流が出ました。(SRM694Div1 Hard)
とりあえず自分がやった方法をメモしておきます。

まず、下図のようなグラフのs→tの最大流が求めたいとする。
f:id:snuke:20160710041224j:plain
以下のように変換する。(蟻本に載ってる図と同様)
f:id:snuke:20160710041307j:plain
超頂点S,Tを作り、u→vにL以上R以下の辺があるとき「u→vにR-L(黒)」「u→TにL(青)」「S→vにL(青)」の辺を張る。
「S→sに∞(緑)」「t→Tに∞(赤)」の辺も張る。
この変換により、最小流量制限を外す準備は整った。
しかし、このまま流すと青の辺に十分な量が流れない可能性がある。
そこで、以下の手順でフローを流す。
1. 緑と赤の容量を0にして流す
2. 緑の容量を∞、赤の容量を0にして流す
3. 緑の容量を0、赤の容量を∞にして流す
4. 緑と赤の容量を∞にして流す
このように流すことによって、青の辺を優先的に使うフローが求まる。
こう流したあとの残余グラフで青の辺に容量が残っていたら条件を満たすフローが存在しない。
(追記:コメントで教えてもらったのですが、緑と赤を張らずに、S→T・s→T・S→t・s→tの順に流せばもっと楽ですね。)

また、上記と同じようなことが最小費用流でも実現できる。
緑と赤の辺だけのコストを1にして残りを0にすればいい。
実行速度は遅くなるが、実装は楽そうだ。


フローまだまだ知らないことがあるなぁ・・・とりあえず、最小費用循環流の解き方が知りたい。

Mo's algorithm とその上位互換の話

最近 Mo's Algorithm - Codeforces をよく目にする気がします。
興味深いアルゴリズムではありますが、より良いアルゴリズムがあります。
追記:「上位互換」と煽っていますが、実装量・定数倍の面から、Moが使えるときはMoを使ったほうが良いでしょう

Mo

まずはMo's algorithmの概要を説明しておきます。

Mo's algorithmは以下のような問題に適したアルゴリズムです。

長さNの数列に対し、Q回の区間クエリを処理する。
ただし、[l, middle) と [middle, r) の結果をマージすることはできない。(できるならsegtreeでいい)
・値の追加操作ができる。([l, r) から [l-1, r) や [l, r+1) が求まる)
・値の削除操作ができる。([l, r) から [l+1, r) や [l, r-1) が求まる)

つまり、区間の結果をマージする操作がlogとかでできず、区間を1つ伸ばしたり縮めたりするのがlogとかでできる場合。
クエリをリンク先の記事のソースコードのようにソートして、区間を伸縮しながら処理するというのがこのアルゴリズム

クエリの l と r を2次元座標にプロットすると一目瞭然です。
f:id:snuke:20160701022948j:plain
(本当は l >= r の領域には点がありませんが、本質的な差はありません)

  • 赤点はクエリを、黒線は区間の伸縮の様子を表しています。
  • 緑線で区切られた領域は√N個あり、それぞれの高さは√Nです。

このとき、横移動(rを増減させる操作)に注目すると、左端から右端までの逆戻りなしの往復が√N回となるため、全体の長さは O(N√N) となります。
そして、縦移動(lを増減させる操作)に注目すると、ひとつの点に対して高々√Nなので、全体の長さは O(Q√N) となります。
つまり、計算量は O( (N+Q) √N * [伸縮1回の計算量] ) となります。(厳密には + Q log Q だけど本質ではない)

追記:区切る領域の個数を√Q個(高さはN/√Q)にすると計算量はO(N√Q)になるらしい、なるほど。(横移動はそのままで、縦移動はQN/√QでこれもN√Q)
こっちの計算量の方が上記よりも良いこと( O(N√Q) ≦ O((N+Q)√N) )を示しておく。
両辺を√Nで割って O(√N√Q) ≦ O(N+Q)、両辺二乗して O(NQ) ≦ O(N^2+Q^2+NQ)。

実装

実装自体はイメージよりもだいぶ軽いです。

int n; // 数列の長さ
int q; // クエリ数
vector<int> l(q), r(q); // クエリの[l,r)
/* 入力 */

// ソート
int sq = max(1, int(n/sqrt(q)));
vector<int> qi(q);
for (int i = 0; i < q; ++i) qi[i] = i;
sort(qi.begin(), qi.end(), [&](int i, int j) { // クエリの順番をpair(l/sq,r)でソート
  if (l[i]/sq != l[j]/sq) return l[i] < l[j];
  return r[i] < r[j];
});

// クエリの処理
// add(i)は追加操作、del(i)は削除操作
int nl = 0, nr = 0; // [nl,nr)
for (int i : qi) {
  while (nl > l[i]) --nl, add(nl);
  while (nr < r[i]) add(nr), ++nr;
  while (nl < l[i]) del(nl), ++nl;
  while (nr > r[i]) --nr, del(nr);
  /* クエリの結果計算 */
}

上位互換

Moの上位互換のアルゴリズムは上記のようなクエリを処理できます。しかも、削除操作ができる必要がありません。
その代わり、データ構造にはrollback(+snapshot)メソッドを実装する必要があります。
rollbackはその名の通り、snapshotを撮った位置までデータ構造の状態を巻き戻すメソッドです。
rollbackは、 <配列のindex, 元の値> のペアを記録しておいて時系列の逆順に戻すようにやります。データ構造が複雑な場合はindexの代わりにポインタで持つと良さそう。
これは追加操作と同じ計算量になります。なぜなら、追加操作の計算量がO(log N) だとすると、追加操作で行われる代入の回数は高々O(log N)にしかならないためです。

アルゴリズム

まず、長さが√N以下のクエリを愚直に全て処理します。(クエリあたり O(√N * [追加操作の計算量] ))
残りの長さが√Nより大きいクエリを l/√N の商で仕分けます。
それぞれのグループのクエリたちの処理は以下のように行います。
f:id:snuke:20160701031448j:plain
1. グループ内のクエリ区間を右端の昇順にソートしておく。
2. グループ内のクエリ区間の左端をギリギリ超えるような √N の倍数を X とする。(緑の縦線の位置)
3. [X,X) から始めて、右端を1つずつ伸ばしていく。
4. 現在の右端がクエリ区間の右端と一致したらsnapshotを撮る。
5. 左端をクエリ区間の左端まで伸ばす。
6. rollbackして 3. に戻る。
右端を伸ばす回数は1グループあたり O(N) なので、全体で O(N √N) 回です。
左端を伸ばす回数は1クエリあたり高々 O(√N) なので、全体で O(Q √N) 回です。
これらをまとめると、計算量はこれまた O( (N+Q) √N * [追加操作の計算量] ) となります。

追記:Moと同様に、√Q個に分割するとO(N √Q * [追加操作の計算量])になって計算量が真に良くなります。

以下はrollback(とsnapshot)がついたUnionFindの実装例です。

struct UF {
  vector<int> d; // 根の場合は高さ*-1、子の場合は親の番号が入る
  vector<pair<int,int>> history;
  UF(){}
  UF(int mx):d(mx,-1){}
  int root(int x){
    if(d[x] < 0) return x;
    return root(d[x]);
  }
  void unite(int x, int y){
    x = root(x); y = root(y);
    if(x == y) return;
    if(d[x] > d[y]) swap(x,y);
    if(d[x] == d[y]) {
      history.pb(make_pair(x,d[x]));
      d[x]--;
    }
    history.pb(make_pair(y,d[y]));
    d[y] = x;
  }
  void snapshot() {
    history.clear();
  }
  void rollback() {
    while (history.size()) {
      d[history.back().first] = history.back().second;
      history.pop_back();
    }
  }
};

このアルゴリズムこれ(UF+区間クエリ)とかが解けます。
ちなみにこれ自分で考えて喜んでたら、Moの記事のコメント欄にも載ってました
名前があった方がウケがいいらしいので、Rollback平方分割とでも呼ぶことにしようかな。
ちなみに、追加クエリが均し計算量の場合は注意が必要です。

まとめ

汎用性の高い Rollback平方分割 の方を覚えておいて損はないと思います。
Mo's algorithmも、上の方にある図を覚えておけばすぐに思いつける程度のものだし、忘れる必要はないです。
ただ、実用上では必ずしも上位互換というわけではなく、削除操作が出来てかつ「削除操作の実装 < 分割+rollbackの実装」の場合は実装量の面でMo's algorithmの方がいいかもしれません。追記:あと、定数倍もMoの方が良いっぽい。