ABC117 参加記録&解説(C, D)
2WAを出して169位…今回は良くなかったですね。
取り急ぎC, Dの解説を。あとで書き直すかもしれません。→書き直しました(02/04)
C - Streamline
解法
※訪れるべき地点 のことを「目的地」と書くことにします。
コマ数 が訪れるべき目的地の数 以上である場合、全ての目的地に最初からコマを置けるので答えは0です。
そうでない場合、まず 個のコマはそれぞれ異なる目的地の上に置くべきです。そうすると最初にコマを置けない目的地が 個あるため、「既にどこかの目的地に置いてあるコマを、まだ訪れていない目的地まで移動する」という操作を 回繰り返す必要があります。
1回の操作ではコマが目的地と目的地の間を移動します。各操作における移動距離の合計を最小化したいので、できるだけ近い目的地の間でコマを運ぶようにしたいです。そう考えると、隣り合う目的地と目的地の間の距離を全部調べて、その中から必要な操作回数と同じ 個を短いほうから選ぶ、という発想ができます。
実際にこの 個の区間を選んで以下のようにコマの初期位置と動き方をすると、これらの区間合計が移動距離の合計となり、これが最適です。
ACコード
Submission #4161130 - AtCoder Beginner Contest 117
D - XXOR
解法
※一番下を0番目として、下から 番目のビットを単に「 ビット目」と書くことにします。 ビット目は の位に相当します。
に加算される値をビットごとに考える
ビット単位のXORなので、 に加算される値をビットごとに分解して考えます。
与えられた 個の についてそれぞれの ビット目を全部見て、0であるものが 個、1であるものが 個あったとします。このとき
- の ビット目を0にすると、 それぞれの ビット目はそのままなので、 が に加算される。
- の ビット目を1にすると、 それぞれの ビット目が全て反転するので、 が に加算される。
となります。このうち大きいほうを採用していきたいですが、 という条件により の各ビットは自由に決めることが出来ません。またビットごとに独立に決めていくことも無理そうです。
桁DPとは
このように「ある値 の各桁の値に注目して最適値探しや数え上げを行う。ただし には上限がある。」という形式の問題を解く有効な方法として「桁DP」というものがあります。
これは「上から○桁目まで見て、その途中の状態が○○であるようなものの個数/最大値/最小値など」を状態に持って、桁を1つずつ進みながらDPをしていくものです。「桁」というのは10進数の桁であることが多いですが、今回のような2進数でももちろん使えます。
今回は桁DPというほど大袈裟なものではないですが、大切なのは
- 上位の桁(今回はビット)から決めていく
- 「 が上限 よりも小さいことが確定しているか?」をフラグとして持った状態を考える
ということです。特に2について詳しく説明していきます。
のビットを上から決めていく場合、 が を超えてしまうのは下の図のようなときです。今まで見たビット全てにおいて と が一致していて、 のビットが0である場合、 のビットとしてはどんなに損でも0を選ぶしかありません。
一方、今まで見てきたビットのどこかで「 が1なのに、 が0である」という選び方をしたとします。そうすると上位ビットで のほうが小さくなっているため、その先 の各ビットをどのように決めても が保証されます。これが「 が よりも小さいことが確定している」状態です。
これをまとめると、
- ビット目までで が よりも小さいことが確定していない状態から遷移するとき…
- もし の ビット目が1であれば…
- の ビット目として1を採用すると、そのまま確定していない状態に遷移する。
- の ビット目として0を採用すると、確定している状態に遷移する。
- もし の ビット目が0であれば…
- の ビット目としても0を採用するしかない。そのまま確定していない状態に遷移する。
- もし の ビット目が1であれば…
- ビット目までで が よりも小さいことが確定している状態から遷移するとき…
- の ビット目は自由に選んで良いので、 への加算値が大きくなる方を取り、確定している状態に遷移する。
「遷移前で確定しているかどうか」「 のビットは何か」「 のビットとして何を選ぶか」の3条件があり、入れ子になっていてややこしいかもしれませんね。1つ1つのパターンそれぞれについて、どうしてそうなるのか考えてみるのが良いと思います。
これが桁DPの基本となる思考パターンで、10進数の場合でも選択肢は多くなりますが考え方は同じです。あとはこれをDPの実装に落とし込めば解くことができるので、続きはコードを参照していただければと思います。
ACコード
Submission #4173561 - AtCoder Beginner Contest 117
※桁DPに見えるような実装に差し替えました。
実装について少し補足です。
- 制約の が より小さいので、39ビット目から順に見るようにしています。
- 最大化問題なので、初期状態以外のDPテーブルは で初期化したいです。この実装だと合計で最悪 くらいの値が足されてくるので、実装上の はそれより大きい値としておく必要があります。あまり上のビットから回し始めると で初期化しても足りなかったり、そもそも計算途中の値で64ビット整数型でオーバーフローが起こってしまう可能性があるので、そこは注意です。