AtCoder Grand Contest 027

AtCoder Grand Contest 027

A - Candy Distribution Again

• $N$ 人の子供に $X$ 個のお菓子を余りなく配る
• 子供たちは、それぞれ $a_1,a_2,...,a_N$ 個のお菓子をちょうどもらった時のみ喜ぶ
• 喜ぶ子供の数を最大化せよ

なるべく少ないお菓子で喜ぶ無欲な子供を優先的に喜ばせる。欲張りな子供は後回しにされちゃうのだ。世知辛いね。

足りなくなったら終わり。

全ての子供に配れた時が注意で、お菓子は「余りなく」配らないといけない。もし余りがあったら誰か1人に押し付ける。その子は喜ばなくなるが、$N-1$ 人は喜ぶ。

B - Garbage Collector

• 直線上に $N$ 個のゴミが落ちているのを、お掃除ロボがゴミ箱に回収する
  • ゴミは座標 $0 \lt x_1 \lt x_2 \lt ... \lt x_N \lt 10^9$ に落ちている
  • ゴミ箱は座標0にあり、動かせない
  • お掃除ロボは座標0からスタートする
  • 拾ったゴミをゴミ箱以外の場所にいったん置くことはできない
• お掃除ロボは、ゴミを拾う時と、ゴミ箱に捨てる時に、$X$ のエネルギーを消費する
  • まとめて捨てても $X$ 固定
• お掃除ロボは、$k$ 個のゴミを持っている時、座標を1移動するのに $(k+1)^2$ のエネルギーを消費する
• 全てのゴミの回収にかかるエネルギーを最小化せよ

少し問題の把握が難しい。

• 一度にたくさんのゴミを拾って帰ると、1移動するためのエネルギーは大きくなるが、移動距離、ゴミ捨ての回数は少なくなる
• 少しずつ拾って帰ると、移動エネルギーは小さくなるが、移動距離は伸び、ゴミ捨ての回数は増える

まず、往復1回で全てのゴミを回収しようとするとどうなるか考える。往復とは、座標0を出発し、いくつかのゴミを回収し、座標0に戻ってきてゴミ箱に捨てる一連の動作を示す。

この場合、一度に多くのゴミを持ったまま長い距離を動きたくは無いので、出来るだけ遠いゴミを身軽な時に拾った方がよい。

よって、右から拾っていくのが良いと分かる。

ゴミを拾う・捨てる際のエネルギーは後でまとめて計算できるため省いて、移動距離だけ考えると、

0     g1        g2      g3       g4  (座標を表す文字がxだと紛らわしいので以下gを用いる)
|-----*---------*-------*--------*

お掃除ロボの動き            エネルギー x 移動距離
|-------------------------------->   1 x g4
|                        <--------   4 x(g4-g3)
|                <------             9 x(g3-x2)
|      <---------                   16 x(g2-g1)
|<-----                             25 x g1

このエネルギーを、各gについてまとめると、

• g4: 1+ 4 = 5
• g3: 9- 4 = 5
• g2: 16- 9 = 7
• g1: 25-16 = 9

移動エネルギーは $5g_4+5g_3+7g_2+9g_1$ となる。

最初の1項以外は隣り合う平方数の差＝奇数列なので、この係数列は $5,5,7,9,11,13,...$ と続く。これらを頭からそれぞれ $g_4, g_3, g_2, g_1$ にかけた結果が、移動に必要とするエネルギーとなる。

各ゴミの座標に係数をかけるだけで移動エネルギーが求められる、ということがポイント。

0     g1        g2      g3       g4
|-----*---------*-------*--------*
      9         7       5        5

では、複数回の往復に分けての回収を考える。仮に往復回数が決まっていて、全てのゴミを2回で回収するとする。

1回1回の往復の移動エネルギーは、ゴミの座標に決まった係数をかけるという先ほどの考えが適用できる。

各往復で拾うゴミの個数は、出来るだけ均等に分けた方がよい。

            g1     g2   g3   g4      g5     g6
      |-----*------*----*----*-------*------*

        こんな割り振りがあったら
1回目 |-----9------7----5----5
2回目 |------------------------------5------5
        ↓こっちの方が良い
1回目 |------------7----5----5
2回目 |-----7------------------------5------5
        g1の係数が9から7に軽減

往復回数が $r$ 回と決まっていたら、以下のように係数を割り振るのが最適となる。

• 座標の大きい方から $2r$ 個は係数5
• 次に大きい $r$ 個は係数7
• 次に大きい $r$ 個は係数9
• …

ゴミの位置
|--*-*-*-*-*-*-*-*-*-*-*-*-*
r=3
|-11-----9-----7-----5-----5
|------9-----7-----5-----5
|----9-----7-----5-----5
r=4
|--9-------7-------5-------5
|--------7-------5-------5
|------7-------5-------5
|----7-------5-------5

（なるほど貪欲に右から拾っていくとWAになるはずだわ）

ここまでわかれば、$r$ について、$1～N$ まで全探索すれば良い。（実際には、ゴミがどこにあろうと少なくとも1往復に2個は拾って損はしない計算になるので、$N/2$ まででよい）

往復回数が $r$ 回ならゴミ捨てにかかるコストは $rX$、また往復回数にかかわらず、ゴミを拾うコストは $NX$。これらを忘れないように足す。

扱う数が大きいのでオーバーフローの問題があるらしいが、Pythonはそういう部分では煩わされずに済む。

C - ABland Yard

• $N$ 頂点 $M$ 本の無向グラフ
  • グラフは連結とは限らず、多重辺や自己ループを含みうる
• 各頂点には文字 $s_i$ が書かれている
  • $s_i$ は'A'または'B'
• このグラフ上を、任意の頂点からスタートし、移動して書いてある文字を順に拾うことで文字列を作る
• 'A'と'B'からなる任意の文字列が作れるかどうか、判定せよ

• A→A
• A→B
• B→A
• B→B

この4つの移動が、常に可能かどうか？

ある文字列（たとえば'AABB'）まで作れたところで、今いる'B'の頂点から'A'に行けなければ、'AABBA…'という文字列は作れない。

つまり、「'A'にも'B'にも行ける頂点だけで、ループが作れるか？」という問題。

Ａ--Ｂ
｜  ｜  こんなんとかOK
Ａ--Ｂ

それ以外の頂点はあっても無くても同じ。

どちらかにしか行けない頂点が不要な理由を説明する。

自身を仮に'B'とする。まず、辺は両方向なので、'…AB'（最後のが説明中の頂点）と作れた時点で、次に'A'に行けることは確実。戻ればよい。

なので、行けないとすれば、'B'。'…ABB'という文字列が作れないことになる。

任意の文字列を作るためには、この他に'…ABB'という文字列を作れる'B'頂点が必要。とすれば、そっちを使えば'A'にも'B'にも行けるのだから、わざわざ最初の頂点を使う必要が無い、ということになる。

これは、自身や、その1つ前のアルファベットを変えても成立する。

よって、どちらかにしか行けない頂点を再帰的に取り除いて、頂点が残れば可能、全て取り除かれると不可能となる。

実装では、各頂点から移動できる頂点を「相手がAかBか」に分けてsetで持ち、いずれかが空なら削除対象とする。自身が削除されると相手のリストから自身を削除し、それによって相手のsetの片方が空になれば、連鎖的に削除対象とする。もっと良い実装はありそうな気がする。

D - Modulo Matrix

• 以下の条件を満たす $N \times N$ の盤面を構築する
  • 全マスに $1 \le a_{ij} \le 10^{15}$ の整数が書かれている
  • 数字は全て異なっている
  • 盤面の、上下左右に隣接するどの2数を取っても、大きい方を小さい方で割った余りは、全て同じ値となる
• $2 \le N \le 500$

解説見れば構築は簡単なんだけど、思いつくかというと……（B問題からそんなんばかりである）

割った余りは、下手に大きくしても無駄なので、1とする。（共通の余りを $d$ とすると、$d$ 以下の数字は盤面に入れられない）

あるマスの周囲にたとえば3と5と7が既に埋まっていると、そのマスには「3と5と7の最小公倍数+1」を入れると、機械的に余りを1に出来る。

まず、市松模様に塗り分けて、黒い方に別々の数を入れ、白い方に周囲の最小公倍数+1を入れると、共通の余りについてはクリア。

■□■□■□
□■□■□■
■□■□■□
□■□■□■
■□■□■□
□■□■□■

$10^{15}$ という制限は、4数が互いに素だった場合、それぞれが $\sqrt[4]{10^{15}}=5623$ くらいで無いと間に合わない。一方、$N$ の制約最大500において、黒いマスの数は12万5000個。互いに異なる数字を入れるので、いくら数字の大小をばらけさせても、これでは何かしらの工夫無しには厳しい。

周囲の4数に、共通する素因数を持つ数を集めるように配置すれば、最大公約数の桁数を抑えられる。

斜め方向に同じ数を入れる。斜め方向の線は $N-1～N$ 本引け、斜めには2方向あるので $2N$ 本の斜めで全て別々の数を入れる。同じマスに入った2数の積を取れば、全ての黒マスを別々にしつつ、白マスの周囲のマスには素因数が2個ずつ共通しているので、最小公倍数も抑えることが出来る。

 2□ 3□ 7□      13□17□19□      26□51□....
□ 2□ 3□ 7      □17□19□23      □34□57....
 5□ 2□ 3□      17□19□23□      85□38□....
□ 5□ 2□ 3  ×  □19□23□29  ＝  □95□46....
11□ 5□ 2□      19□23□29□      ............
□11□ 5□ 2      □23□29□31      ............

       |  34  |
       | 2x17 |
+------+------+------+  中央マス
|  85  |      |  38  |  2x5x17x19 + 1 = 3231
| 5x17 |      | 2x19 |
+------+------+------+
       |  95  |
       | 5x19 |

同じ数が入らないようにするには、素数にすればよい。

1000番目の素数は7919で、これが斜めに入れる素数の最大値。なので、この最大値付近の数字を周囲の素因数に集めてしまうと白マスで $10^{15}$ をオーバーしてしまうが、まぁ意図的にそうしない限り大丈夫。たとえば「＼」方向に小さい方から入れると最大値は500番目の素数で3571。「／」方向に続きから入れると、最大値同士が集まっても、$3571 \times 3571 \times 7919 \times 7919 = 8 \times 10^{14}$ なので $10^{15}$ 以内に収まる。