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を採用するしかない。そのまま確定していない状態に遷移する。
- もし
ビット目までで
が
よりも小さいことが確定している状態から遷移するとき…
の
ビット目は自由に選んで良いので、
への加算値が大きくなる方を取り、確定している状態に遷移する。
「遷移前で確定しているかどうか」「 のビットは何か」「
のビットとして何を選ぶか」の3条件があり、入れ子になっていてややこしいかもしれませんね。1つ1つのパターンそれぞれについて、どうしてそうなるのか考えてみるのが良いと思います。
これが桁DPの基本となる思考パターンで、10進数の場合でも選択肢は多くなりますが考え方は同じです。あとはこれをDPの実装に落とし込めば解くことができるので、続きはコードを参照していただければと思います。
ACコード
Submission #4173561 - AtCoder Beginner Contest 117
※桁DPに見えるような実装に差し替えました。
実装について少し補足です。
- 制約の
が
より小さいので、39ビット目から順に見るようにしています。
- 最大化問題なので、初期状態以外のDPテーブルは
で初期化したいです。この実装だと合計で最悪
くらいの値が足されてくるので、実装上の
はそれより大きい値としておく必要があります。あまり上のビットから回し始めると
で初期化しても足りなかったり、そもそも計算途中の値で64ビット整数型でオーバーフローが起こってしまう可能性があるので、そこは注意です。