ABC117 参加記録＆解説（C, D）

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

f:id:betrue12:20190203232047p:plain

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

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

解法

※一番下を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というほど大袈裟なものではないですが、大切なのは

上位の桁（今回はビット）から決めていく
「 $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

これをまとめると、

ビット目まででがよりも小さいことが確定していない状態から遷移するとき…
- もしのビット目が1であれば…
  - $X$ の $d$ ビット目として1を採用すると、そのまま確定していない状態に遷移する。
  - $X$ の $d$ ビット目として0を採用すると、確定している状態に遷移する。
- もしのビット目が0であれば…
  - $X$ の $d$ ビット目としても0を採用するしかない。そのまま確定していない状態に遷移する。
ビット目まででがよりも小さいことが確定している状態から遷移するとき…
- $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ビット整数型でオーバーフローが起こってしまう可能性があるので、そこは注意です。