恒例のARCに参加して、今回もC完でした。

前回も「恒例の」と書いていた ので1週間練習してなかったことになります。なるほど……

AtCoder Regular Contest 103 

問題リスト：

C - /\/\/\/

問題概要：数列 A が与えられる。K 個の要素を変更した。このとき偶数番目の要素 A[2n] はすべて等しい。奇数番目の要素 A[2n + 1] もすべて等しい。しかし A[2n] ≠ A[2n + 1] である。操作回数 K の最小値を求めよ。

解説：書き換える回数を最小化するということは、書き換えない要素の個数を最大化するということです。偶数番目に出現する要素の中で、同じ値のものが最大のものを維持するのがベスト。つまり最瀕値を計算すればOK。

A[2n] = A[2n + 1] となってしまうのは、その数値が偶数番目と奇数番目のどちらにも最も多く出現するときです。この場合はどちらかを諦めて書き換えるしかないです。2番目に多く出現する値を維持するのがベスト。

どちらを諦めるかは、両方試してみればOKです。

提出：

書き損じと min/max の取り違えで2回WAしてしまいました。早解きで順位を上げるのは厳しいので、Dでは部分点をひとまず無視して、満点解法に挑戦……したんですが解けませんでした。部分点は通してます。

D - Robot Arms

問題概要：多関節の腕「ロボットアーム」がある。N 個の点 (X, Y) が与えられる。

1. m (≤40) 個の腕が関節で繋がっている
2. i 番目の腕の長さは d[i] (≤10^12)
3. 関節の角度は90度の整数倍
4. 腕は無限平面上にあり、ロボットアームの始点は原点 (0, 0) に固定されている。
5. 関節の角度を調整して、点 (X, Y) がロボットアームの終点になるようにできる。(関節の角度を一通り決めることを、以下「配置」と呼ぶ。)

条件を満たす m, d と配置の一例を示せ。解がないときはその旨を答えよ。

※平面が小さいケース (|X|, |Y| ≤ 100) を解けば部分点 300 がもらえる。

本番では具体例を試したり当て推量をしてみたりしてましたが、あまり手応えはありませんでした。

実はこれ、数ヶ月前に AtCoderでやって参戦記も書いたやつ とほぼ同じ手順で解けます。こういうのを記憶に刻み込むために参戦機を書いているのに……みたいな感じがある。

解説：最初に明らかなケースを弾きます。アーム全体の長さ Σd と X+Y の偶奇が等しい必要がありますから、X+Y の偶奇が混在しているとダメです。以下、X+Y は奇数とします。(偶数だったら長さ1の腕を追加すればいい。)

腕の本数の上限 40 に対して終点の座標は最大 (10^9, 10^9) なので、長い腕が必要です。終点が原点に近いケースもケアするため、短い腕も必要になります。2進法の出番です。

本番でも、腕の長さを 2^p にすればいいのでは？ と3分ぐらい考えたんですが、腕の本数が足りないと思いました。X方向に移動するのに 10^9 ≒ 2^30 だから30本、Y方向も30本、計60本ぐらい要りそう。実はこれが正解ルートでした。

原点から長さ1の腕を伸ばして到達できる点をプロットし、それらの点から長さ2の腕で到達できる点をプロットし、というのを地道にやっていくと、X+Y が奇数の点は隙間なく覆えることが分かります。

したがって、腕の数と長さを m=32, d = 2^31, 2^30, ..., 2^0 とすればOK。どの点に対しても、そこが終点になるような配置があるようです。

具体的に配置を計算します。これはわりと簡単で、原点から (X, Y) に近づくように貪欲的に選んでいけばいいです。現在地点 (x, y) と (X, Y) の間の距離が縮まるように選んでいけば最終的に 0 になることは、前述の考察から分かっているので。コードだけみると「本当に解けてるの？」ってなるやつ、構成問題にありがち。

提出：

感想

このD問題はオンタイムで解くべきでした。悔しいです。

昼間にやっていたマラソンコンテストについては後日書きます。