AtCoder Regular Contest 109 B,C,D,E問題メモ

AtCoder Regular Contest 109

B - log

問題

$N+1$ 本の丸太が売られている
- それぞれの長さは $1,2,3,...,N,N+1$
- 値段は全て1円
$1,2,...,N$ の長さの丸太を1本ずつ揃えたい
丸太は、切ることで合計長の等しい複数の丸太にできるし、余ったら捨ててもよい
最小費用を求めよ
$1 \le N \le 10^{18}$

解法

長さ $N+1$ の丸太を買わないことには、他の全ての丸太を買うしかないので、これをどう使うか。
丸太の値段は長さに依らず等しいので、なるべく多くの丸太に分割したい。

小さい方から $1+2+3+...+k \le N+1$ となる $k$ 本の丸太を $N+1$ の丸太1本で賄える。

$\dfrac{k(k+1)}{2} \le N+1$ より、$k \lt \sqrt{2N+2}$ なので、とりあえず平方根を切り捨てで取って、そこから条件を満たさない場合は1減らせばよい。

Python3

n = int(input())
k = int((2 * n + 2) ** 0.5)

if k * (k + 1) > 2 * n + 2:
    k -= 1

print(n - k + 1)

C - Large RPS Tournament

問題

$2^N$ 人のじゃんけんトーナメントを行う
全ての参加者は全試合を通して各々に決められた手を出し続ける
- 各人の出す手は文字列 $S$ で与えられる
- トーナメント表で左から $i$ 番目の人は、$S$ を無限回繰り返した文字列の $i$ 番目の文字が 'R','P','S' ならそれぞれグー、パー、チョキを出す
あいこの場合はトーナメント表で左の参加者が勝ち上がる
優勝者の出し続けた手を答えよ
$1 \le N \le 100$
$1 \le |S| \le 100$

解法

参加者がとてつもない人数になるが、$S$ が短いので、かなりの試合は同じ展開になる。

具体的には、「$2^d$ 人が参加するトーナメントで、左端の人の手が $S_i$」としたときの $(d,i)$ の組が同じであれば、展開は全く同じになり、優勝者も同じになる。

この組数は $N|S|=10^4$ 通りくらいしか無いので、メモ化再帰で求めればよい。

Python3

import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 6)


@lru_cache(maxsize=None)
def winner(i, d):
    if d == 0:
        return s[i]

    l = winner(i, d - 1)
    r = winner((i + pow(2, d - 1, n)) % n, d - 1)
    if l == r:
        return l
    if l > r:
        l, r = r, l
    if l == 0 and r == 1:
        return 1
    if l == 0 and r == 2:
        return 0
    if l == 1 and r == 2:
        return 2


n, k = map(int, input().split())
s = list(map('RPS'.index, input()))

print('RPS'[winner(0, k)])

D - L

問題

2次元座標の格子点上にある3つの点が「L字に並ぶ」とは、3点がともに $1 \times 1$ の正方形の相異なる3頂点となっている状態を言う
はじめ、3点は $(0,0),(0,1),(1,0)$ にある
「L字の状態を保ったまま1点ずつ動かす」ことを繰り返して $(ax,ay),(bx,by),(cx,cy)$ まで移動させる最短手数を求めよ
点と点の対応は問わない（はじめにどこにあった点が $(ax,ay)$ になってもよい）
ケースは $T$ 個あるので、全てについて求めよ
$-10^9 \le ax,ay,bx,by,cx,cy \le 10^9$

解法

3点の動きをくねくねシミュレートしてたら時間切れになった。くねくね。

結果的には、近い範囲をシミュレートして、法則性を見つけるのが速かった。
また、公式解説にある通り、重心の座標は3点の配置が異なれば必ず異なるため、重心で考えれば見通しが立ちやすかった。

自分は、3点が含まれる $1 \times 1$ の正方形単位で移動回数を考えた後、最初と最後の3点の配置と移動方向によって微調整を行った。

目的地を特に考えずなるべく多く移動しようとしたら、3点が含まれる $1 \times 1$ の正方形単位で、2手でタテヨコナナメに1マス動けることが分かる。

・・・・・・      ・・・・・・      ・●・・・・
・・●・・・  →  ・●●・・・  →  ・●●・・・  左上に1マス移動
・・●●・・      ・・●・・・      ・・・・・・
・・・・・・      ・・・・・・      ・・・・・・

・・・・・・      ・・・・・・      ・・・・・・
・・●・・・  →  ・・●●・・  →  ・・・●・・  右に1マス移動
・・●●・・      ・・・●・・      ・・・●●・
・・・・・・      ・・・・・・      ・・・・・・

特定の方向に動かすには、正方形の4頂点の内、動かしたい方向の2頂点に共に点が必要で、たとえば初期状態から右上に動きたい場合は、動かしたい方向に1頂点しか無いため準備のための1手が必要となる。

・・・・・・      ・・・・・・      ・・・●・・      ・・・●・・
・・●・・・  →  ・・●●・・  →  ・・●●・・  →  ・・・●●・
・・●●・・      ・・・●・・      ・・・・・・      ・・・・・・
・・・・・・      ・・・・・・      ・・・・・・      ・・・・・・
                正方形の右か上の辺に
                2点があるように準備

ゴール時も同様に、たとえば上方向に多く動かした場合、正方形の下側の辺の2点にともに最終状態があればよいが、上側の辺に2点あった場合は $1 \times 1$ の正方形単位の移動回数にさらにもう1手が必要となる。

チェビシェフ距離の2倍を基本手数とした上で、ゴールがどちらの方向にあるかで場合分けして初手と最終手を調整すればよい。

Python3

t = int(input())
buf = []
for _ in range(t):
    ax, ay, bx, by, cx, cy = map(int, input().split())

    mx = min(ax, bx, cx)
    my = min(ay, by, cy)

    dx = (ax == mx) + (bx == mx) + (cx == mx)  # 左辺上にある頂点数（1 or 2）
    dy = (ay == my) + (by == my) + (cy == my)  # 下辺上にある頂点数（1 or 2）

    if mx == 0 and my == 0:
        if dx == 2 and dy == 2:
            buf.append(0)
        else:
            buf.append(1)
        continue

    rx, ry = False, False
    if mx < 0:
        mx = -mx
        dx = 3 - dx
        rx = True
    if my < 0:
        my = -my
        dy = 3 - dy
        ry = True

    ans = 2 * max(mx, my)

    if mx == my:
        ans += 1
        if rx or ry:
            ans -= 1
            if (rx == False and dx == 1) or (ry == False and dy == 1):
                ans += 1
            elif rx and ry and dx == 1 and dy == 1:
                ans += 1
        elif dx == 1 and dy == 1:
            ans += 1
    elif mx > my:
        if rx:
            ans -= 1
        if dx == 1:
            ans += 1
    elif mx < my:
        if ry:
            ans -= 1
        if dy == 1:
            ans += 1

    # print(_, mx, my, dx, dy, ans)

    buf.append(ans)

print('\n'.join(map(str, buf)))

E - 1D Reversi Builder

問題

$N$ 個のマスが横一列に並ぶ
黒石さんと白石さんがこのマス上で少し変則的な1次元オセロを行う
各マスに置ける石の色はゲーム開始前に固定される。各マスについて白・黒が独立に等確率で決められる
$s$ 番目のマスに最初の石が置かれ、そこから黒石さんを先手として交互に石を置く
石の置き方
- 既に石のあるマスに隣り合う空きマスを選び、そのマスに決められた色の石を置く
- 通常のオセロと同様、挟まれた石はひっくり返される
- ※黒石さんが白の石を置いてもいいし、逆も然りな点に注意
黒石さんは最終的な黒い石の個数が多くなるように行動する。白石さんは白い石を多くする
最終的な黒い石の個数の期待値を、$s=1～N$ のそれぞれについて求めよ
$1 \le N \le 2 \times 10^5$

解法

サンプルから法則性を見つけて、証明の無いまま提出したら通ってしまうエスパーが可能だったらしい。

まぁ、この問題だと分母が最初の石配置の固定のされ方 $2^N$ になるのはわかって、それをかけると「全固定配置における最終的な黒い石の数の合計」が出るので、とりあえず $2^N$ をかけてみたくなる。

すると、サンプル2,3で $s$ が1つ増えたときの差分を取っていくと見事に一致して、ははーんとなる。

ちゃんと解こうとすると、両端の色が重要となる。

まず、置かれた石は○○○●●●のように白と黒にはっきり分かれ、○○●○●●のように入り交じることは無い。

理由: 1次元オセロは白と黒の境界の個数を考えるとわかりやすく、

○○●●  ←● ... 境界数変わらず
○○●●  ←○ ... 境界数1減る
○○○○  ←● ... 現在の境界数が0の場合のみ、1増える
○○○○  ←○ ... 境界数変わらず

境界数が1個以上の時は変わらないか減るしか無く、0個の場合のみ1増えることがある。初期状態の境界数は0なので、2以上になることは無いことがわかる。

また、両端の石は挟まれることが無いため変わらない。通常オセロの角と一緒。

以上の2点より、両端の色が同じ場合、両者がどう置こうと、全ての石は両端と同じ色になることがわかる。くそげー！！

以下、違う場合について考える。
違う場合、両者は「自分が多くしたい色の方の端点」にいち早くたどり着けるように石を置いていく。

こんな固定配置を考えると、

○○○●○○ ...... ●○●●●
    ＊                  ＃

＊（左端から白が続く連続成分で一番 $s$ に近い点）と＃（右端から黒が、以下同）とで、＊の方に先に到達したら、後はどう置いても＃より左は全て白となり、黒は右端の3つだけしか残らない。
逆に＃に先に到達したら、＊より右の石を黒が総取りできる。

黒の方が先手なので、$s$ と＊、＃の位置関係を見て、距離が同じか＃の方が近ければ、黒の狙い通りになる。

両者の最適な行動がわかったので、期待値を考える。

期待値とは「最終的な黒い石の数の、全固定配置における総和」を固定配置の場合の数 $2^N$ で割ったものなので、この総和がわかればよい。
ただ、これを各 $s$ について直接求めようとすると、「端から何マスの白/黒が連続しているか」ごとの計算で $O(N)$ 必要となり（たぶん）、全体で $O(N^2)$ となってしまう。

ここで、ほとんどの場合、固定配置の白黒が反転すると、勝敗およびその枚数も反転することを利用する。
反転したもの同士をセットにすると、ほとんどのペアの最終形の黒石の個数の和はちょうど $N$ となる。

            ＊  ｓ    ＃
A       ○○○●●●○○●●●
B       ●●●○○○●●○○○

A最終形 ○○○○○○○○●●●    固定配置の白黒を反転したペアは、
B最終形 ●●●●●●●●○○○    ほとんどは最終形も白黒反転したものになる

ここで和が $N$ とならないものは何かというと、$s$ からの＊と＃への距離が等しいものについては、黒が先手という関係上、両方とも黒が勝つ。
その場合、ペアの和は $N$ より「＊と＃の間にある石の個数（両端含まず）」だけ増えることになる。

          ＊    ｓ    ＃
A       ○○●●●○○●●●
B       ●●○○○●●○○○

A最終形 ○○●●●●●●●●
B最終形 ●●●●●●●○○○

このような各ペアについてパターン数×増加分を求めて合計し、全てのペアの和が $N$ と仮定したときの総和 $N2^{N-1}$ に加算すると、答え（の分子）となる。

端から考える。ペアを重複させないため、左が白、右が黒のパターンのみを考える。

ｓ
？？？？？？？？？？    s=1の場合、そのようなペアは存在せず

  ｓ                    s=2の場合、距離が等しいという意味では図のような＊＃の配置が考えられるが、
○？●●●●●●●●    sがどちらになっても「＊＃は端からの同色の連続でsに最も近い」に矛盾する。
＊  ＃                  したがって、s=2でもそのようなペアは存在しない。

    ｓ                  s=3ではじめてそのようなペアが生じる。
○●？○●●●●●●    真ん中の1マスをどちらにするかで2パターン
＊      ＃              増加分は3マスで、合計6個、黒が増える

      ｓ                s=4では、
○○●？○●●●●●    s=3と同じようなパターンに加え、
  ＊      ＃            
      ｓ                もう1段階広いものも取れる。
○●？？？○●●●●    これは、真ん中3マスで 2^3 パターン
＊          ＃          増加分は5マスで、合計40個、さらに黒が増える

$s$ が半分を超えると左右反転して考えればよいので、半分までを考えると、$s \ge 3$ では $s$ が1つ進むたびに黒の個数は $(2s-3)2^{2s-5}$ 個増える。

これを累積的に求めていけばいい。

Python3

n = int(input())
MOD = 998244353

if n == 1:
    print(pow(2, MOD - 2, MOD))
    exit()

if n == 2:
    print(1)
    print(1)
    exit()

div = pow(pow(2, n - 1, MOD), MOD - 2, MOD)
num = n * pow(2, n - 2, MOD) % MOD
a = 1
b = 3
buf = [div * num % MOD] * 2
for i in range((n + 1) // 2 - 2):
    num = (num + a * b) % MOD
    buf.append(div * num % MOD)
    a = a * 4 % MOD
    b += 2
if n % 2 == 0:
    buf.extend(list(reversed(buf)))
else:
    buf.extend(list(reversed(buf[:-1])))

print('\n'.join(map(str, buf)))

目次

AtCoder Regular Contest 109 B,C,D,E問題メモ

B - log

問題

解法

C - Large RPS Tournament

問題

解法

D - L

問題

解法

E - 1D Reversi Builder

問題

解法