ARMERIA

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

ABC117 参加記録&解説(C, D)

2WAを出して169位…今回は良くなかったですね。

f:id:betrue12:20190203232047p:plain

取り急ぎC, Dの解説を。あとで書き直すかもしれません。→書き直しました(02/04)

C - Streamline

C - Streamline

解法

※訪れるべき地点  X_{i} のことを「目的地」と書くことにします。

コマ数  N が訪れるべき目的地の数  M 以上である場合、全ての目的地に最初からコマを置けるので答えは0です。

そうでない場合、まず  N 個のコマはそれぞれ異なる目的地の上に置くべきです。そうすると最初にコマを置けない目的地が  M - N 個あるため、「既にどこかの目的地に置いてあるコマを、まだ訪れていない目的地まで移動する」という操作を  M - N 回繰り返す必要があります。

1回の操作ではコマが目的地と目的地の間を移動します。各操作における移動距離の合計を最小化したいので、できるだけ近い目的地の間でコマを運ぶようにしたいです。そう考えると、隣り合う目的地と目的地の間の距離を全部調べて、その中から必要な操作回数と同じ  M - N 個を短いほうから選ぶ、という発想ができます。

実際にこの  M - N 個の区間を選んで以下のようにコマの初期位置と動き方をすると、これらの区間合計が移動距離の合計となり、これが最適です。

f:id:betrue12:20190203232945p:plain

ACコード

Submission #4161130 - AtCoder Beginner Contest 117

D - XXOR

D - XXOR

解法

※一番下を0番目として、下から  d 番目のビットを単に「  d ビット目」と書くことにします。 d ビット目は  2^{d} の位に相当します。

 f(X) に加算される値をビットごとに考える

ビット単位のXORなので、  f(X) に加算される値をビットごとに分解して考えます。

与えられた  N 個の  A_{i} についてそれぞれの  d ビット目を全部見て、0であるものが  n_{d, 0} 個、1であるものが  n_{d, 1} 個あったとします。このとき

  •  X d ビット目を0にすると、  A_{i} それぞれの  d ビット目はそのままなので、  n_{d, 1} \times 2^{d} f(X) に加算される。
  •  X d ビット目を1にすると、  A_{i} それぞれの  d ビット目が全て反転するので、  n_{d, 0} \times 2^{d} f(X) に加算される。

となります。このうち大きいほうを採用していきたいですが、 X \le K という条件により  X の各ビットは自由に決めることが出来ません。またビットごとに独立に決めていくことも無理そうです。

桁DPとは

このように「ある値  X の各桁の値に注目して最適値探しや数え上げを行う。ただし  X には上限がある。」という形式の問題を解く有効な方法として「桁DP」というものがあります。

桁DP入門 - ペケンペイのブログ

これは「上から○桁目まで見て、その途中の状態が○○であるようなものの個数/最大値/最小値など」を状態に持って、桁を1つずつ進みながらDPをしていくものです。「桁」というのは10進数の桁であることが多いですが、今回のような2進数でももちろん使えます。

今回は桁DPというほど大袈裟なものではないですが、大切なのは

  1. 上位の桁(今回はビット)から決めていく
  2.  X が上限  K よりも小さいことが確定しているか?」をフラグとして持った状態を考える

ということです。特に2について詳しく説明していきます。

 X のビットを上から決めていく場合、 X K を超えてしまうのは下の図のようなときです。今まで見たビット全てにおいて  X K が一致していて、 K のビットが0である場合、 X のビットとしてはどんなに損でも0を選ぶしかありません。

f:id:betrue12:20190204201311p:plain

一方、今まで見てきたビットのどこかで「 K が1なのに、 X が0である」という選び方をしたとします。そうすると上位ビットで  X のほうが小さくなっているため、その先  X の各ビットをどのように決めても  X \lt K が保証されます。これが「 X K よりも小さいことが確定している」状態です。

f:id:betrue12:20190204201544p:plain

これをまとめると、

  •  d+1 ビット目までで  X K よりも小さいことが確定していない状態から遷移するとき…
    • もし  K d ビット目が1であれば…
      •  X d ビット目として1を採用すると、そのまま確定していない状態に遷移する。
      •  X d ビット目として0を採用すると、確定している状態に遷移する。
    • もし  K d ビット目が0であれば…
      •  X d ビット目としても0を採用するしかない。そのまま確定していない状態に遷移する。
  •  d+1 ビット目までで  X K よりも小さいことが確定している状態から遷移するとき…
    •  X d ビット目は自由に選んで良いので、 f(X) への加算値が大きくなる方を取り、確定している状態に遷移する。

「遷移前で確定しているかどうか」「 K のビットは何か」「  X のビットとして何を選ぶか」の3条件があり、入れ子になっていてややこしいかもしれませんね。1つ1つのパターンそれぞれについて、どうしてそうなるのか考えてみるのが良いと思います。

これが桁DPの基本となる思考パターンで、10進数の場合でも選択肢は多くなりますが考え方は同じです。あとはこれをDPの実装に落とし込めば解くことができるので、続きはコードを参照していただければと思います。

ACコード

Submission #4173561 - AtCoder Beginner Contest 117

※桁DPに見えるような実装に差し替えました。

実装について少し補足です。

  • 制約の  10^{12} 2^{40} より小さいので、39ビット目から順に見るようにしています。
  • 最大化問題なので、初期状態以外のDPテーブルは  -\infty で初期化したいです。この実装だと合計で最悪  N \times 2^{39+1} くらいの値が足されてくるので、実装上の  \infty はそれより大きい値としておく必要があります。あまり上のビットから回し始めると  -10^{18} で初期化しても足りなかったり、そもそも計算途中の値で64ビット整数型でオーバーフローが起こってしまう可能性があるので、そこは注意です。