ARMERIA

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

AGC027 参加記録

AtCoder プログラミング 競技プログラミング

結果は1完…速かったのでそこまでパフォーマンスは悪くないのですが、前回時点で黄色スレスレだったので色が落ちてしまいました。

f:id:betrue12:20180916041647p:plain

本番後に通したものも含めてA～Cを振り返ります。

A - Candy Distribution Again

A - Candy Distribution Again

解法

要求数が小さい子供から順番に配っていくと良いです。ぴったり配りきれない場合は最後の1人が満足できないので注意。

ACコード

B - Garbage Collector

B - Garbage Collector

解法

本番では「端から i 個回収済みで原点にいるときの最小消費エネルギー」みたいなのでDPをずっと考えていましたが…どうやらそれでは最適でないケースがあるようです。

普通に解法を書くと公式解説とほぼ同じ流れになってしまうので、公式解説で省略されている内容を補足しつつ書いていきます。

移動エネルギーの求め方

まず、普通にゴミをいくつか拾う時の移動エネルギーを考えてみます。

f:id:betrue12:20180916100210p:plain

上図で、 x_{1} ～ x_{3} のごみ全てを1回で回収することを考えます。所持ゴミが多いほどエネルギーが余計にかかるので、なるべく帰り道に拾ったほうがよいです。図のように拾っていくと、移動エネルギーの合計は 5x_{3} + 5x_{2} + 7x_{1} となります。

より一般的に書くと、各項にかかる係数は、

  • 一番右の x の係数は、往路1と復路4の合計で5
  • 右から i 番目（ i \ge 2）の x の係数は、 (i+1)^{2} から i^{2} を引いたものになり、これを計算すると 2i+1 になる

となります。各係数が「そのゴミを何番目に拾うか」だけで決まり、その順番が遅いほど係数が大きくなっているのがポイントです。

往復回数決め打ち全探索

公式解説通り、往復回数を決め打ちして考えます。往復回数を k とします。

このとき、 k 回の往復にゴミを割り当てることになりますが、どのような割り当てが最適でしょうか。

f:id:betrue12:20180916100813p:plain

この図のように、各要素に「ゴミを拾う順番」を割り当てます。 k 回往復するので、1番目に拾うゴミが k 個、2番目に拾うゴミが k 個…というのを割り当てることになりますが、これを右から順番に割り当てていくのが最適となります。

その理由は、直観的にはこう説明できます。前節で見たように、ゴミを拾う順番が遅いほど、そのゴミのための移動エネルギーの係数が大きくなります。より距離が長いほうのゴミに、より大きな係数を掛けてしまうと損です。そのため、遠いゴミほど係数を小さくしたい、つまり早い順番で拾いたい、と考えると上のようになります。

ちゃんと証明しようと思うと、最適でない並べ方と最適な並べ方の移動エネルギーの差分を計算して、不等式で評価して0以上であることを示すんじゃないかと思います。

累積和でまとめて計算

上記の割り当てのもとで、移動エネルギーの合計を計算していきましょう。このとき、拾う順番が同じ要素たちは、

  • 係数が同じ
  • 全て隣り合っている

という特徴があります。そのため、累積和を使ってまとめて計算することができます。

f:id:betrue12:20180916134223p:plain

累積和を事前に計算しておくと、拾う順番の最大値、つまり \lceil \frac{N}{k} \rceil 回の計算で移動エネルギーを求めることができます。これは後で計算量の話の時に使います。

ゴミを拾う・捨てるエネルギー

後回しにしていましたが、ロボットは移動エネルギーの他に、ゴミを拾う・捨てるのにもエネルギーを消費します。

ゴミを拾う回数はゴミの個数と同じ N なので、ゴミを捨てる回数（＝往復回数）が k であるとき、ゴミを捨てる・拾うエネルギーは (N+k)X となります。

解法まとめ

以上で問題を解く材料が揃いました。

  1. x_{i} の累積和を前計算しておく。
  2. 往復回数 k を決め打ち全探索する。
    1. 移動エネルギーは、累積和を使ってまとめて計算する。
    2. 拾う・捨てるエネルギーは (N+k)X で計算できる。
  3. 全探索で一番小さかったものを答えとする。

これで解くことができます。往復回数決め打ちに気付くかどうか…ですね。

補足

計算量についてです。先程見たように、往復回数を k とすると、その時の移動エネルギーは \lceil \frac{N}{k} \rceil 回の計算で求められます。

ちょっと乱暴ですがceilを外して、 \sum_{k=1}^{N} \frac{N}{k} = N\sum_{k=1}^{N} \frac{1}{k} を考えます。この \sum_{k=1}^{N} \frac{1}{k} という式は調和級数という名前が付いていて、だいたい \log(N+1) くらいの値になります（積分で近似計算できます）。そのため、 \sum_{k=1}^{N} \frac{N}{k} = O(N\log N) であることから、移動エネルギーの計算量は全体で O(N\log N) となります。累積和などそれ以外の計算は O(N) なので、問題全体の計算量も O(N\log N) です。

次にオーバーフローについて。すごく極端な例ですが、最も遠い、ほぼ 10^{9} の位置に 2\times10^{5} 個のゴミが密集していて、これを1回で回収することを考えます。そのとき、帰り道の距離はほぼ 10^{9} であり、持っているゴミの個数は 2\times10^{5} 個なので、 4\times10^{19} くらいになってlong longでもオーバーフローします。

ただしこれが答えになることはありません。もし全要素を1個ずつ拾うという動きをした場合、移動エネルギーの合計は 5\sum_{i} x_{i} 、ごみを拾う・捨てるエネルギーの合計は 2NX となり、この値は制約から計算すると 1.4 \times 10^{15} 未満です。なのでそれぞれの往復回数について移動エネルギーを計算しているときにも、この値を超えた時点でもう最適解にはなり得ないので、計算途中で打ち切ってしまって構いません。このようにするとオーバーフローを回避することが出来ます。

ACコード

※（2019/03/14）C++のコードのオーバーフロー回避方法がマズかったので差し替えました。

C - ABland Yard

C - ABland Yard

公式解説の方法がだいぶ天才感あるので、まずはイメージしやすい頂点削除の解法を書いていきます。

解法1：頂点削除

「任意の文字列を作れる」ということは、「次にAにもBにも遷移できる」という状態を永遠に続けられることを意味します。

そのため、グラフ内に「次にAとBのどちらかにしか遷移できない」もしくは「どこにも遷移できない」という頂点が存在する場合、その頂点は「入ってはいけない頂点」ということになります。

f:id:betrue12:20180916114429p:plain

このような「入ってはいけない頂点」は、文字列を構成する上で使えないので、グラフから消してしまいます。そのとき、繋がっている辺もろとも消します。

そうすると辺を消したことで、他の頂点の遷移先が減ります。これにより他の頂点が「次にAとBのどちらかにしか遷移できない」という状態になってしまうと、その頂点も使えなくなります。こうして連鎖するように、頂点が消えていく可能性があります。

f:id:betrue12:20180916115137p:plain

上のグラフではその後、連鎖的に全ての頂点が消えてしまいます。そうなってしまった場合、答えはNoです。

一方、全部の頂点の削除判定を全て済ませてなお生き残った頂点がいる場合、それらの頂点は全て「次にAにもBにも遷移できる」頂点なので、その頂点を辿っていくことで任意の文字列を作ることができます。その場合、答えはYesです。

頂点の削除判定は、各頂点ごとに「A、Bに遷移する辺がそれぞれいくつあるか」を管理して、辺を消すごとに1引いていくと楽です。どちらかが0になったら削除します。

解法1：ACコード

解法2：AABB法

解法1で見てきたように、「任意の文字列を作れる」ということは、「次にAにもBにも遷移できる」という状態を永遠に続けられることを意味します。

仮に与えられたグラフで、「AABBAABBAABB…」という文字列を無限に続けられるとします。このとき、グラフが無向グラフなので、その経路内の任意の点はAにもBにも遷移できていることになります。この経路を前に進むか、後ろに戻るかで、異なるアルファベットに遷移できます。

※「端点は？」という話はありますが、一方が無限に続いているので、無限に遠いところ（具体的には、作りたい文字列の長さを超えるところ）からスタートすれば端点に届くことはありません。

f:id:betrue12:20180916121833p:plain

逆にこの文字列が作れないときに「任意の文字列を作れる」と言えないことは当たり前なので、「AABBAABB…」という文字列を無限に続けられるかどうかを考えれば、それが任意の文字列を作れることの必要十分条件になっています。

では、「AABBAABB…」という文字列を無限に続けられる条件を考えます。それぞれの「AABB」のうちの最初のAを「1つ目のA」と呼ぶことにします。頂点数は有限なので、この「AABBAABB...」を続けていくと、必ずどこかで「1つ目のA」が重複するはずです。なので、「1つ目のA」が重複している経路がない場合は「AABBAABB…」の無限経路が存在しないことになりますし、逆に重複していればその経路をぐるぐる回り続けることができます。

これで必要十分条件を「AABB...を繰り返す経路で、「1つ目のA」が重複しているものが存在する」まで落とし込めました。これを解くにあたって、「1つ目のA」と「2つ目のA」を分けて考えたくなります。そのため、AもBも1つ目と2つ目で分けて、頂点数を2倍にすることを考えます。

元のグラフは無向グラフでしたが、

  • 1つ目のAからは2つ目のAに
  • 2つ目のAからは1つ目のBに
  • 1つ目のBからは2つ目のBに
  • 2つ目のBからは1つ目のAに

だけ、それぞれ遷移するような有向グラフに変換します。この有向グラフにおいて閉路が存在すれば、それがAABB...を繰り返す経路で「1つ目のA」が重複しているものになります。

f:id:betrue12:20180916123714p:plain

このグラフで閉路が存在するかどうかを判定すれば、この問題が解けます。

解法2：ACコード

さいごに

大変な回でした…本番中はほぼ全ての時間をB問題のDPと戦うのに費やしていました。

次は黄色復帰を目指します！