ARC103 参加記録＆解説（C～E）

AtCoder Regular Contest 103 - AtCoder

結果はCE2完+D部分点で73位。黄色復帰！

今回、この獲得点数の人が180人くらいいたので、スピードも功を奏したと思います。

f:id:betrue12:20180930102724p:plain

C～Eを振り返ります。

C - /＼/＼/＼/

↑半角バックスラッシュが円マークになるので全角にしました…

C - /\/\/\/

解法

偶数番目と奇数番目に分けて考えます。変更個数を少なくするためには、それぞれ元から一番多かった数字を残したくなります。

一番多かった数字が異なっていれば、それらをそのまま採用できます。もし同じ数字だった場合は 数列に現れる数はちょうど2種類 という条件に反しないよう、片方を諦めて2番手にする必要があります。「奇数1番手+偶数2番手」と「奇数2番手+偶数1番手」の両方を試して、登場回数合計の多い（＝変更が少ない）ほうを採用します。

ACコード

D - Robot Arms

解法

必要条件を導出する

まず、解が存在する必要条件を考えます。いったん $x$ と $y$ の区別をなくし、「それぞれの腕が正負どちらの方向に伸びているか？」を考えます。これを符号付きで全部足し算したものが、最終到達地点の座標を足したもの、つまり $X_{i} + Y_{i}$ となります。

ある腕を、負から正に変更したとします。その腕の長さを $d_{i}$ とすると、 $-d_{i}$ だったものが $+d_{i}$ になるため、最終地点の座標の和は $+2d_{i}$ 加算されます。逆に正から負に変更した場合は $-2d_{i}$ です。

より一般的に言うと、腕の正負を入れ替えた時、その長さの2倍だけ座標和が変動します。奇数の長さで変動することはありません。つまり作らなければいけない最終到達地点 $(X_{1}, Y_{1}), ..., (X_{N}, Y_{N})$ について座標和を考えると、それらの差は全て偶数である、言い換えると偶奇が一致している必要があります。

まずこれが必要条件になります。

構成方法を考える

では、構成方法を考えましょう。作りたいパターン数が $N \le 1000$ というのはそこまで多い数ではないですが、何と使える腕の本数が $m \le 40$ しかありません。1つ1つのパターンを見て腕の長さを決めていく方法は無理そうです。どんな数でも作れる「必勝法」を考えたいです。

「どんな数でも作れる」の定石は $n$ 進数です。2進数を使うとすると、作りたい座標は $0 \le |X_{i}|, |Y_{i}| \le 10^{9} \fallingdotseq 2^{30}$ であり、腕40本でも足りそうな雰囲気です。ただ、 $x, y$ をそれぞれ作るとなると、それぞれに腕が30本必要そうに見えますし、不必要な腕をどう調整するかも難しく思えます。

ではどうすればいいかというと、 $x, y$ を それぞれ作る をやめて、同時に作る ようにします。1本の腕の方向を選ぶことで $x, y$ 両方の値を操作できれば、腕の数が足りそうです。もちろんこのままでは無理ですが、それを可能にするのが座標変換です。

$u = x+y, v = x-y$ として、 $uv$ 座標系を考えます。これは、座標平面を45度回転しているような変換です。

f:id:betrue12:20180930114650p:plain

このように変換すると、腕の4方向が「 $u$ と $v$ それぞれ、正負どちらの方向にはたらくか」の4通りに対応します。2つの値を同時に操作することができて、かつ「 $u$ は増やしたいけど $v$ は減らしたい」みたいな要求4パターン全てに対応できるのが嬉しいポイントです。

目的地の座標も変換して $(U_{i}, V_{i})$ と書くことにします。そうすると $0 \le |U_{i}|, |V_{i}| \le 2\times 10^{9} \fallingdotseq 2^{31}$ と値の範囲が変わりますが、腕は40本あるので大丈夫です。各腕に $1, 2, 4, 8, ..., 2^{30}$ を割り振って、これらの足し算引き算だけで目的の値を作ることを考えます。

普通の0 or 1の2進数とは違い、-1 or 1の2進数（？）となっていますが、以下のように「大きい方から選ぶ」ことを考えればよいです。

f:id:betrue12:20180930115950p:plain

常に目的の値に近づく方向に正負を採用していけば、最後は目的の値に辿り着きます。実際には目的の値が「3」のような小さな数のときでも、もっと大きな値を組み合わせて作ることになりますが、その場合でも考え方は同じです。

ただしこれがキレイに収まるのは $U_{i}, V_{i}$ が奇数の場合で、偶数の場合は最後にもう1つ1を付けて調整してあげる必要があります。

※ $U_{i}$ と $V_{i}$ の偶奇は一致するため、片方では追加で1が必要だけどもう片方では余計、という事態にはならないので安心です。

f:id:betrue12:20180930120955p:plain

これで解けました。解法をまとめると、

まず目的地の座標和の偶奇が一致しているかチェック。一致していなければ解なしで終了。
座標変換を行う。
腕の長さとして $2^{30}, ..., 4, 2, 1$ の値を用意する。目的地の座標和が偶数の場合、さらに1を足す。
それぞれの目的地ごとに、大きい方の腕から方向を決めていくことで目的の値を作る。

これで解けます。

ACコード

（C++）Submission #3305898 - AtCoder Regular Contest 103

※部分点解法は、全部の腕の長さを1にしても足りるので、偶奇チェックした後は全部1で作ります。部分点獲得コードはこちら。

E - Tr/ee

解法

必要条件を導出する

これも、まず必要条件を考えます。

サイズ1の連結成分は必ず作れる。葉だけを切断するとサイズ1の連結成分になるため。
サイズ $n$ の連結成分は必ず作れない。サイズ $n$ の木を切断するとそれぞれの部分木のサイズは $n$ 未満になるため。
サイズ $i$ の連結成分が作れるならば、サイズ $n-i$ の連結成分も作れる。切断によってサイズ $i$ の連結成分ができたとき、もう片方はサイズ $n-i$ になっているため。