第七回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 222）A,B,C問題メモ

第七回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 222）

A - Colorful Intervals

問題文

正整数 $N, M$ と、$M$ 個の区間 $(L_j,R_j)$ が与えられます．
長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ であって，すべての $j=1,2,\ldots,M$ に対して次の条件を満たすものを考えます．
- $A_{L_j},A_{L_j+1},\ldots,A_{R_j}$ はすべて相異なる．
このような正整数列 $A$ は必ず存在することが証明できます．
条件を満たす正整数列 $A$ のうち，$\max(A_1,A_2,\ldots,A_N)$ の値が最小となるものを $1$ つ出力してください．

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

制約

$1\leq T\leq 10^5$
$1\leq N\leq 2\times 10^5$
$1\leq M\leq 2\times 10^5$
$1\leq L_j \leq R_j\leq N$ ($1\leq j\leq M$)
入力される値はすべて整数．
すべてのテストケースにわたる $N$ の総和は $2\times 10^5$ 以下．
すべてのテストケースにわたる $M$ の総和は $2\times 10^5$ 以下．

解法

ARCの最初の方にたまにある、気付けばギャグかと思うほど簡単系の問題。
無思考で $R_i$ の昇順にソートした人はパターンマッチングの過剰適合。

区間長 $R_i-L_i+1$ の最大値を $W$ とする。この中は被ってはいけないので、$\max(A_1,...,A_N)$ として取り得る下限は $W$ である。

で、$A=(1,2,...,W,1,2,...,W,1,2,...)$ という数列は、どの長さ $W$ 以下の連続区間を見ても被っていないので、これが条件を満たす数列の1つである。

Python3

def solve(n, m, sections):
    max_len = 0
    for l, r in sections:
        l -= 1
        max_len = max(max_len, r - l)
    ans = [0] * n
    for i in range(n):
        ans[i] = (i % max_len) + 1
    return ans


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

B - Circular RPS

問題文

$a+b+c$ 人の参加者によるじゃんけん大会が行われました．
大会では，まず参加者全員が円周上に並びます．その後，各参加者は「グー」「チョキ」「パー」のいずれか $1$ つの手を出します．
各参加者について，自分の出した手が両隣の参加者が出した手の両方に勝っているとき，その参加者は勝者となります．
この大会について，以下のことが分かっています．
- $a$ 人の参加者が「グー」の手を出した．
- $b$ 人の参加者が「チョキ」の手を出した．
- $c$ 人の参加者が「パー」の手を出した．
この条件のもと，大会の勝者の人数としてありうる最大値を求めてください．

$T$ 個のテストケースが与えられるので，それぞれについて解いてください．

制約

$1\leq T\leq 5\times 10^5$
$0\leq a, b, c\leq 10^9$
$3\leq a+b+c$
入力される値はすべて整数．

解法

勝者となる手が1種類、2種類、3種類に分けて考えると道筋が良い。

以下で説明される $(a,b,c)$ の関係性は、$(b,c,a)$ や $(c,a,b)$ に置き換えても成り立つとする。

まず、例外的なケースを先に処理する。

$b=c=0$ のとき、グーだけでは勝者を作れないので、答えは $0$ となる。
$a=b$ かつ $c=0$ の時、グーとチョキを交互に並べるとグーが全て勝者とできる。

以下、それ以外とする。

勝者を多くしようと思うと、次の3つのタイプの並びをなるべく多く作るのがよい。
複数の並びの間で、勝者の数を保ったまま参加者を共有することはできない。3つの並びは全て別の参加者である。

① チグチグチグチ: グーが勝者。
② パチパチパチパ: チョキが勝者
③ グパグパグパグ: パーが勝者

①の並びで使用したグーを $G_w$ 個、チョキを $C_l$ 個とする。
②の並びで使用したチョキを $C_w$ 個、パーを $P_l$ 個とする。
③の並びで使用したパーを $P_w$ 個、グーを $G_l$ 個とする。

すると、以下が成り立つ。

$G_w+G_l \le a$
$C_w+C_l \le b$
$P_w+p_l \le c$
$G_w=0$ の時、$C_l=0$。$G_w \ge 1$ の時、$C_l=G_w+1$
$C_w=0$ の時、$P_l=0$。$C_w \ge 1$ の時、$P_l=C_w+1$
$P_w=0$ の時、$G_l=0$。$P_w \ge 1$ の時、$G_l=P_w+1$

なので、$G_w,C_w,P_w$ がそれぞれ正かどうかで場合分けが発生する。

1種類

$G_w$ のみの時、$\min(a,b-1)$

2種類

$G_w,C_w$ のみの時、$G_w=\min(a,b-1)$ としてよい。この時、$C_l=G_w+1$ である。

その後、$C_w=\min(b-C_l,c-1)$ とできる。

3種類

負ける側に配置する必要があるので、$a,b,c$ は全て $1$ 以上である必要がある。

$a'=a-1,b'=b-1,c'=c-1$ とする。
こうすると、どれか2個をペアにする度に、1人を勝者にできる。

よって、$\max(a',b',c')=a'$ であるとして、答えは $\min(b'+c', \lfloor \frac{a'+b'+c'}{2} \rfloor)$ となる。

Python3

def solve(a, b, c):
    if max(a, b, c) != a:
        return solve(b, c, a)

    if b == 0:
        return c
    if c == 0:
        if a == b:
            return a
        return b - 1

    def increase(a, b, c, gw, gl, cw, cl, pw, pl):
        g_ok = (a - gw - gl) // 2
        c_ok = cw
        p_ok = pl
        d = min(g_ok, c_ok, p_ok)
        return gw + d, gl + d, cw - d, cl + d, pw + d, pl - d

    def use_2(a, b, c):
        gw = min(a, b - 1)
        cl = gw + 1
        cw = min(b - cl, c - 1)
        return gw + cw

    def use_3(a, b, c):
        gw = min(a - 1, b - 1)
        cl = gw + 1
        cw = min(b - cl, c - 1)
        pl = cw + 1
        pw = 0
        gl = 1

        for _ in range(3):
            gw, gl, cw, cl, pw, pl = increase(a, b, c, gw, gl, cw, cl, pw, pl)
            cw, cl, pw, pl, gw, gl = increase(b, c, a, cw, cl, pw, pl, gw, gl)
            pw, pl, gw, gl, cw, cl = increase(c, a, b, pw, pl, gw, gl, cw, cl)
            # print(gw, gl, cw, cl, pw, pl)

        return gw + cw + pw

    ans = max(use_2(a, b, c), use_2(b, c, a), use_2(c, a, b))
    ans = max(ans, use_3(a, b, c), use_3(b, c, a), use_3(c, a, b))

    return ans


t = int(input())
for _ in range(t):
    a, b, c = list(map(int, input().split()))
    ans = solve(a, b, c)
    print(ans)

C - 2 Directions vs 4 Directions

問題文

$N\times N$ のマス目があります．はじめ，すべてのマスは黒マスです．
このマス目とひとつの駒を使って，Alice と Bob がゲームを行います．
ゲームは次のような $3$ つのステップからなります．
- ステップ1:
  - 審判が，駒を最初に置くマスを指定します．
- ステップ2:
  - Alice は次の操作を $0$ 回以上行います．
    - 黒マス $(i,j)$ をひとつ選び，コスト $A_{i,j}$ を支払って，そのマスを白マスに変更する．
- ステップ3:
  - ステップ 1 で初期位置として指定されたマスに駒を置きます．
  - その後 Alice から始めて，Alice と Bob は交互に手番を行います。
    - Alice の手番では，Alice が駒を左右のいずれかに隣接するマスへ動かす．
    - Bob の手番では，Bob が駒を上下左右のいずれかに隣接するマスへ動かす．
    - ただし，マス目の外へ出るように動かすことはできません．
  - 互いに $10^{10}$ 回ずつ手番を行うと終了します．
ステップ 3 が終了した時点で，駒があるマスが白マスならば Alice の勝ち，黒マスならば Bob の勝ちとなります．
各マス $(h,w)$ について，ステップ 1 で駒を最初に置くマスとして $(h,w)$ が指定された場合に，Alice が勝つためにステップ 2 で支払う必要がある合計コストの最小値を求めてください．

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

制約

$1\leq T\leq 10^4$
$2\leq N\leq 500$
$0\leq A_{i,j}\leq 10^9$
入力される値はすべて整数．
すべてのテストケースにわたる $N^2$ の総和は $500^2$ 以下．

解法

総手番は偶数回なので、市松模様で $(h,w)$ と異なる色のマスで終了することはない。ただ、同じ色ならどこでも終了する可能性があるわけでもない。 Aliceは上手く操作することで、終了する可能性のあるマスをどこまで減らせるか、というのが考察の肝である。

感覚的には、Aliceはなるべく既に訪れたマスに移動できるならそちらへ移動した方が、可能性の広がりを抑制できそう。

Bobがコマを左右に移動させた場合、Aliceは即座に元に戻せる。

上下に動かした場合、Aliceは左右どちらかに動かさなければならないが、その後、Bobがさらに左右に動かした場合は、即座に元に戻せる。

よって、同じ行では最大3マス分の幅しか、移動させないことができる。

.BAB...
..BAB..  A: Aliceが移動させる可能性のあるマス
.BAB...  B: Bob  が移動させる可能性のあるマス
BAB....
AB.....
BAS....  S: スタートマス
.BAB...
..BAB..
...BAB.

このように、1つずつずれた3マス（壁際は2マス）の範囲の領域における、 “B”のマスの $A_{i,j}$ の合計としてあり得る最小値を求めればよい。

“B”を付けたマスは、全てそこで終了する可能性がある。
Bobは、一度目標のマスに辿り着けたら、Aliceに戻されようと、自分の手番で永遠にそのマスに移動させ続けることができる。

Aliceは、Bobが新しい行に移動させるたび、左右どちらかを選ぶことができる。どちらを選んだ方が得かは、上からと下からのDPで求められる。

$\mathrm{DP}_{up}[i,j]:=$
- Bobは左右と上にしか移動しないとする。
- スタート直後、$(i,j)$ にAliceがコマを移動させた場合の、
- 終了する可能性のあるマスの $A_{i,j}$ の合計としてあり得る最小値
$\mathrm{DP}_{down}[i,j]:=$
- Bobは左右と下にしか移動しないとする。以下同。

Python3

def solve(n, field):
    center = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tmp = 0
            if 0 < j:
                tmp += field[i][j - 1]
            if j < n - 1:
                tmp += field[i][j + 1]
            center[i][j] = tmp
    # print(f'{center=}')
    dp_dn = [[0] * n for _ in range(n)]
    dp_dn[0] = center[0]
    for i in range(1, n):
        dp_dn[i][0] = dp_dn[i - 1][1] + center[i][0]
        dp_dn[i][n - 1] = dp_dn[i - 1][n - 2] + center[i][n - 1]
        for j in range(1, n - 1):
            dp_dn[i][j] = center[i][j] + min(dp_dn[i - 1][j - 1], dp_dn[i - 1][j + 1])
    dp_up = [[0] * n for _ in range(n)]
    dp_up[-1] = center[-1]
    for i in range(n - 2, -1, -1):
        dp_up[i][0] = center[i][0] + dp_up[i + 1][1]
        dp_up[i][n - 1] = center[i][n - 1] + dp_up[i + 1][n - 2]
        for j in range(1, n - 1):
            dp_up[i][j] = center[i][j] + min(dp_up[i + 1][j - 1], dp_up[i + 1][j + 1])
    ans = [[0] * n for _ in range(n)]
    for i in range(n):
        ans[i][0] = dp_dn[i][1] + dp_up[i][1] - center[i][1]
        ans[i][n - 1] = dp_dn[i][n - 2] + dp_up[i][n - 2] - center[i][n - 2]
        for j in range(1, n - 1):
            ans[i][j] = min(
                dp_dn[i][j + 1] + dp_up[i][j + 1] - center[i][j + 1],
                dp_dn[i][j - 1] + dp_up[i][j - 1] - center[i][j - 1],
            )
    return ans


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

目次

第七回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 222）A,B,C問題メモ

A - Colorful Intervals

問題文

制約

解法

B - Circular RPS

問題文

制約

解法

1種類

2種類

3種類

C - 2 Directions vs 4 Directions

問題文

制約

解法