ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

早稲田大学プログラミングコンテスト2019 D - Choose Your Characters

D - Choose Your Characters

解法

条件を満たしている区間はさらに伸ばしても必ず条件を満たすので、しゃくとり法が使えます。上手くしゃくとり法ができるように工夫をしましょう。

しゃくとり法では自キャラのほうを区間に入れたり出したりするので、それに応じて相手キャラごとに管理した値を操作するほうがやりやすいです。具体的には相手キャラ  j それぞれについて、

  •  n\lbrack j \rbrack = 今見ている区間  \lbrack L, R\rbrack 内の自キャラ  i のうち、「 i j に対して不利である」ような  i の個数

を管理すると上手くいきます。

その理由として、問題には「任意の相手キャラに対して五分または有利な自キャラが1体以上存在する」という条件が書いてありますが、入力  N が大きいときにはほとんどが五分の関係なので数が非常に多いです。そのため逆に「自キャラが相手キャラに対して不利である」という関係を使うようにすると条件数が少なくて扱いやすくなります。

ここで「相手と同じキャラは自キャラとして選べる候補から除外する」という条件が厄介ですが、「自キャラ  i は相手の同キャラ  i に対して不利である」という関係を追加することでこの条件を処理することが出来ます。

区間  \lbrack L, R\rbrack を選んだ時に問題の条件を満たすためには、すべての相手キャラ  j について「 j に対して不利でない自キャラが存在する」こと、つまり  n\lbrack j \rbrack の最大値が区間  \lbrack L, R\rbrack の長さ  R-L+1 よりも小さいことが必要十分です。 \max を取りたいので  n\lbrack j \rbrack の値をセグメント木で管理しましょう。

区間に自キャラ  i を出し入れする際には、「自キャラ  i が不利であるような相手  j 」を事前に列挙しておいて、そのような  j について  n\lbrack j \rbrack を増減させます。不利であるという関係が全部で  N+M 個しかないので、この増減操作は問題全体で  O(N+M) 回しか行われません。

このようにしゃくとり法を最後まで回して、見つかった区間のうち最も短いものを出力すればよいです。

ACコード

Submission #4542091 - 早稲田大学プログラミングコンテスト2019

早稲田大学プログラミングコンテスト2019 C - Permutation City

C - Permutation City

解法

木にする

まずはグラフの形を簡単にします。距離に関する条件が「1または2である」ということ、そして「条件を満たす順列は必ず存在する」と書かれていることから、

  1. 連結性を保ったままいくつかの辺を削除しても、変化後のグラフに対する答えは存在する。
  2. 変化後のグラフに対して求めた答えは、元のグラフに対する答えにもなっている。

ことが分かります。2番目の性質は、変化後のグラフで距離が1または2である頂点対は、辺を足して元のグラフに戻しても距離が1または2であることから分かります。

そのため考えやすいように木にしてしまいましょう。例えばUnion-Findを用いて、辺を1本ずつ入力から受け取りながら既に両端が連結な辺については無視することで、全域木を得ることが出来ます。

答えを求める

答えの構成方法として最も簡単なのは、どの頂点間の距離も1または2であるような2頂点以上のグループに分割し、その中で頂点番号をローテーションすることです。

f:id:betrue12:20190310192606p:plain

このように2頂点以上のグループを作ることが重要です。1頂点だけだと頂点番号が動かないので、距離が1または2ではなく0になってしまいます。

どの頂点間の距離も1または2であるようなグループとして、作りやすいのは深さ1の木です。先ほどグラフを木にしたので、これを深さ1の木に分割していくことを考えます。

根付き木にして葉のほうからグループを作っていきます。具体的には各頂点について、

  • 自分の子のうち「グループに入っていない」状態の子が1つでもあれば、そのような子と自分自身でグループを作る。
  • そうでない場合、自分を「グループに入っていない」状態にする(親とグループになる)。

と処理していくと条件を満たすグループを作れます。以下の図がそのようなグループ分けの例です。

f:id:betrue12:20190310193335p:plain

ただしこの方法だと、運が悪いと根が孤立してしまいます。これを防ぐ方法としては、最初に根を選ぶ時には次数1の頂点を選び、根が孤立しそうな時は唯一の子が根をグループに入れてあげると良いです。

各グループについて頂点番号をローテーションしたものを答えとして出力すればOKです。

ACコード

Submission #4536151 - 早稲田大学プログラミングコンテスト2019

ABC121 D - XOR World

D - XOR World

解法

 A, A+1, ..., B について○○を計算した合計を求めよ」という問題で使える実装テクニックとして、代わりに「 0, 1, ..., B について○○を計算した合計」から「 0, 1, ..., A-1 のうち○○を計算した合計」を引いたものを求めると考えると、変数が減る上に同じ処理を2回すれば良いだけになるので楽です。XORの場合は、引き算としてはXORをすればよいです。

そのため以降は  0, 1, ..., B のXORを考えます。このとき0から数えて、各ビットの値は以下のようになっています。

f:id:betrue12:20190309224118p:plain

XORを求めたいので、重要なのは各ビットごとの1の個数の偶奇です。

図を見るとまず一番下以外のビットについては、隣り合う (偶数, 奇数) のペアではビット値が同じになっていることが分かります。つまり一番下以外の各ビットについて、このペアに含まれる1の個数は偶数個です。

一番下のビットだけはそうなっていませんが、隣り合う4つごとに区切って考えると1つの4つ組には1が2個あることが分かります。

つまり左から4つ組で区切っていくと、その4つの中では必ず全てのビットについて1の個数が偶数個になっている、つまり4つの数のXORがちょうど0になることが分かります。

f:id:betrue12:20190309224128p:plain

そのため4つ組ができているところは無視してもよく、一番最後に余ったところだけを計算すればよいです。具体的には  B を含む4つ組の最初の数字は  \lfloor\frac{B}{4}\rfloor\times 4 になるので、この値から  B までのXORを取ればよいです。

この計算を  A-1 B の両方に行い、その結果のXORを取ったものが答えです。

ACコード

Educational Codeforces Round 61 D. Stressful Training

Problem - D - Codeforces

問題概要

コンテスト参加者が使う  n 台のPCがある。 i 番目のPCの初期電池残量は  a_{i} で、消費速度は毎ステップ  b_{i} である。

初めに充電器の充電速度として非負整数  c を決め、以下の処理を  k-1 ステップ行う。

  • 各ステップごとに、どのPCを充電するかを1台選ぶ。
  • 充電対象として選んだPCは、電池残量が  b_{i} - c 減る。それ以外のPCはそれぞれ  b_{i} 減る。電池残量に上限はない。

全てのステップにおいて全てのPCの電池残量が負にならなければコンテストは成功である。コンテストを成功させることが可能な非負整数  c の最小値を求めよ。( c の値に関わらず不可能な場合は -1 を出力せよ。)

※ステップ数が  k-1 なのが謎ですが、サンプルがそう言っているのでそうなんだと思います。

制約

  •  1 \le n \le 2 \times 10^{5}
  •  1 \le k \le 2 \times 10^{5}
  •  1 \le a_{i} \le 10^{12}
  •  1 \le b_{i} \le 10^{7}

解法

二分探索をします。 c を固定した時にコンテストを成功させることが可能かどうかを判定することを考えます。

最初のステップを0ステップ目として各ステップに番号を付けます。 c を固定することで、各PCについて「 t 回目の充電は遅くとも何ステップ目までに行わなければいけないか?」を求めることが出来ます。例えば  i 番目のPCでは、電池残量が  a_{i} からスタートして1ステップごとに  b_{i} 減っていくので、1回目の充電は遅くとも  \lfloor\frac{a_{i}}{b_{i}}\rfloor ステップ目終了時点までに行う必要があります。2回目の充電は  \lfloor\frac{a_{i} + c}{b_{i}}\rfloor ステップ目終了時点までに、3回目の充電は  \lfloor\frac{a_{i} + 2c}{b_{i}}\rfloor ステップ目終了時点までに…とそれ以降も計算できます。

これを、計算結果が最終ステップである  k-2 ステップ目を超えるまで計算します。ただし合計充電回数が  k-1 回を超えてしまった場合は絶対に成功させられないので、その時点で強制的に処理を終わらせて「不可能」と判定してしまいましょう。このように処理すると全PCについての処理を  O(\max(n, k)) 時間で終わらせることが出来ます。

これを全てのPCについて計算することで、各ステップについて「 t ステップ目終了時点までに、全体で累積何回の充電が必要か?」を求めることが出来ます。対して  t ステップ目終了時点までに行える累積充電回数は(0-indexedとしているので)  t+1 回です。全てのステップそれぞれの終了時点においてこの累積充電回数が足りていることが、コンテストを成功させられる必要十分条件となります。これで判定ができます。

先程書いたように判定1回の計算量は  O(\max(n, k)) となります。全体計算量はこれに、解の最大値を  C_{\max} として  O(\log(C_{\max})) を掛けたものです。

1台のPCについてコンテストを通して減る電池残量は最大で  (k-1) \max b_{i} \lt 2\times 10^{12} であり、これを超える充電は意味がありません。なので  C_{\max} = 2\times 10^{12} としておけば良いでしょう。

ACコード

Submission #50899052 - Codeforces

ABC120 D - Decayed Bridges

D - Decayed Bridges

解法

グラフの連結性を考えるのに便利な道具として Union-Find木 があります。Union-Find木では「辺を追加して頂点同士を連結にする」という操作が可能ですが、対して今回の問題は「辺を削除して頂点同士を分断する」という操作になっています。辺の削除はUnion-Find木ではできません。

このような時に有効なのが「時間を逆回しにして考える」というテクニックです。問題の操作を逆回しにすると、辺が全くない状態から始まって辺が1本ずつ追加されていくと考えることができます。これならUnion-Find木が使えます。

ということで辺を1本ずつ追加しながら、それぞれの時点での「互いに行き来できない(非連結な)頂点のペア数」を求めることにしましょう。

最初は辺が1本もないので、全てのペアが非連結です。なので非連結なペア数は  \frac{N(N-1)}{2} 個です。

 (A_{i}, B_{i}) を1本足した際、 A_{i} B_{i} が既に連結だった場合は何も起こりません。非連結だった場合は以下の図のように「既に A_{i} と連結な頂点」と「既に B_{i} と連結な頂点」の組み合わせ全てが新しく連結になります。そのためそれぞれの頂点数を掛け算した値だけ、非連結なペア数が減ることになります。

f:id:betrue12:20190303224053p:plain

あとはこれを実装しましょう。それぞれの連結成分に含まれる頂点数を保持する機能を持ったUnion-Find木を用いて、辺を追加するごとに上記のような計算をしていけばよいです。

ACコード

このコードではUnion-Find木の実装の中に、非連結なペアの個数を計算する処理を追加しています。個人的にはこれが楽ですが、分かりにくいようであればmain関数の中で計算しても良いでしょう。

元の問題は「 i 番目の橋を壊した後に  i 番目の答えを計算する」ですが、時間を逆回ししているため「 i 番目の答えを計算してから、 i 番目の辺を追加する」という処理順番になることに注意してください。

みんなのプロコン2019 決勝 A - Affiches

A - Affiches

オンサイトで解けなかった問題…ザ・数学。

解法

公式解説と少し違う方法で考えたので、その解法を書きます。

大きな長方形の中にある1点  (h, w) を考えます。この点が2つの小さな長方形両方に入っている確率を考えます。

f:id:betrue12:20190225222409p:plain

小さな長方形の置き方は1枚目と2枚目では独立に、そして縦座標と横座標でも独立に考えることが出来ます。縦座標  h が長方形1つの縦座標に含まれる確率を  f(h), 横座標  w が長方形1つの横座標に含まれる確率を  g(w) とすると、点  (h, w) が2つの小さな長方形両方に含まれている確率は  f(h)^{2} g(w)^{2} になります。これを大きな長方形の領域全体で積分すると答えを求めることが出来ます。

ここで積分の式は分離することが出来て、大きな長方形の領域全体を  D とすると

 \iint_{D} f(h)^{2} g(w)^{2} dhdw = (\int_{0}^{H} f(h)^{2} dh) \times (\int_{0}^{W} g(w)^{2} dw)

と縦横それぞれの積分の掛け算で答えを求めることが出来ます。(左辺は重積分で書いていますが、あまり気にしなくてもいいです)

あとは具体的に  f(h) などの値を計算して積分をします。  f(h) がどのようなグラフになるかを調べるため、 2A H の大小関係で場合分けします。(縦座標と言いつつ横向きになっていますが気にしないでください…)

f:id:betrue12:20190225221044p:plain

f:id:betrue12:20190225221107p:plain

場合分けをしたものの、両者のグラフの形は全く同じ形をしています。両端に近づくと確率が低くなる台形状です。

実際、 a = \min(A, H-A) とおくとこれはどちらも

  •  0 \le h \le a のとき  f(h) = \frac{h}{H-A}
  •  a \le h \le H-a のとき  f(h) = \frac{a}{H-A}
  •  H-a \le h \le H のとき  f(h) = \frac{h}{H-A}

という同じ式で表すことが出来ます。それぞれの区間で2乗を積分して合計すると

 \int_{0}^{H} f(h)^{2} dh = \frac{1}{(H-A)^{2}} \times (\frac{1}{3} a^{3} + (H-2a)a^{2} + \frac{1}{3} a^{3})

という式が得られます。

 w についての積分も全く同様に計算することができるので、それぞれ計算して掛け算すると答えを求めることが出来ます。

ACコード

Submission #4354095 - 「みんなのプロコン 2019」決勝

まあ、数式をコードにしてるだけですね…。これを本番解けなかったのは悔いが残ります。

AtCoder World Tour Finals 2019 B - Multiple of Nine

B - Multiple of Nine

解説ACしたので、自分の理解のためにも公式解説よりも少し詳しい解説を書いていきます。

区間の条件を累積和の条件に落とし込む

「非負整数を9で割った余りは10進数での桁和を9で割った余りと等しい」という性質を使います。

 i 番目の数字を  d_{i} と表記します。 d_{1} から  d_{i} までの累積和を9で割った余りを  s_{i} と表記します(ただし  s_{0} = 0)。以降は9で割った余りを単に累積和と呼びます。

こうすると区間  \lbrack l, r\rbrack が表す整数が9の倍数であることは、そのすぐ外側にある累積和  s_{l-1}, s_{r} が等しいことと同値であることが言えます。

ただし、複数のクエリが同じ累積和を共有することがあります。その場合は条件式が結合されます。

このようにクエリの集合を、「mod9で取った累積和のどこかが等しい」という条件の集合に落とし込むのが第一歩です。この結合された後の条件式の個数を  Q^{\prime} とします。全ての累積和が異なっていれば  Q^{\prime} = Q で、そうでなければ  Q^{\prime} \lt Q です。

以降、いずれかの条件式に登場する累積和を「大事な累積和」と呼ぶことにします。

累積和の間の場合の数を考える

全ての条件式の大事な累積和を集めてソートして、それぞれの累積和の位置で数列を分割します。ソートされたときに隣り合っている大事な累積和を「隣り合う累積和」と呼ぶことにします。

隣り合う累積和に挟まれたブロックについて、数字を選ぶ場合の数を考えます(両端のブロックは後で考えます)。1ブロックの中の数字の選び方に関係するのは、その両端にある隣り合う累積和の差です。ブロックの中の数字の合計を9で割ったものが、両端にある大事な累積和の差(mod9)と一致しなければなりません。

具体的に数えてみます。例えば1ブロックに含まれている数字の個数が3つだったとします。3つの数字の選び方は全部で1000通りです。そして3つの数字の合計を9で割った余りの分布は、0~999までの整数を9で割った余りの分布と等しいので

  • 0:112個
  • 1:111個
  • 2:111個
  • ...
  • 8:111個

となり、0になるものが1個だけ多いです。これは文字数が3でない場合にも同様に計算できて、文字数が  n のとき余りが1~8になる場合の数はそれぞれ  \frac{10^{n}-1}{9} で、余りが0になる場合の数はそれに1足したものになります。

つまりそれぞれのブロック中の数字の選び方を求めるためには、その両端にある隣り合う累積和が等しいかどうかを考える必要があります。

大事な累積和の値の取り方についてDPする

最初に見たように、大事な累積和は「このグループに属する累積和たちは値が等しい必要がある」という  Q^{\prime} 個のグループに分かれています。それぞれのグループに0~8を割り当てていけば全てのパターンを列挙できますが、 9^{Q^{\prime}} パターンあるので単純な全列挙はできません。

このグループには大事な累積和がごちゃ混ぜの位置で入っているため、「左から順番に決めていく」みたいな方法を取るのも難しいです。そこで「値が同じである累積和のグループを一気に決める」ことを考えます。具体的には次のようなDPです。

 dp \lbrack i \rbrack \lbrack S \rbrack:累積和の値が  0, 1, ..., i になるようなグループまで選び終わっていて、割り当て終わったグループの集合が  S であるような○○

この○○は何にすれば良いでしょうか。ある  i について「こことここの累積和が  i になる」として決めた時、それらの累積和に隣り合ったものがあれば、先程見たようにその間にあるブロックについて「場合の数が1多くなる」現象が発生します。このとき、「全累積和が異なる」ことを仮定したときの場合の数は最後に掛けることにして、DPテーブルにはあるブロックの場合の数が1多くなったことによって得られる倍率(係数)を格納していく という荒業を使います。先程の例で言うと  \frac{112}{111} をDPの値に掛けます。

ということでDPテーブルの定義は以下のようになります。

 dp \lbrack i \rbrack \lbrack S \rbrack:累積和の値が  0, 1, ..., i になるようなグループまで選び終わっていて、割り当て終わったグループの集合が  S であるときの、「全累積和が異なる」ことを仮定したときの各ブロックの場合の数の積と比較して得られる係数

そして「全累積和が異なる」ことを仮定したときの場合の数は別途計算して、DPの初期値にするか最後に掛けてあげればよいです。

このDPは部分集合を列挙する  O(3^{Q^{\prime}}) のDPとなります。具体的に  dp \lbrack i \rbrack \lbrack S \rbrack を求める時は、値を  i にするグループの集合  T S の全ての部分集合として列挙し全て合計します。 i-1 までに得られている係数は  dp \lbrack i-1 \rbrack \lbrack S-T \rbrack であり、これに集合  T を同じ値にしたときに得られる係数を掛けます。

この「集合  T を同じ値にしたときに得られる係数」は全ての  T について事前に計算しておくことが出来ます。各  T について、隣り合う累積和が含まれているかをチェックし、含まれている場合はその間にある文字数を  n として  (\frac{10^{n}-1}{9} + 1) \div \frac{10^{n}-1}{9} を掛けていけば良いです。この前計算は  O(Q^{\prime}2^{Q^{\prime}}) で出来ます。

両端のブロックについて考える

ここで先程後回しにしていた、どの区間にも含まれない両端のブロックについて考えます。

まず一番右のブロックは好きに選んで良いです。文字数を  n として  10^{n} の係数が掛かります。

次に一番左のブロックですが、左端の累積和は  s_{0} = 0 です。つまり一番前のブロックの文字数を  n、大事な累積和のうち一番左にあるものを  s_{f} として、場合の数は  s_{0} \ne s_{f} ならば  \frac{10^{n} - 1}{9} であり  s_{0} = s_{f} であればそれより1大きい値です。

この値を、DPの中で「 s_{f} を含むグループが選ばれるタイミング」で  s_{f} の値に応じて掛け算してあげればよいです。

また、もう少し計算が簡単な方法として、DPの対称性を利用する方法があります。このDPでは各グループに割り当てた余りをまるっと入れ替えても同じになるので、 s_{f} の値に応じた値をそれぞれ掛け算する代わりに「最初のブロックは好きに選んで良い、そのかわり  s_{f} の値は何か1つ(例えば0)に固定されている」という条件でDPをしてもよいです。公式解説の数式はこっちになっていると思います。

解法まとめ

上記の内容を手順としてまとめます。

  1. まず入力のクエリを「累積和が等しい」という条件に置き換える。このとき条件式が結合するものはまとめてグループ化しておく。
  2. グループの集合  2^{Q^{\prime}} 個について、「そのグループに含まれる累積和が等しいときに、隣り合う累積和が等しいことによって得られる係数」を前計算しておく。
  3. 部分集合列挙DPを行う。
  4. 最後に全体に掛かる係数(公式解説にある数式1)を掛ける

これで解けます。お疲れ様でした。

ACコード

Submission #4375982 - World Tour Finals 2019 Open Contest