AtCoder Regular Contest-- 219 A～E問題メモ

AtCoder Regular Contest-- 219

ARC– は、ARC(無印)より若干易しめの問題が出題されるとのこと。
ただし、「気付けば実装は簡単（気付くのが簡単とは言っていない）」系の問題は解ける解けないのブレが大きいね。。。

A - Similarity

• $N$ 個の相異なる文字列 $S_1, \dots, S_N$ が与えられます。これらの文字列はいずれも、0, 1 のみからなる長さ $M$ の文字列です。
• 0, 1 のみからなる長さ $M$ の文字列 $T$ のうち、以下の条件を満たすものが存在するか判定し、あれば一例を構築してください。
  • どの文字列 $S_i$ も、$T$ と少なくとも $1$ 箇所で文字が一致する。

• $N,M$ は整数
• $1 \leq N \leq 2 \times 10^4$
• $1 \leq M \leq 100$
• $S_i$ は 0, 1 のみからなる長さ $M$ の文字列
• $S_1, \dots, S_N$ は相異なる

$S_i$ に対して条件を満たさない $T$ は、唯一、$M$ 個の '0','1' が全て反転されたもののみである。

• (例) $S_i=01001$ に対しては、$T=10110$ 以外なら何でもよい

よって、

• $2^M=N$ の場合は、不可能。
• それ以外の場合 $N+1$ 個の $T$ を試すと、必ず1つは条件を満たす。

Python3

def solve(n, m, sss):
    ttt = [int(s, base=2) for s in sss]
    if n == (1 << m):
        return None
    full_bit = (1 << m) - 1
    ng = {t ^ full_bit for t in ttt}
    for bitset in range(n + 1):
        if bitset in ng:
            continue
        return f'{bitset:0{m}b}'


n, m = list(map(int, input().split()))
sss = [input() for _ in range(n)]
ans = solve(n, m, sss)
if ans is None:
    print('No')
else:
    print('Yes')
    print(ans)

B - Reverse Permutation

• 整数 $N$ と $(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ が与えられます。
• $(1,2,\ldots,N)$ の順列 $Q=(Q_1,Q_2,\ldots,Q_N)$ に対して、以下の操作をちょうど $1$ 回行うことにより得られる順列の中で辞書順最小の順列を $Q'=(Q_1',Q_2',\ldots,Q_N')$ とします：
  • $1\le l\le r\le N$ を満たす整数の組 $(l,r)$ を選び、$Q_l,Q_{l+1},\ldots,Q_r$ を反転させる。
• $Q'=P$ となる $(1,2,\ldots,N)$ の順列 $Q$ の個数を $998244353$ で割ったあまりを求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T$
• $1\le N\le 5\times 10^5$
• $P$ は $(1,2,\ldots,N)$ の順列
• 全てのテストケースにおける $N$ の総和は $5\times 10^5$ 以下
• 入力される値は全て整数

まず、$Q$ に対して $Q'$ の求め方は意外と単純で、

• $Q_i \neq i$ である最小の $i$ を見つける
• $l=i$、$r=(i=Q_j である j)$ として操作する

i   1 2 3 4 5 6      i    1 2 3 4 5 6
Q = 1 2 6 5 3 4  →  Q' = 1 2 3 5 6 4
        ~~~~~

ただし、最初から $Q=(1,2,...,N)$ だった場合は、$l=r$ として元の数列を変えないように操作する。
この変えないケースは特殊なのでひとまず除き、$l \lt r$ の場合を考える。
その上で、$P=(1,2,...,N)$ だった場合のみ、最後に答えに1加算すればよい。

$P$ の中で、$l$ として指定されたのが何であったかを固定する。

そのような $l$ は、左から $i=P_i$ が続いているような $i$ の1つでなければならない。
また各 $l$ に対し、対応する $r$ は $l \lt r \le N$ を満たす $N-l$ 通りのどれでもよい。

よって、以下の総和を求めればよい。

• 「$1 \le j \le i$ なる $j$ が全て $j=P_j$」であるような各 $i$ に対し、$N-i$ を答えに加算する。

ところで、答えは64bit整数に収まることが保証されるが、MODを取ることを忘れないように。

Python3

def solve(n, ppp):
    ans = 0
    for i in range(n):
        if ppp[i] != i + 1:
            break
        ans += n - i - 1

    else:
        # 最初からソート済みのやつ
        ans += 1

    ans %= 998244353
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    ppp = list(map(int, input().split()))
    ans = solve(n, ppp)
    print(ans)

C - Traveling Door-to-Door Salesman (Elevator)

• $H$ 行 $W$ 列のグリッドで表される地下アパートがあります。上から $i$ 行目・左から $j$ 列目のマスをマス $(i,j)$ と表記します。
• 地下アパートの出入り口はマス $(1,1)$ にあります。
• 地下アパートにはドアが $N$ 個あります。$k$ 個目のドアはマス $(A_k, B_k)$ にあります。
• 地下アパート内で、セールスマンは以下の $2$ 種類の移動を好きな順番で何回でも行えます。
  • 現在いるマスから左か右に隣接するマスに徒歩で移動できる。この移動はコストを $1$ 消費する。
  • 現在いるマスが $1$ 列目または $W$ 列目の場合、そこから上か下に隣接するマスにエレベーターで移動できる。この移動はコストを $\mathbf{0}$ 消費する。

• セールスマンの目標は、マス $(1,1)$ から出発して移動を繰り返し、ドアのある $N$ 個のマスすべてを $1$ 回以上訪問してからマス $(1,1)$ に到着することです。
• セールスマンが目標を達成するために消費する総コストの最小値を求めてください。

• $1 \leq H \leq 10^9$
• $2 \leq W \leq 10^9$
• $1 \leq N \leq 3 \times 10^5$
• $1 \leq A_k \leq H$
• $1 \leq B_k \leq W$
• $(A_1, B_1), \dots, (A_N, B_N)$ は相異なる
• 入力される値はすべて整数

ドアを階層 $A_i$ ごとに分類して同階層にあるドアの位置をリスト化する。
ドアがない階層には（エレベーターでの経由以外で）訪れる必要は無い。

ドアが存在する各階層のコストを計算する。
着目中の階にあるドアを $k$ 個、位置を左から $b_1,...,b_k$ とすると、この階のコストは以下のいずれかである。

• (a) フロアを横断する。コストは $W-1$ かかる
• (b) $0$ 個以上のドアを左から、残りを右から訪問する
  • 便宜的に $b_0=1,b_{k+1}=W$ として、コストは $\min_{0 \le i \le k}(2(b_i-1)+2(W-b_{i+1}))$
• (c) 全てのドアを左から訪問して左に帰る
  • コストは $2(b_k-1)$

その後、各階層でどの移動方法を採用するかを考える。

まず (a) を1つも含まない場合、右に移動する機会が無いので、(b) が実現できない。
この場合、全て (c) とした場合のコストが1つの候補となる。

(a)を含む場合、(a)は→方向と←方向の2階層を1セットで使わなければならない。
各階層の(b)のコストを計算し、ソートする。
$m=1,2,...$ に対し、コストの大きい方から $2m$ 個を $W-1$ で置き換える、ということをコストが改善しなくなるまで試せばよい。

Python3

from collections import defaultdict
from itertools import accumulate


def solve(h, w, n, doors):
    doors_by_floor = defaultdict(lambda: {0, w - 1})
    max_by_floor = defaultdict(int)
    for a, b in doors:
        b -= 1
        doors_by_floor[a].add(b)
        max_by_floor[a] = max(max_by_floor[a], b)

    ans_all_uturn = 0
    uturn_costs = []
    for a, bbb in doors_by_floor.items():
        bbb = sorted(bbb)
        floor_cost = 1 << 60
        for i in range(len(bbb) - 1):
            floor_cost = min(floor_cost, bbb[i] * 2 + (w - bbb[i + 1] - 1) * 2)
        ans_all_uturn += 2 * max_by_floor[a]
        uturn_costs.append(floor_cost)
    if len(uturn_costs) == 1:
        return ans_all_uturn

    uturn_costs.sort()
    acc = [0] + list(accumulate(uturn_costs))
    ans = ans_all_uturn

    for i in range(3, len(acc) + 1, 2):
        tmp = (w - 1) * (i - 1) + acc[-i]
        ans = min(ans, tmp)

    return ans


h, w = list(map(int, input().split()))
n = int(input())
doors = [list(map(int, input().split())) for _ in range(n)]
ans = solve(h, w, n, doors)
print(ans)

D - Grid Game

• $N$ 行 $N$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と表します。マス $(i,j)$ にははじめ $A_{i,j}$ 個の石があります。
• Alice と Bob がこのグリッドを使って以下のようなゲームを行います。
  • Alice から始めて両者は交互に手番をプレイする。
  • 各手番では、プレイヤーはマスを $1$ つ選び、そこから $1$ 個以上 $K$ 個以下の石をまとめて上または左に隣接するマスへ移動させる。具体的には、次の手順を順に行う。
    • 石が $1$ 個以上あるマス $(i,j)$ を選ぶ。ただし、マス $(1,1)$ は選べない。
    • マス $(i,j)$ にある石の個数を $c$ とし、$1 \le x \le \min(c,K)$ を満たす整数 $x$ を選ぶ。
    • 移動先として、存在するならばマス $(i-1,j)$ またはマス $(i,j-1)$ のいずれか一方を選び、マス $(i,j)$ から石を $x$ 個取り出して全てそのマスに移動させる。
• 先に手番をプレイできなくなったプレイヤーの負けです。
• 両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T$
• $2\le N\le 100$
• $1\le K\le 10^9$
• $0\le A_{i,j}\le 10^9$
• 全てのテストケースにおける $N^2$ の総和は $3\times 10^5$ 以下
• 入力される値は全て整数

ニム（石取りゲーム）のように Grundy 数が使えそうなんだけど、この時「各山は独立」という条件が必要となる。

今回の場合、山から石が消えるわけでは無く移動するので、 「移動先に石が何個あるか」の状態が関わってきて、個々の山を独立に考えられないように見える。

だが、実は上手い考察によって独立と見なせる。

盤面を市松模様に塗る。$(1,1)$ が黒とする。
この時、「白のマスのみのGrundy数」を考えるのが解法となる。

以下、「Grundy数」は白のマスのみを対象としたものを指すとし、 Grundy数の総XORが $0$ の状態を「後手必勝盤面」とする。

仮に現在が後手必勝盤面とすると、後手は以下の通りに行動すれば、後手必勝盤面を維持できる。

• 先手が黒から白に動かした場合、後手はその白から同数を黒に動かす。
• 先手が白から黒に動かした場合、後手は任意の白から、Grundy数の総XORが $0$ の状態を維持できるように黒に動かす。

黒にある石は、先手がどのように動かそうと後手は黒に戻せ、最終的に動かせない $(1,1)$ に到達するので、 先手にとっては状況を打破する材料とならない。

これを「黒にある石は無いのと変わらない」と考えて良いことに気づけば、 「白から石を取るゲーム」となり、元のニムと同様に独立に考えることができる。

一度に取れる石の個数が $1～K$ であるニムの Grundy 数は、石の数を $(K+1)$ で割ったあまりとなる。

Python3

def solve(n, k, field):
    grundy = 0
    for i in range(n):
        for j in range(n):
            if (i + j) % 2 == 0:
                continue
            grundy ^= field[i][j] % (k + 1)
    if grundy == 0:
        return 'Bob'
    return 'Alice'


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    field = [list(map(int, input().split())) for _ in range(n)]
    ans = solve(n, k, field)
    print(ans)

E - Equal Distribution

• $2H$ 行 $2W$ 列のグリッド状のショートケーキがあります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と表します。
• マス $(i,j)$ には $S_{i,j}=$ o ならばイチゴが $1$ つ乗っており、 $S_{i,j}=$ x ならば何もありません。ここで、イチゴが乗ったマスはちょうど $2HW$ マスであることが保証されます。
• このショートケーキの各マスを以下の条件を全て満たすように領域 A, B に分けてください。
  • 全てのマスは領域 A, B のちょうど一方に含まれる。
  • 領域 A, B はどちらも連結である。つまり、任意の同じ領域内の $2$ マスは上下左右に辺で接している同じ領域内のマスに移動する操作を繰り返すことで互いに移動可能である。
  • 領域 A, B はどちらもマスを $2HW$ マスずつ含む。
  • 領域 A, B はどちらもイチゴを $HW$ 個ずつ含む。
• ただし、そのような分け方が必ず存在することが証明できます。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T$
• $1\le H\le W$
• $H\times W\le 10^6$
• $S_{i,j}$ は o または x
• $S_{i,j}=$ o を満たす $(i,j)$ がちょうど $2HW$ 個存在する
• 全てのテストケースにおける $H\times W$ の総和は $10^6$ 以下
• $T,H,W$ は整数

いくつかのマスを、（$S_{i,j}$ に依らない決められたパターンで）以下の条件を満たすように領域 A,B に固定する。

• 領域AもBも、固定した時点で連結である。
• 固定されていないマスは全て、A,B の両方に隣接している

AAAAAA
A.....
ABBBBB  一例
AAAAAB
.....B
BBBBBB

この時、固定されていないマスは任意に A,B に振り分けることができる。 固定したマスと合わせてマス,イチゴの数をそれぞれ $2HW,HW$ にできるように調整すれば達成できる。

だが、、、

最初に固定した時点で、1つの領域における「'o'のマス」または「'x' のマス」の個数の いずれかが $HW$ 個を超えた場合は構築不可となる。

1領域につき固定するマスを $HW$ 個以下にする方法があればよいが、それはどうも難しい。 （固定マスを $HW$ 個にするには、平均して固定した1マスあたり2マスの非固定マスに隣接する必要があるが、 そもそも連結した領域において1マスに隣接できる領域外のマスは $領域サイズ \times 2 + 2$ 個以下となり、この時点でギリギリである。 さらにA,B両方に隣接するという条件を考慮すると盤面の端のマスはほぼ非固定にできないので、まぁ無理っぽい）

回転させたり、転置させたり、様々なケースを試して1通りでも上手くいけばよし、としても、 その全てで不可能となるような盤面がテストケースに含まれるらしく、1ケースのWAが取れなかった。

$2N$ 個の 'o'と $2N$ 個の'x'からなる長さ $4N$ の円環状の列を、 $N$ 個の'o'と $N$ 個の'x'からなる長さ $2N$ の列2つに切り分ける、 ということは、必ず達成可能である。

• Necklace_splitting_problem

今回の場合、グリッドからハミルトン閉路を構築し、それを円環状の列と見なすことで条件を達成することができる。

Python3

from itertools import accumulate


def solve(h, w, field):
    hamilton = []
    pos = []

    for i in range(h * 2):
        if i % 2 == 0:
            s, t, step = 1, w * 2, 1
        else:
            s, t, step = w * 2 - 1, 0, -1
        for j in range(s, t, step):
            hamilton.append(1 if field[i][j] == 'o' else -1)
            pos.append((i, j))
    for i in range(h * 2 - 1, -1, -1):
        hamilton.append(1 if field[i][0] == 'o' else -1)
        pos.append((i, 0))

    acc = list(accumulate(hamilton))
    hw2 = h * w * 2
    hi = -1
    for hi in range(hw2):
        if acc[hi] == acc[hi + hw2]:
            break
    assert hi != -1

    ans = [['B'] * (w * 2) for _ in range(h * 2)]
    for pi in range(hi + 1, hi + hw2 + 1):
        i, j = pos[pi]
        ans[i][j] = 'A'

    return '\n'.join(''.join(row) for row in ans)


t = int(input())
for _ in range(t):
    h, w = list(map(int, input().split()))
    field = [input() for _ in range(h * 2)]
    ans = solve(h, w, field)
    print(ans)