ARMERIA

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

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

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

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

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

これで解けます。

ACコード

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

E - Tr/ee

E - Tr/ee

解法

必要条件を導出する

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

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

入力がこれらの条件に反する場合、条件を満たす木は構築不可能です。

構成方法を考える

サイズの小さいほうから考えていきましょう。根付き木として考えたとき、深いほうから順に構成していきます。

先ほど見たように、サイズ1は必ず作れます。では「サイズ2が作れる」と「サイズ2が作れない」は、どのように差を付ければ良いでしょうか。

f:id:betrue12:20180930123643p:plain

サイズ2を作りたい場合、サイズ2の部分木の上に親を作ればよいです。逆に作りたくない場合は、サイズ2の部分木で親となっている頂点に、さらに子を生やせばよいです。これを繰り返すことで目的の木を作ることができて、もう少し丁寧に書くと

  • 構築している木がサイズ i で、次に i+1 番目の頂点を付ける時に、
    • サイズ  i の連結成分を作りたい場合は、現在親となっている頂点のさらに親に  i+1 番目の頂点を置く。
    • サイズ  i の連結成分を作りたくないときは、現在親となっている頂点の子として  i+1 番目の頂点を置く。

このように構成することができます。以下は「1, 3, 6, ...」が作れる木の例です。

f:id:betrue12:20180930124619p:plain

ACコード

さいごに

Dの満点解法、2進数よりも45度回転の発想のほうが難しいかなと個人的には思いました。さっさと部分点だけ獲得したのは、結果的には正解でした。

木の問題はけっこう好きなので、Eは速く解けたかなと思います。Fも好きなタイプの問題だったので、本番で通せるようになりたい…