ARMERIA

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

HACK TO THE FUTURE 2020予選 参加記録

HACK TO THE FUTURE 2020予選 - AtCoder

なんと全体10位で本戦に進むことができました!

f:id:betrue12:20191104193413p:plain

やったことを軽く書いておこうかと思います。けっこう雑な焼きなまし法なので、あまり参考になるかは分かりませんが…

ビジュアライザのスクリーンショット等はexample_01.txtのものを利用しています。また記載している試行回数などは手元実行のもので、AtCoderのコードテストでは4倍くらい多く回っています。

BFSでマス全埋め(24:39、4,370,893点)

最初に挨拶代わりに 0 で正の得点を取ったのはいいとして、まず思ったのは「全ロボットはゴールさせる前提になるだろう」ということ。

ゴールと連結であればゴールからBFSで矢印を伸ばしていくことで必ずゴールさせることができるので、まずそれを書きました。

f:id:betrue12:20191104194425p:plain

サンプル1での矢印は1298個。何となく直線で続いていたほうが後々削りやすそうかなと思ったので、1回の探索で隣4マスだけでなく、4方向に進んでブロックにぶつかるまでを見るようにしました。これが437万点。

不要矢印の削除(58:29、4,947,389点)

さすがにこれは無駄で、全く使われない矢印がいっぱいあります。この経路に沿って実際にロボットを動かしてみて、ロボットが1回以上向きを変えた矢印のみを残すようにしました。これで矢印は160個に。

さらにこの中に、「最初に決めた経路通りにロボットが進むと使うけど、実は取り除いても問題ないもの」がいくつかあります。これは愚直に、矢印全部に対して「1個矢印を消してみて全ロボットを動かして、全員ゴールできるようなら消す」ようにして消しました。これは意外とあって142個まで減りました。

f:id:betrue12:20191104200114p:plain

これで494万点、暫定トップになっていたようです。

試行錯誤

BFSのキューに入れる順番を近い方から入れてみたり、遠い方から入れてみたり、DFSにしてみたり、過去コンテストで「4方向の探索順序を変えるとスコアが大きく変わる」というのがあったので試してみましたが、いまいち良い知見は得られず。

仕方がないので山登り法/焼きなまし法を回し始めます。

近傍1種の山登り法(1:49:17、4,950,033点)

近傍2種の焼きなまし法(3:43:46、4,962,496点)

この辺は改良と提出を何回か繰り返していますがまとめて書きます。

焼きなまし法をするにしても「近傍って何だよ…」という気分になるのですが、既に矢印によって経路ができているので、あまり経路を大きく崩すような近傍は良くない気がしました。

とりあえず試したのが「矢印を1個選んでランダムに回転させる」というもので、次に「矢印を1個選んでランダム方向に1~10マス平行移動する」と2種類交互に実行するようにしました。その矢印を通っていたロボットが、運良く違う経路に合流できてそっちからゴールできる場合、元々通っていた矢印を消せるかもしれないからです。

変更後はまず全部のロボットがゴールできるか確かめて、ゴールできなかったらその時点で却下。その後は先ほどと同じように全矢印に対して消していいか判定をして減らします。そしてスコア計算をして焼きなまし法に従い解を更新します。

サンプル1の矢印数は117個まで減り、スコアも496万点まで伸びました。

f:id:betrue12:20191104204438p:plain

試行回数は35,000回×2種類。ただ近傍を完全にランダムに取ったので、変更するとそもそも全部のロボットがゴールできなくなって即却下される確率のほうが高いです。変更した矢印の先に矢印がなければ置いてみる…みたいな実装もしましたがイマイチでした。ここでちゃんとBFSをやり直すなどして経路を作ってあげたらマシになったのかもしれません。

近傍3種の焼きなまし法(5:53:42、4,964,370点)

コンテスト時間が半分を過ぎて順位もズルズル落ち、アイデアが尽きてきたのでとりあえず新しい近傍を開発してみることにしました。今の近傍の取り方では実行時間を増やしてもスコアが全然伸びなかったので、もっと広い範囲に解を振ってみようというものです。

これまで「回転」と「平行移動」をしていたので、3つ目として「回転と平行移動」を加えました。これだけでサンプル1の矢印数は114個になり、ちょっとスコアが伸びました。

近傍4種+高速化(6:52:32、4,965,203点)

さらに4種類目の近傍として「縦にも横にも位置をずらして回転」というのを加えました。斜めに動かすと入る方と出る方の両方がずれるのであまり良くないような気がしたんですけど、実際に試すと意外にもスコアが伸びました。単純に振れ幅の大きい近傍が入ることで探索範囲が広がった効果ですかね…?

ただこの4種類目の近傍だけを試しても上手く行かなくて、「回転だけ」→「平行移動だけ」→「平行移動+回転」→「縦横移動+回転」→「回転だけ」→…というふうに順番に回していったので、近い近傍と遠い近傍をバランス良く探索できたのかもしれません。

また近傍が増えてくるとその分試行回数も必要になってくるので、小手先でできる範囲の高速化をしました。具体的には矢印を変えた後にロボットがゴールできるかの判定を、元の経路でその矢印を通っていたロボットから先に行うようにしました。本当はもっとオーダーレベルの改善ができると思うんですけど…

試行回数は約100000回×4種類。矢印の数は112個でした。

最終成績(7:54:07、4,965,312点)

Submission #8259364 - HACK TO THE FUTURE 2020予選

最後はパラメータや乱数シードガチャでわずかに点数を伸ばして終了。最後の追い上げでどんどん抜かされてハラハラでした。

f:id:betrue12:20191104211131p:plain

振り返り

全員ゴール可能にする→不要矢印削除、というそこそこ強い初期解を素早く作ることができた…けど、早い段階での実装・提出をしていなかっただけで上位勢は気づくポイントだと思うので、強みになるのかは微妙。

斜め移動など「絶対に損するだけでしょ」と思うような振り方でも試してみるのは大事。

途中時点では高速化の恩恵が薄いと思っても、後で試行回数を増やしたくなるタイミングは高確率で来るので、他にやることがないなら高速化しておくに越したことはない。速度は正義。ただし高速化でバグらせると萎えるので実装力大事。

4時間時点でアイデアが尽きて既にお腹いっぱいな気持ちだったけど、諦めなければ何かできることはある。アルゴのコンテストと同じく、コンテスト中のモチベーション維持は大事。

本戦も頑張ります。

AtCoder Grand Contest 040 B - Two Contests

B - Two Contests

本番では考察不足で2ペナを出しましたが…自分の考察がある程度整理できたので書きます。

解法

公式解説にならい、それぞれのコンテストを「集合」、問題  i を解ける人の範囲を「区間  i 」、コンテストの楽しさを「含まれる区間の共通部分の長さ」と書くことにします。区間を半開区間として扱うことで区間  \lbrack s, t) の長さを単に  t-s と書けるので、区間は半開区間として扱います。また区間の番号は  i = 0, ..., N-1 で表記します。

2つの集合を集合1, 2と書くことにします。このとき集合  k に含まれる区間の共通部分は(もし存在するならば)区間になり、その左端は含まれる区間 L_{i} の最大値、右端は  R_{i} の最小値となります。これらの値をそれぞれ  s_{k}, t_{k} と書くことにします。共通部分が存在しない場合のことも考慮すると、この共通部分の長さは  \max(t_{k} - s_{k}, 0) と計算できます。

 N 個の区間を左端  L_{i} でソートして、番号を振り直してみましょう。このとき  L_{i} が最も大きい区間  N-1 が含まれるほうを集合2、そうでないほうを集合1と呼ぶことにします。

ここで「集合1に含まれる区間のうち、最も番号が大きいものはどれか」を全探索しましょう。これを  x 番目とすると、以下の状態まで割り振りが確定します。

f:id:betrue12:20191104045925p:plain

ここまで割り振ると、残りの区間 L_{i} L_{x} 以下なので、 s_{1} = L_{x}, s_{2} = L_{N-1} であることが確定します。このように左端でソートして、それぞれの集合で左端が大きいものを1つ決めてあげることで、 s_{k} の値が確定して考えやすくなります。

 t_{1}, t_{2} については今後区間が足されることで小さくなるかもしれませんが、既に割り振っている  R_{i} の最小値を暫定値と思っておきましょう。

残りの区間はどう割り振るべきでしょうか?このとき実は、残っている区間を集合1, 2のどちらか一方に全て入れるケースだけを考えれば良いです。残っている区間の中で最も小さい  R_{i} はどちらかの集合に割り振らなければならず、これを割り振ったほうにそれより大きい  R_{i} を割り振っても影響はないので、どちらか一方の集合に集中させたほうが  t_{1}, t_{2} への損失は少ないからです。

つまり、割り振りは以下の2パターンになります。

f:id:betrue12:20191104045934p:plain

f:id:betrue12:20191104045943p:plain

これは結局、区間の割り振り方としては「ある1つの区間  x だけを孤立させて残りを全部まとめる」か、「左端ソートして、ある区間  x を境界として二分する」かのどちらかしか考えなくても良い ということを意味しています。

これはどちらも、 L_{i} の範囲最小値と  R_{i} の範囲最大値を効率的に求められるようにしておけば計算できます。セグメント木、スパーステーブルが使えますし、今回必要なのは左右端からの範囲だけなので累積min/maxを前計算しても良いです。 \log を乗せてもいいならセグメント木が楽だと思います。

ACコード

Submission #8282036 - AtCoder Grand Contest 040

JOI春合宿2015 K - 遺産相続

お題箱より。JOIの解説記事は初めてかな…?

K - 遺産相続

解説途中の証明についてのリクエストだったのでそこを重点的に書きます。

解法

最大全域木として考える

都市を「頂点」、鉄道を「辺」、鉄道の収益を「辺重み」と考えます。

「閉路ができない範囲で取れるだけ取る」という処理は最小(最大)全域木のアルゴリズムで実現できます。まず子供1の辺の取り方は、

  1. 辺を重みが大きい方から順に見ていく。
  2. それぞれの辺について、それを追加することで閉路ができないならば、その辺を取る。

というクラスカル法のアルゴリズムで求めることができます。重みが相異なるという条件から、この取り方は一意です。

子供2以降は、自分より前の子供が誰も使わなかった辺だけについて同じことを繰り返します。閉路ができるかの判定のためには、各子供がそれぞれグラフ(実装上はUnion-Find木だけで十分)を持って連結状態を管理しておけば良いです。

これを最後の子供までやれば答えが求められる…のですが、辺が大量に後ろまで残るようなケースだと、単純計算で(子供の人数)×(辺の数)×(追加できるかの判定の計算量)くらいの計算量がかかることになります。

処理順序の逆転

発想を逆転させて、辺を重み順に見ていくというループを外側に持ってきます。つまり、

  • 子供を番号順に見ていく。
    • 残っている辺を重み順に見ていき、取れる(閉路ができない)ならば取る。

ではなく、

  • 辺を重み順に見ていく。
    • それを取れる子供のうち、最も番号の小さい子供がその辺を取る。

という処理をします。

これを単純にやると計算量はさっきと同じです。ですがこの「辺を取れる子供のうち、最も番号の小さい子供」を効率的に求める方法が存在します。

何となくの考察としては、番号の小さい子供のほうが優先的に辺を取るので、頂点同士が連結になっている度合いが高いです。であればある頂点  (a, b) 間を結ぶ辺を追加するときに、 (a, b) が既に連結である子供」と「 (a, b) がまだ連結でない子供」はある番号を境にキレイに分かれているのでは、と推測できます。この単調性が成り立っていれば二分探索ができます。

この証明を考えます。公式解説は帰納法として書いていますが、背理法っぽく書きます。本質的にはだいたい同じだと思います。

単調性の証明

上記の性質が成り立たない、つまり

処理の途中で、ある頂点の組  (a, b) について、ある子供  i では非連結で、それより番号の大きいある子供  j について既に連結である状態になっている

と仮定します。このとき子供  j のグラフにおいて頂点  (a, b) 間を結ぶパスが存在します。説明を簡単にするため、例えば中継する頂点を  x, y の2個として、3辺  (a, x), (x, y), (y, b) がグラフに含まれているとします。

一方、子供  j より番号の小さい子供  i の持つグラフでは  (a, b) が非連結なので、 (a, x), (x, y), (y, b) のうち少なくともどれか1組は非連結です。であれば、子供  j が持っている3辺のうちどれか1つは子供  i に取られているはずです。これは矛盾です。

f:id:betrue12:20191103154107p:plain

実際には中継する頂点がいくつであっても同じ証明ができます。よって背理法から先ほどの単調性は必ず成り立つことが分かります。

これで二分探索ができるので間に合います。C/C++しか使えないJOI春合宿での問題なのでちょっとタイトですね。

ACコード

Submission #8266997 - JOI春合宿2015 オンラインジャッジ

Educational Codeforces Round 75 E2. Voting (Hard Version)

お題箱より。

Problem - E2 - Codeforces

問題概要

選挙の投票者が  n 人いて、全員が自分を支持するようにしたい。投票者  i が自分を支持する条件は2つあり、どちらかを満たすと支持する。

  1. 金額  p_{i} を払って買収する。
  2. 他の投票者のうち  m_{i} 人以上が自分を支持している。

全員に自分を支持させるために必要な金額の最小値を求めよ。

制約

 1 \le t \le 2\times 10^{5} の複数テストケースで、各ケースは以下を満たす。

  •  1 \le n \le 2\times 10^{5}
  •  1 \le p_{i} \le 10^{9}
  •  0 \le m_{i} \lt n
  • 全ケースの  n の総和は  2\times 10^{5} 以下

解法

支持者0の状態から、1人ずつ順番に支持者を選んで増やしていくことを考えます。このとき買収金額最小化の裏返しとして、「買収せずに支持させる投票者の  p_{i} の合計を最大化する」ように支持者を選んでいきます。

既に  x 人の支持者がいて、次に  x+1 人目の支持者を選ぶ時のことを考えます。このときの選択としては、

  1.  m_{i} \le x でありまだ選んでいない投票者がいる場合、その中で p_{i} が最大である人を1人選んで支持させる。
  2. そうでない場合、誰かを1人買収することにする。誰を買収するかは後で決めて良い。

とするのが最適となります。その理由は、各ステップであえて損する選択(安い人を支持させたり、買収なしで支持させられる人がいるのに買収を選んだり)をしたときに、後でその損した分を上回るほどの得ができることはないからです。

これは優先度付きキューを使ってシミュレーションすることができます。具体的には支持者が  x 人であるような段階それぞれについて、まず  m_{i} = x であるような人の買収金額  p_{i} を優先度付きキューに入れ、その後キューが空でなければ最大要素を1つキューから出せば良いです。

そして最後までキューに残った人たちが買収の対象になるので、その人たちの  p_{i} の合計が答えになります。

ACコード

Submission #63321804 - Codeforces

CPSCO2019 Session1 F - Fruits in Season

お題箱より。

F - Fruits in Season

解法

最小値の最大化問題です。このタイプの問題はまず二分探索を考えてみる価値があります。

判定問題として、ある  X に対して「果物の美味しさの最小値を  X 以上にできるか?」という問題を考えます。最小値の最大化問題についてこのような二分探索を考えると、2つの嬉しいことがあります。

1. 単調性が自動的に確保される

二分探索を適用できる条件として必要なのが単調性です。

f:id:betrue12:20190511141733p:plain

「最小値を  X 以上にできるか?」という判定問題は、 X が大きいほど条件が厳しい問題になります。ある  X について条件を満たせば、それより小さい(条件の甘い) X については必ず条件を満たすので、自動的に単調性が確保されます。

2. 「貪欲」や「ギリギリまで粘る」など最適戦略が定まりやすい

果物の美味しさの最小値を  X 以上にすることは、全ての果物の美味しさを  X 以上にすることと同じです。

食べる日が旬から離れるほど果物の美味しさは減っていき、全ての果物をピッタリ旬に食べられるとは限りません。目標値が決まっていない状態では、1日ごとに美味しさが変動する果物のうちどれを優先すれば最小値を大きくできるのか決めづらいです。一方「全部  X 以上にする」という目標が決まっていれば、 X 以上である間はいつ食べても同じなので、「食べていい期間」と「食べられない期間」に分けることができます。

f:id:betrue12:20191103014857p:plain

このように目標値を決めることで、それを達成できる/できない条件が明確化されます。今回の問題のように「どれを優先するか」で悩むような問題や、限られたリソースを各要素に配分するような問題では、目標値を決めることで最適戦略が定まることが多いです。

この問題における最適戦略

今回の問題は果物  i の「食べていい期間」が区間になるので、以下のような戦略で割り当てていくことができます。

「今見ている日付を食べていい区間に含む、未割り当ての果物」を集合として管理しておきます。日付を早いほうから1日ずつ見ていきながら、以下の処理をします。

  1. 今見ている日が区間の左端である果物、つまり新しく食べられるようになった果物を集合に入れる。
  2. 今見ている日に割り当てる果物を決める。このとき区間の右端が最も左側にある果物、つまり猶予が最も短いような果物を選ぶのが最適である。

これで最後まで割り当てができた場合は判定問題の結果はYes、途中で割り当てる果物がなくなってしまったらNoです。

2で最も右端が左側にある区間を選ぶ操作は、集合を優先度付きキューとして管理していれば実現できます。集合に入れた後は右端の値しか使わないので、右端の値を単に整数として優先度付きキューに入れていけば良いです。

これで二分探索をすれば、解くことができます。

ACコード

Submission #5251240 - CPSCO2019 Session1

この問題の解法説明は公式解説とほぼ同じです。公式解説が十分丁寧に書かれているので、「最小値の最大化問題は二分探索するとなぜ上手くいくことが多いのか」というところをメインで書いてみました。

Codeforces Round #358 (Div. 2) D. Alyona and Strings

お題箱より。

Problem - D - Codeforces

問題概要

文字列  s, t が与えられ、それぞれの長さは  n, m である。また整数  K が与えられる。

以下の条件を満たすような  K 個の文字列の組  (p_{1}, ..., p_{K}) の、長さの総和の最大値を求めよ。

  •  p_{1}, ..., p_{K} のどの文字列も空でない。
  •  s, t のどちらにも、 p_{1}, ..., p_{K} がこの順番に重なることなく連続部分文字列として出現する。

制約

  •  1 \le n, m \le 1000
  •  1 \le K \le 10
  •  s, t は英小文字からなる
  • 問題の条件を満たす  (p_{1}, ..., p_{K}) が存在することが保証されている

※添字に  k を使いたいので入力の  K を大文字にしました。

解法

※文字列のインデックスは先頭を0文字目とする0-indexedで扱います。

この問題は最長共通部分列(LCS)の応用です。LCSとは2つの文字列  s, t に対して、「 s, t のどちらの(連続とは限らない)部分列にもなっているような文字列のうち、最長のもの(の長さ)」を求めたものです。

これはそれぞれの文字列の長さを  n, m として  O(nm) のDPで求めることができます。具体的には、

 dp\lbrack i \rbrack\lbrack j\rbrack = 文字列  s i-1 文字目までと文字列  t j-1 文字目までを見終わったときの、そこまでの共通部分列の長さの最大値

と定義して、以下の3パターンの遷移を考えます。

  •  s i 文字目を採用せずに無視する
    •  dp\lbrack i+1 \rbrack\lbrack j\rbrack \leftarrow dp\lbrack i \rbrack\lbrack j\rbrack
  •  t j 文字目を採用せずに無視する
    •  dp\lbrack i \rbrack\lbrack j+1\rbrack \leftarrow dp\lbrack i \rbrack\lbrack j\rbrack
  •  s i 文字目と  t j 文字目が等しい場合、これを共通部分列に採用する
    •  dp\lbrack i+1 \rbrack\lbrack j+1\rbrack \leftarrow dp\lbrack i \rbrack\lbrack j\rbrack + 1

今回の問題の条件は部分列に求められる条件が少し厳しくなっていて、 K 個の連続部分文字列として抜き出す必要があります。

 K の値が小さいことに注目して、DPの添字として「これまで連続部分列を何個使ったか」の添字  k を加えましょう。この  k は新しい連続部分列を始める時に1増やすことにします(終わるときでも良いです)。

DPの中での  k の増え方は以下のように考えられます。

  • 文字を1つも採用していない時、あるいはいったん「採用せずに無視する」遷移によって途切れた後に新しい連続部分列を始めると、必ず  k が1増える。
  • 文字を採用した直後の遷移でまた文字を採用する場合は、前の連続部分列にくっつける( k が増えない)か、新しい連続部分列を始める( k が1増える)かを選ぶことができる。

これらを区別するためには、「最後に見たところの文字を採用したか」のフラグがあれば良いです。

つまり、最終的にDPの状態は以下のように定義すると上手くいきます。

 dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack\lbrack l \rbrack:文字列  s i-1 文字目までと  t j-1 文字目までを見て、これまでに連続部分列を  k 個使っていて、最後に見たところの文字を採用した  (l=1)/採用していない  (l=0) 時の、長さ合計の最大値

遷移も通常のLCSのDPを以下のように応用すれば良いです。

  • 遷移後の  l の値を、文字を採用せずに無視する遷移では  l=0 、文字を採用する遷移では  l=1 とする。
  •  l=0 の状態から  l=1 の状態に遷移する時には  k を1増やす。
  •  l=1 の状態から  l=1 の状態に遷移する時には、 k を1増やす場合と増やさない場合の2つの遷移を行う。

最終的には  dp\lbrack n\rbrack\lbrack m\rbrack\lbrack K\rbrack\lbrack 0\rbrack dp\lbrack n\rbrack\lbrack m\rbrack\lbrack K\rbrack\lbrack 1\rbrack のうち大きいほうが答えになります。

ACコード

Submission #63993107 - Codeforces

AtCoder Beginner Contest 144 E - Gluttony

E - Gluttony

解法

この問題はいくつか考察ステップが必要なので、順に見ていきましょう。

記法などについて

簡単のため、入力として与えられる値の集合  \lbrace A_{1}, ..., A_{N} \rbrace を単に  A \lbrace F_{1}, ..., F_{N} \rbrace を単に  F と書くことにします。

また、最小化すべき値である「メンバーと食べ物の組み方を決めた時の、積  A_{i}F_{i} の最大値」を単に「スコア」と書くことにします。

最適なメンバーと食べ物の組み方

まず修行のことは忘れましょう。

メンバーの消化コスト  A と食べ物の食べにくさ  F が与えられた時、どのように組めばスコアを小さくできるでしょうか。感覚的には大きい値同士を組ませると超大きい値ができるので悪手であり、大きいものと小さいもの、小さいものと大きいものを組ませたほうが良いような気がします。

これは実際に正しくて、 A を小さい方から順に、 F を大きい方から順に並べて組ませるのが最適になります。証明してみましょう。

f:id:betrue12:20191030005215p:plain

最適性の証明

このような並べ方や組み方の最適性を証明するテクニックとして、「このような組み方になっていないものは、ある所を組み替えることで得をする(または損しない)」ということを示す方法があります。

図のように、まず  A を昇順にソートして固定します。この下に  F をどう並べるかを考えます。インデックスは、並べた順番に振り直すことにします。

f:id:betrue12:20191030005633p:plain

もし上の図のように  F が降順に並んでいないとします。このときには、 A_{i} \le A_{j} かつ  F_{i} \lt F_{j} であるようなペア  i とペア  j が必ずどこかに存在しているはずです。上の図でいうと  2, 3 です。

このとき常に  A_{i}F_{i} \lt A_{j}F_{j} が成り立つので、最大値を考える上で  A_{i}F_{i} は無視できます。つまりスコアを  S とすると

 S = \max\left(A_{j}F_{j}, (他のペアたちの値...)\right)

となります。

この  F_{i} F_{j} を入れ替えてみましょう。この時のスコアを  S^{\prime} とすると

 S^{\prime} = \max\left(A_{i}F_{j}, A_{j}F_{i}, (他のペアたちの値...)\right)

となります。 A_{i}F_{j} A_{j}F_{i} のどちらが大きいかは場合によりますが、これらはどちらも  A_{j}F_{j} 以下です。他のペアたちの値は変わらないので、

 S \ge S^{\prime}

が常に成立します。これはつまり、 F が降順に並んでいないならば、 A_{i} \le A_{j} かつ  F_{i} \lt F_{j} であるような  F_{i}, F_{j} を選んでスワップすることで、得をするか損をしないように必ず組み方を変更できるということを意味します。

そしてこの操作ができなくなるまで繰り返すと、どのような並び方からスタートしてどう操作をしても、最後には  F が降順にソートされた状態になります。これはつまり  F が降順にソートされた状態が、他の全ての並べ方よりも得をするか損をしないこと、つまり最適であることを意味します。

修行で  A が変化する場合は?

修行のことを思い出しましょう。

修行前の  A を昇順に並べてペアを決めたとします。ここでもし修行によって大小が逆転すると、最適な組み方が変わってしまいます。

ただしこれは気にしなくて良いです。大小が逆転するような修行の割り振りは、以下のように同じ値で大小が逆転しないような割り振りに置き換えることができるからです。

f:id:betrue12:20191030010728p:plain

答えを求める

いよいよ答えを求めます。これまで見てきたように、ペアの組み方は修行前の  A を昇順に、 F を降順にしたものだけを考えれば良いです。

もし修行回数  K が少なければ、例えば「今  A_{i}F_{i} が最も大きい組を選んで修行させる」ことを  K 回繰り返して最大値がどこまで落ちるか調べることで答えを求められます。ですが今回は  K \le 10^{18} なので厳しいです。

発想を逆転させましょう。ある目標スコア  X を決めて、

 \max A_{i}F_{i} \le X とするための合計修行回数はいくつか?

を求めるような問題を考えます。この場合は全ペアについて  A_{i}F_{i} \le X となればよいので、メンバー  i A_{i} の目標値は  \lfloor\frac{X}{F_{i}}\rfloor です。初期値が目標値以下である場合は修行不要で、目標値より大きい場合はその差がそのまま必要修行回数となります。その合計は  O(N) で求められます。

そしてこれは二分探索ができる形になっています。目標スコア  X を小さくするほど必要な修行回数は多くなり、単調性があるからです。つまり判定問題を

ある固定した値  X について、 \max A_{i}F_{i} \le X とするための合計修行回数は  K 以下か?

として二分探索をすることで、答えを求めることができます。その判定方法は先ほど書いたように、メンバー  i A_{i} の目標値を  \lfloor\frac{X}{F_{i}}\rfloor として、初期値がこれより大きいものについてその差を合計し、 K 以下であるか調べれば良いです。

まとめ

この問題で用いた方法はかなりの頻出テクニックで、覚えておくと役に立つ可能性大です。

  • 要素の組み合わせ方・並べ方について、「ある規則でソートするとそれが最適になっている」という場合がある。
    • その証明テクとして、「そうなっていないものはあるところを入れ替えると必ず改善できる」という手法を使うことが多い。
    • こういうソート規則が使えない問題ではDP等に頼ることになります
  • 「最大値を最小化する」という問題では二分探索が使えることが非常に多い。
    • 最大値を  X 以下にする = 全ての要素を  X 以下にする
    • 目標値を固定することで、そのために必要な操作回数などが簡単な計算で求まったり、貪欲法が使えたりする。
    • 過去記事にもまとめています

ACコード

Submission #8161840 - AtCoder Beginner Contest 144