AtCoder Beginner Contest 184 C,D,E,F問題メモ

AtCoder Beginner Contest 184

個人的に、今回は骨のあるABCだった。

C - Super Ryuma

• 無限に広がる将棋盤がある
• 駒「スーパー竜馬」があり、【本家問題文参照】のように移動できる
• $(r_1,c_1)$ から $(r_2,c_2)$ に最低何手で行けるか答えよ

0手は言うまでも無し。1手は問題文中に判定法があるのでその通りに。

3手かければ絶対行けるので、「2手か3手か」というのがメインの考察。

以下、1手以下ではいけないとする。以下のパターンで2手が可能、それ以外で3手となる。

• 2手のナナメ移動
• 2手の横移動
• 1手の横移動 + 1手のナナメ移動

ただし、マンハッタン距離3以下の移動を“横移動”と称する。

「市松模様に塗ったときに同じ色になるマス」へはどんなに離れていても行ける。
$r_1+c_1$ と $r_2+c_2$ の偶奇が一致していればよい。

        ・
      ↗  ↘
    ↗      ↘
  ↗         (r2,c2)
(r1,c1)

なお、3手で絶対行けるのは、2手であと1マスの距離まで近づけることから分かる。

マンハッタン距離が6以下ならよい。

これが少しややこしい。

1手目で $(r_2,c_2)$ のナナメの利きに移動できる場合も2手で移動できる。
この場合、$(r_1,c_1)$ から見て $(r_2,c_2)$ が幅のあるナナメの範囲に入っているか、という判定となる。

$(r_1,c_1)$ を $(0,0)$ に平行移動すると、少しわかりやすくなる。

o: 1手横移動 + 1手ナナメ移動（よりも少ない手数）で行ける範囲

    -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6
-6   o  o  o  o                 o  o  o  o
-5   o  o  o  o  o           o  o  o  o  o
-4   o  o  o  o  o  o     o  o  o  o  o  o
-3   o  o  o  o  o  o  o  o  o  o  o  o  o
-2      o  o  o  o  o  o  o  o  o  o  o
-1         o  o  o  o  o  o  o  o  o
 0            o  o  o  o  o  o  o
 1         o  o  o  o  o  o  o  o  o
 2      o  o  o  o  o  o  o  o  o  o  o
 3   o  o  o  o  o  o  o  o  o  o  o  o  o
 4   o  o  o  o  o  o     o  o  o  o  o  o
 5   o  o  o  o  o           o  o  o  o  o
 6   o  o  o  o                 o  o  o  o

これは、$r,c$ の関係性を見ると、「差か和の絶対値が3以下」なら行ける、ということになる。

もう1つの方法として、$(r_1,c_1)$ から1手の横移動で行けるマスを全て試して、「あと1手のナナメ移動で $(r_2,c_2)$ へ行けるか？」を調べてもよい。

Python3

def solve(r1, c1, r2, c2):
    r3 = r2 - r1
    c3 = c2 - c1

    if r3 == 0 and c3 == 0:
        return 0

    if r3 == c3 or r3 == -c3:
        return 1
    if abs(r3) + abs(c3) <= 3:
        return 1

    if (r3 + c3) % 2 == 0:
        return 2
    if abs(r3) + abs(c3) <= 6:
        return 2
    if abs(r3 - c3) <= 3 or abs(r3 + c3) <= 3:
        return 2

    return 3


r1, c1 = map(int, input().split())
r2, c2 = map(int, input().split())
print(solve(r1, c1, r2, c2))

なお、本番はマンハッタン距離6以下を見落とす嘘解法で通した模様。

D - increment of coins

• 3種類のコインの入った1つの袋があり、はじめ、コインはそれぞれ $A,B,C$ 枚入っている
• 以下の操作を、どれかが100枚になるまで繰り返す
  • 袋からコインを等確率で1枚選ぶ
  • それと同じ種類のコインを1枚袋に追加する
• 操作回数の期待値を求めよ
• $0 \le A,B,C \le 99$

状態数が少ない （$100^3$）ので、再帰を利用した全探索。

• $f(a,b,c)=$ 袋のコインがそれぞれ $a,b,c$ 枚だったときの操作回数の期待値

すると、たとえば $\dfrac{a}{a+b+c}$ の確率で $a$ 枚あるコインが選ばれ、その時の操作回数は $f(a+1,b,c)+1$ 回となる。

これを $b,c$ 枚のコインについてもあわせればよい。

• $f(a,b,c)=0$（どれかが100の場合）
• $f(a,b,c)=\dfrac{a}{a+b+c}f(a+1,b,c)+\dfrac{b}{a+b+c}f(a,b+1,c)+\dfrac{c}{a+b+c}f(a,b,c+1)+1$

再帰で解く場合はキャッシュを忘れないように。

Python3

import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)


@lru_cache(maxsize=None)
def solve(a, b, c):
    if max(a, b, c) == 100:
        return 0

    s = a + b + c
    return (solve(a + 1, b, c) * a + solve(a, b + 1, c) * b + solve(a, b, c + 1) * c) / s + 1


a, b, c = map(int, input().split())
print(solve(a, b, c))

E - Third Avenue

• $H \times W$ の盤面
• 各マスはS,G,.,#,a～zのいずれか
• 以下の2通りの移動で'S'から'G'まで行く
  • 壁'#'でないマスにタテヨコに移動する
  • 'a'～'z'のマスにいる場合、同じアルファベットの好きなマスにワープする
• 最小手数を求めよ
• $1 \le H,W \le 2000$

よくあるグリッド探索に、ワープ移動も追加されたもの。

注意点として、ある文字のワープを1回使ったら、同じ文字のワープを2回目に使う意味は無い。

グリッド探索は基本的にグラフを構築して幅優先探索に帰着させるのだが、移動できるマス間全てに辺を張ってしまうと、 「'S'と'G'以外の全てのマスが同じアルファベット」などのケースで辺数が $O(H^2W^2)$ となり、MLE or TLEとなる。

以下の方法で回避できる。

• あらかじめグラフは作らずに、必要に応じて次の探索場所を広げる
  • 新しいマスに訪れるたびにそこから「上下左右」「ワープマスならワープ」へと探索を広げていく
  • 事前に、どのワープ文字からどの座標へ移動できるか調べておく
  • 同じ文字の2回目以降はワープしないようにする
• ワープ中継頂点を追加する
  • ワープの中継地点となる仮想的な頂点を追加し経由させると、辺数が $O(HW+ワープ種類数)$ に抑えられる
  • ワープマス→中継地点→ワープマスというグラフ上で2回の移動がコスト1になってしまうので、どちらかを0にする
  • 辺のコストが一定でなくなるので幅優先探索が使えなくなり、0-1BFSかDijkstraでの実装となるが、グラフさえ作れば既存のライブラリにそのまま当てはめやすい

本番ではNumbaを使ったが、使わない素のPythonでも高速化を頑張ればギリギリ通った。
文字列が入力にある問題でのNumbaは変換をどうしようか悩む時間がもったいないですね。 （ただ、素のPythonでTLEを解消しようと高速化頑張るよりはよほどまし）

Python3

import string
from collections import deque


def solve(h, w, field):
    teleport = {c: [] for c in string.ascii_lowercase}
    for i, c in enumerate(field):
        if c in teleport:
            teleport[c].append(i)

    s = field.index('S')
    g = field.index('G')
    q = deque()
    q.append(s)
    dp = [-1] * len(field)
    dp[s] = 0
    MOVE = (-w - 2, -1, 1, w + 2)
    while q:
        v = q.popleft()
        next_cost = dp[v] + 1
        for dv in MOVE:
            u = v + dv
            if field[u] == '#':
                continue
            if dp[u] != -1:
                continue
            if u == g:
                return next_cost
            dp[u] = next_cost
            q.append(u)
        f = field[v]
        if f in teleport:
            for u in teleport[f]:
                if dp[u] != -1:
                    continue
                dp[u] = next_cost
                q.append(u)
            del teleport[f]
    return -1


h, w = map(int, input().split())
field = '#' * (w + 3)
field += '##'.join(input() for _ in range(h))
field += '#' * (w + 3)
print(solve(h, w, field))

F - Programming Contest

• あるプログラミングコンテストでは $N$ 問の問題が出題され、制限時間は $T$
• $i$ 番目の問題を解くのにかかる時間は $A_i$
• 制限時間内に収まるように選んで問題を解くとき、解くのにかかる時間の和の最大値を求めよ
• $1 \le N \le 40$
• $1 \le T \le 10^9$

制約を見て、ペロッ…これは…半分全列挙!! となる。

やりたいことはナップサックだが、$O(TN)$ かかるので無理。
bitDPも $O(2^N)$ なのでちょと厳しい。

ナップサック問題はそれくらいしか現実的な解法が無いはずなので、困る。

$O(2^\frac{N}{2})$ なら可能な制約であることに着目する。

$N$ 個を半分くらいに分け（$B,C$ とする）、それぞれでbitDPにより「作れる所要時間の集合」$D_B,D_C$ を求める。

A = { 2 3 5 7 11 }

B: 2 3 5  →  DB: { 0 2 3 5 7 8 10 }  2,3,5だけで作れる所要時間
C: 7 11   →  DC: { 0 7 11 18}        7,11だけで作れる所要時間

すると、「$D_B$ と $D_C$ から1つずつ選んで足し合わせて作れる値」が「$A$ の $N$ 個の要素を選んだり選ばなかったりして作れる値」と一致する。

ここで $D_C$ の1要素 $d$ を固定すると、$D_B$ からは「$T-d$ を超えない最大の値」を持ってきてペアにするのが最適となる。
これはあらかじめ $D_B$ をソートしておくと、二分探索で高速に持ってこれる。

T = 16

{ 0 7 11 18 } から 7 を固定すると...
{ 0 2 3 5 7 8 10 } からは、9を超えない、9に最も近い値が欲しい

なので、$D_C$ の $2^\frac{N}{2}$ 個の要素それぞれにつき、$D_B$ の二分探索をすることで答えの候補を求められる。

その中で最大のものが答え。

計算量は、$O(2^\frac{N}{2}N)$ となる。

なんか「競プロで、解くのにかかる時間をなるべく制限時間ぎりぎりに近づける」という問題設定が直感的でなくって、 金額とか、暇な時間をつぶすとか、他のシチュエーションの方が頭に入ってきやすかったなあとちょっと思った。

まぁ、金額だとありふれすぎて、丸被りしちゃう過去問があったのかも。

Python3

import os
import sys

import numpy as np


def solve(inp):
    def bit_length(x):
        ret = 0
        while x:
            x >>= 1
            ret += 1
        return ret

    def powerset(aaa):
        dp = np.zeros(1 << aaa.size, np.int64)
        for bit in range(1, 1 << aaa.size):
            b = bit & -bit
            bi = bit_length(b) - 1
            dp[bit] = dp[bit ^ b] + aaa[bi]
        return dp

    n = inp[0]
    t = inp[1]
    aaa = inp[2:]

    if n <= 20:
        p = powerset(aaa)
        return p[p <= t].max()

    bbb = np.unique(powerset(aaa[:20]))
    bbb.sort()
    ccc = np.unique(powerset(aaa[20:]))

    ans = 0
    for c in ccc:
        if c > t:
            continue
        i = np.searchsorted(bbb, t - c, side='right')
        ans = max(ans, c + bbb[i - 1])
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

計算量上は、以下の2箇所を工夫することで、$O(2^\frac{N}{2})$ に減らせるらしい。（元の方法では、どちらも $O(2^\frac{N}{2}N)$ かかっている）

• 半分ずつの集合から作れる和の全列挙+ソートを、$O(2^\frac{N}{2})$ で行う
  • ソートされた2つの配列を、ソートされた状態を保ちながらマージする、を繰り返す
• ペアを二分探索でなく、尺取りで求める

が、実際にやってみると、以下の理由からか、あまり速くはならない。

• 上手く実装しないと、配列のマージで毎回新たな配列を作ってしまい、その生成コストが高い
• Pythonでは配列アクセスがあまり速くない

Numpyを使うと以下のことが可能になる。

• 全列挙において、最初に全体分のメモリを確保しつつ、一部だけをソートできる
  • マージする方法を用いながら、毎回新たな配列を作らずに済む
  • ソート方法も、既に半分ずつがソート済みであることを生かせるマージソートを指定できる
• 二分探索において、同じ対象に複数の値をまとめて投げられ、そこそこ高速に処理される

すると、Numbaを使わないPythonでも、200msを切ることが可能となる。

• 参考（maspy氏）
  • 提出 #18313090 - AtCoder Beginner Contest 184