2021-06-20

ABC206 参加記録

3完0ペナ 8分でした
Dに関してはサンプルの値に引っ張られすぎて、正しい考察ができていなかったのが反省です。
E問題は AND 条件を分割して考えることを意識しようと思います。

A - Maxi-Buying

$N$ 円に 1.08 倍して小数点以下を切り捨てます。その値と 206 を比較して、問題文にあるような出力をします。

from math import floor

N = int(input())
res = floor(N * 1.08)
if res > 206: print(":(")
elif res == 206: print('so-so')
else: print('Yay!')

B - Savings

$10^{5}$ から $10^{6}$ の間の加算を行うだけでも、 $10^{10}$ は超えます。（ $10^{5}$ を $9\times 10^{5}$ 加算することになるので）

したがって順に足していき、初めて $N$ を超えたら終了させれば良いです。

N = int(input())
res = 0
for i in range(1, 10**8+1):
    res += i
    if res >= N:
        print(i)
        break

C - Swappable

$A_i \neq A_j$ となる $(i,j)$ の組の数は、全体（全ての $(i, j)$ の組の数）から $A_i = A_j$ となる $(i, j)$ の組の数を引いて求めることができます。

$A_i = A_j$ となる $(i, j)$ の組の数は、 $A$ の要素の出現回数をカウントして、「同じ数を2つ選ぶ」場合を考えれば求めることができます。

N = int(input())
A = list(map(int, input().split()))
counterA = Counter(A)
ans = (N*(N-1))//2
res = 0
for _, cnt in counterA.items():
    if cnt >= 2: res += (cnt*(cnt-1))//2
ans -= res
print(ans)

D - KAIBUNsyo

解説AC です。

まず、サンプルで考えてみると、以下のように、回文になっていないところを確認することができます。

f:id:Xenous:20210620152647p:plain — 回文になっていないところをペアにした図

ここで、5 と 3 と 2 は数珠繋ぎになっています。5 と 3 と 2 のうち、どれかひとつの数字に全て変換しないと回文にすることができません。この場合の答えは、回文にならない数字の集合の大きさから1引いたものになります。

さて、以下の場合はどうでしょうか。

f:id:Xenous:20210620153249p:plain — 回文になっていないところをペアにした図その2

この図では、2と6、1と3と5 をまとめて同じ数字にする必要はなく、それぞれのグループで、ひとつの数字に変換させれば良いです。

グループの管理は unionfind を使えばできます。制約より $A_i \leq 2\times 10^{5}$ なので、 $A$ の値でグループ管理します。あとは各グループの大きさから1引いたものが最小回数になります。

本番ではこのパターンが抜けていました。。気づけなかったのが残念すぎます。

D問題提出コード

# UnionFind は細部を省略して記載
class UnionFind():
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """

    def find(self, x:int) -> int:
        """
        要素 x の親の要素を見つけるメソッド
        """

    def union(self, x:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        """

    def msize(self, x:int) -> int:
        """
        要素 x の属するグループの大きさを返すメソッド
        """


def main():
    N = int(input())
    A = list(map(int, input().split()))
    uf = UnionFind(max(A)+1)
    ans = 0
    for i in range(N//2):
        if A[i] != A[N-i-1]:
            uf.union(A[i], A[N-i-1])
    for g in uf.grouping:
        ans += uf.msize(g)-1
    print(ans)


if __name__ == "__main__":
    main()

ちなみに、もし $A$ の値が $10^{9}$ まで取り得るときでも、 $A$ の値を圧縮する（要素の大きさの順位を $A$ の要素にする）ことで、unionfind で扱える大きさに縮小させて、以下同様に解くことができます。

E - Divide Both

解説AC です。本番では D がイマイチ解けなさそうだったので逆転を狙って E に取り組んでいました。

まず「最大公約数」とか言われると扱いにくいので、基本的な言い換えをします。

「 $\gcd(x, y) = g$ が成り立つ（ $x$ と $y$ の最大公約数が $g$ ）」なら、「 $x$ と $y$ は $g$ の倍数」

これは逆は成り立たないことに注意します。

さて、問題文の条件について見てみます。

$L \leq x, y \leq R$
をとの最大公約数とすると、以下が成り立つ
- $g \neq 1$ ... ① かつ $\frac xg \neq 1$ ... ② かつ $\frac yg \neq 1$ ... ③

① は最大公約数が 1 でないことを意味します。 $x, y$ はともに何かしらの 1 でない自然数の倍数になっているということになります。

②③は、最大公約数 $g$ と $x$ または $y$ が同じ値にならない、と言えます。例えば $x = 6, y = 12$ のとき、 $\gcd(x,y) = 6$ になりますが、これは②を満たしていません。

次にどのように組み立てていくかですが、まずは $g$ によって場合分けします。すなわち、最大公約数が 2 のときの $(x, y)$ の組の数、最大公約数が 3 のときの $(x, y)$ の組の数、... と見ていきます。そこで $(x, y)$ の組の数を洗い出して、②③を満たさないものを除いていきます。

最初の言い換えを使って、 $\gcd(x, y) = 2$ だから、 $x, y$ は 2 の倍数。 $(x, y)$ の組の数は（ $L, R$ の範囲内の）2の倍数の組み合わせだ、とやりたいところですが、例えば $x = 8, y = 12$ はどちらも 2 の倍数でありながら $\gcd(x,y) = 4$ になります。このようなパターンは不適です。

数えたいのは、 $\gcd(x, y)$ がちょうど $2$ になる $(x, y)$ の組の数です。先程の求め方では、 $\gcd(x, y) = 4, 6, 8, ... = 2k$ のパターンが含まれています。したがって、大きい方から順に計算していき、除いていくのが良さそうです。

以上より、まずは最大公約数 $g$ の大きい方から $(x, y)$ の組の数を洗い出していきます。 $L, R$ の範囲だけ考えればよく、最大公約数は $R$ が最大ですから、 $R$ から $2$ （①より $1$ の場合は考えなくて良い）まで見ていきます。

$\gcd(x, y) = R$ となるのは、（ $x$ と $y$ は $R$ の倍数と言えるので） $(R,R)$ だけになります。 $\frac R2$ まではこのように 1 通りになります。

$\gcd(x, y) = k$ については、 $k$ の倍数で構成された数字の組が候補になります。 $R$ までの $k$ の倍数の数字の個数を $Z_k$ とおくと、候補の組は $Z_k^{2}$ 個あります。ちょうど $\gcd(x, y) = k$ となるには、今まで計算した $\gcd(x, y) = mk$ （ $m$ は2以上の整数）の場合の数を除きます。

例えば、下記の例で、例えば $\gcd(x, y) = 3$ を考えます。候補の数字は、3の倍数なので、3と6です。これらの数字を使ったペアの作り方は (3, 3), (3, 6), (6, 3), (6, 6) の4通りあります。各 $g$ について計算すれば $Z_g^{2}$ の行が埋まります。

そして、ちょうど $\gcd(x, y) = 3$ となる組の数を調べるため、最後の行の後ろから埋めていきます。8から5までは2倍すると $R$ を超えるので 1 通りのままです。 $\gcd(x, y) = 4$ は、 $\gcd(x,y) = 8$ の場合に 1 通りダブりが生じるので、それを除いて、3 通りです。 $\gcd(x, y) = 3$ も同じ要領で計算して 3 通りとわかります。

$\gcd(x, y) = 2$ となる組みも同様に、 $\gcd(x, y) = 4, 6, 8$ となる場合にダブりが生じているのでそれを除いて 4 通りになります。

f:id:Xenous:20210620230542p:plain — 計算のイメージ

次に、②③の条件を満たさないものを除きます。

②③の条件は、 $g = x$ または $g = y$ となる場合で、これは $g$ が $L, R$ に含まれているときに除外する必要があります。除くのは $(g, g)$ と、 $(g, kg)$ （ $k = 2, 3, \cdots$ ）とその逆の場合です。

以上で全ての条件を満たした $(x, y)$ の組を数え上げることができました。

実装では、 $\gcd(x, y) = g$ を調べる部分をエラトステネスの篩の要領でテーブルを作ることができます。計算量は $O(R\log{R})$ です。

E問題提出コード

def main():
    L, R = map(int, input().split())
    table = [0] * (R+1)
    for k in range(2, R+1):
        cnt = 0; i = 1
        while k*i <= R:
            if L <= k*i <= R: cnt += 1
            i += 1
        table[k] = cnt
    gcnt = [c**2 for c in table]
    
    for g in range(R, 1, -1):
        i = 2
        while g*i <= R:
            gcnt[g] -= gcnt[g*i]
            i += 1
    
    ans = 0
    for g, t in enumerate(gcnt):
        if g < L: ans += t
        elif L <= g <= R:
            if t <= 1: continue
            ans += t - (table[g]-1)*2 - 1
    print(ans)


if __name__ == "__main__":
    main()

2021-06-13

ARC122 参加記録

AtCoder コンテスト参加記録

1完(C問題)2ペナ 130分でした

A - Many Formulae

各 $A_i$ について、マイナスの個数がそれぞれわかれば良さそうです。 DPplus、DPminus を以下のように定めます。

DPplus[i] : $i$ 番目までで、 $i$ 番目がプラスで終わるようなプラスマイナスの並び方の総数
DPminus[i] : $i$ 番目までで、 $i$ 番目がマイナスで終わるようなプラスマイナスの並び方の総数

遷移は以下のようになります。

f:id:Xenous:20210615213043p:plain — DP の遷移イメージ

この遷移で更新させると、最後の $N$ 番目のマイナスで終わる並び方の総数はわかりますが、それ以前がぱっと見わかりません。実は、表を埋めていくと、以下のような法則が見つけられます。

f:id:Xenous:20210615213318p:plain — 各 $A_i$ でマイナスの場合の数を算出する

DPminus[i] $\times$ DPminus[N-i] の数が、 $A_i$ がマイナスになる場合の数と同じ

以上より、 $O(N)$ で計算することができました。

提出コード

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    # 初期化
    DPplus = [0] * N
    DPminus = [0] * N

    # 初期値
    DPplus[0] = 1

    # 遷移
    for i in range(1, N):
        DPplus[i] = (DPplus[i-1] + DPminus[i-1])%MOD
        DPminus[i] = DPplus[i-1]%MOD
    
    # 場合の数
    al = (DPminus[N-1] + DPplus[N-1])%MOD
    m = [0]
    for i in range(1, N):
        m.append((DPminus[i] * DPminus[N-i])%MOD)
    
    # 答え
    ans = 0
    for i, a in enumerate(A):
        ans += a * (al - m[i]) - a * m[i]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

B - Insurance

自分が失う金額を以下のようにおきます。

$y_{i} = x + A_{i} - \min(A_{i}, 2x)$

求める期待値は次のように表せます。

$\displaystyle \frac1{N}\sum_{i} y_{i} = \frac{Nx + \sum_{i} A_{i} - \sum_{i} \min(A_{i}, 2x)}{N}$

右辺の分母の値の最小化を考えます。各 $y_i$ が凸関数であれば、その和も凸関数であるので、三分探索で見つけることができます。

$y_i = x + A_{i} - \min(A_{i}, 2x)$ について、グラフを描いてみます。 $\min$ の部分で場合分けが必要です。

$A_{i} > 2x$ 、すなわち $\frac{A_{i}}{2} > x$ のとき

$y_i = x + A_{i} - \min(A_{i}, 2x) = x + A_{i} - 2x = -x + A_{i}$

$A_{i} \leq 2x$ 、すなわち $\frac{A_{i}}{2} \leq x$ のとき

$y_i = x + A_{i} - \min(A_{i}, 2x) = x + A_{i} - A_{i} = x$

f:id:Xenous:20210615211703p:plain — $y_i = x + A_{i} - \min(A_{i}, 2x)$ の図

$y_i$ が凸関数ということがわかります。したがって和も凸関数で、求める式の最小化を三分探索します。

実装では、あらかじめ $A$ をソートしておき、累積和を求めておくと、 $\min$ の計算を $O(1)$ でできます。全体では $O(N\log{N})$ でできます。

提出コード

from itertools import accumulate
from bisect import bisect_left

def f(x:int):
    global A, accumulateA, N, sumA
    idx = bisect_left(A, 2*x)
    res = N*x + sumA - accumulateA[idx] - 2*x*(N-idx)
    return res


def main():
    global A, accumulateA, N, sumA
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    sumA = sum(A)
    accumulateA = [0] + list(accumulate(A))

    # 三分探索
    L = 0; R = 10**14+1
    err = 0.0000001
    while abs(R-L) > err:
        c1 = (L*2 + R) / 3
        c2 = (L + R*2) / 3
        if f(x = c1) > f(x = c2): L = c1
        else: R = c2
    ans = min(f(L), f(c1), f(c2))/N
    print(ans)


if __name__ == "__main__":
    main()

C - Calculator

唯一解けました。実装含め70分くらいかかってます。

最初に 1 を加えてから、操作3, 操作4, 操作3, 操作4, ... と操作するのが最も数字を大きくできる方法のように見えます。実際に計算するとこれがフィボナッチ数列になっていることもわかります。

ちなみに $10^{18}$ には、上記のように操作するとして、合計90回くらいで到達できます。

次に操作1, 操作2 の意味について考えます。操作1や操作2を行うと、そこから加算されていく数字がフィボナッチ数列的に増えていきます。

f:id:Xenous:20210613003019p:plain — 遷移例と操作2による差分の増加具合

方針としては、 $N$ を超えない最大のフィボナッチ数を求めて、その値との差分をさらにフィボナッチ数を構成することで縮めていくことを考えます。

以下は $N = 50$ のときの数列の例です。

f:id:Xenous:20210613003359p:plain — $N = 50$ のときの $(x,y)$ の遷移

初手では $34$ が最も( $50$ を超えずに) $50$ に近い数字になります。その差分の $16$ を埋めることを考えます。

$16$ に最も近い数字の $13$ は、一行目の $(x, y)$ の遷移 7番目 (0-index) に初めて出てきています。つまり、差分が $16$ となっているところから 7回前で、操作1 を行うことで、差分を $13$ 埋めることができます。その操作を行なった遷移列が 2 行目の $(x, y)$ の遷移になります。

このように求めたい数字との差を、フィボナッチ数列の値で縮めていくために、何回前に操作1, 操作2 をしておけばいいのかを探索することで、求める操作列を作ることができます。

提出コード

from bisect import *


def fibonacci_l(n, seta=1, setb=0):
    l = [(seta-1, setb)]
    a, b = seta, setb; l.append((a, b))
    for k in range(n):
        a, b = l[-1]
        if k%2 == 0: l.append((a, a+b))
        else: l.append((a+b, b))
    return l


def main():
    N = int(input())
    if N == 1:
        print(1)
        print(1)
        return
    base = fibonacci_l(100)
    baselside, _ = map(list, zip(*base))
    
    ans = base.copy()
    idx = bisect_left(baselside, N)-2
    diff = N - base[idx][0]
    #print(ans[:idx+1])

    while diff > 1:
        #print(diff)
        nextidx = bisect_left(baselside, diff)-2
        i, j = ans[idx+1 - nextidx]
        #print(i, j)
        ans = ans[:idx+1 - nextidx] + fibonacci_l(100, i+1, j)
        lside, _ = map(list, zip(*ans))
        idx = bisect_left(lside, N)-2
        #print(ans[:idx+1])
        diff = N - ans[idx][0]

    #print(idx)
    ans = ans[:idx+1]
    #print(ans)

    res = []
    for k in range(len(ans)-1):
        bfx, bfy = ans[k]
        afx, afy = ans[k+1]
        if bfx == afx:
            if afy == bfy+1: res.append(2)
            else: res.append(4)
        else:
            if afx == bfx+1: res.append(1)
            else: res.append(3)
    
    res.append(1)
    print(len(res))
    print(*res, sep='\n')


if __name__ == "__main__":
    main()

D - XOR Game

少しだけ考えました。あとで解きたい問題です。

2021-06-06

ABC204 参加記録

AtCoder コンテスト参加記録

3完1ペナ 24分でした

A - Rock-paper-scissors

じゃんけんの値を調べて、同じならあいこを出し、異なるなら残り一つを出します。

x, y = map(int, input().split())
if x == y:
    print(x)
else:
    print(3-x-y)

B - Nuts

木の実を一つずつ確認して、問題文の通りに処理します。

N = int(input())
A = list(map(int, input().split()))
ans = 0
for a in A:
    if a > 10: ans += a - 10
print(ans)

C - Tour

各頂点から出発して、BFS を行って到達できる頂点を調べます。計算量は、BFS が $O(N+M)$ で、各頂点を巡るので $O(N(N+M))$ となります。

C 問題提出コード

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1; B -= 1
    graph[A].append(B)

ans = set([])
for i in range(N):
    fr = i
    que = deque([fr])
    goneset = set([fr])
    count = [-1] * N; count[fr] = 0
    while True:
        fr = que.popleft()
        for to in graph[fr]:
            if to in goneset:
                continue
            count[to] = count[fr] + 1
            que.append(to)
            goneset.add(to)
        if len(que) == 0:
            break
    for j, c in enumerate(count):
        if c != -1: ans.add((i, j))
print(len(ans))

D - Cooking

この DP が苦手すぎて、同じ問題を 3 度解けていません。。。（これ苦手なやつだ、となりそのまま終わってしまいました。）

最初に思いついた方針は嘘解法でした。

$A$ を大きい順(降順)に並べる。
それぞれのレンジの使用合計時間の短い方に入れる。同じ場合はレンジ1に入れる。

これは、以下のようなパターンで WA となります。

6
9 10 13 20 17 4

嘘解法では、「20、10、9」「17、13、4」が選択され、合計は 39 です。一方、実際は「9、10、17」「20、13、4」で 37 が最短になります。

しかし嘘解法が正しいと思い込んでいる間は反例をなかなか作り出すことができず、この問題を後回しにしてしまいました。反省として、全探索ができる範囲でテストケースをランダムに作成してテストすることにしました。

さて、嘘解法の反例が見つかったところで、正しい回答の方針です。まず片方のオーブンにかかる時間がわかれば、もう一方は自動的に定まります。したがって、問題文を次のように言い換えるとわかりやすくなります。

$N$ 品の中からいくつかを選び、1つ目のオーブンで調理します。あり得る調理時間を全て洗い出してください。

洗い出した調理時間からもう一方も加味して、最短になるものを選べば良いです。

ここで、調理時間の候補が膨大だと成り立たないわけですが、問題文の制約で $N \leq 100$ 、 $T_i \leq 10^{3}$ がわかっており、最大でも $10^{5}$ までの時間ということがわかります。したがって今回は可能な範囲です。

調理時間の候補を洗い出すには、以下のような遷移を考えます。

$10^{5}$ までの配列 $\mathrm{DP}$ を用意する。中身の値について、候補の調理時間は 1 とし、それ以外を 0 とする。初期値として $\mathrm{DP}_0 = 1$ を入れる。（何一つ選ばなかったときの調理時間は 0）
品を順に見ていく。
- $1$ 品目を選んだ場合、 $\mathrm{DP}_{T_1} = 1$ とできる。選ばない場合は $\mathrm{DP}_{0} = 1$ のまま。
- $2$ 品目は、配列上の候補の調理時間（2品目の場合 $\mathrm{DP}_0$ と $\mathrm{DP_{T_1}}$ ）のそれぞれに対して、2品目を選んだ場合、選ばなかった場合を考える。
- ... これを $N$ 品目まで繰り返す。

f:id:Xenous:20210613165829p:plain — DP 遷移のイメージ

$i$ 品目を選んでいるときは、 $i-1$ 品目を選び終わった状態の DP を参照する必要があります。逆にいうとそれ以前の情報はもう使わないので、実装上は更新前と更新後の2種類を使い回していけば良いです。

最後に、各候補の値について、もう一方のレンジにかかる時間を出しておき、全て調理するまでの時間を計算した結果の最小値を答えとします。

計算量は $O(N^{2}T)$ です。大体 $10^{7}$ くらいで、間に合います。

以下が参考コードです。

D 問題提出コード

def main():
    N = int(input())
    T = list(map(int, input().split()))

    # 初期化
    DPbf = [0] * (1000*N+1)
    DPaf = [0] * (1000*N+1)

    # 初期値
    DPbf[0] = 1
    sumT = sum(T)

    # 遷移
    for i in range(N):
        for j, k in enumerate(DPbf):
            if k == 1: 
                DPaf[j] = 1
                DPaf[j+T[i]] = 1
        DPbf = DPaf.copy()
        DPaf = [0] * (1000*N+1)

    # 答え
    ans = float('inf')
    for k, flag in enumerate(DPbf):
        if flag == 1:
            ans = min(max(k, sumT-k), ans)
    print(ans)


if __name__ == "__main__":
    main()

さて、このD問題は bitset の考え方で実装することもできます。先程の DP の遷移ですが、調理時間の候補になるかどうかを 0 と 1 で対応させたとき、DP は二進数として見ることができます。また、更新の動きをよく見ると、右シフトと OR 演算で更新できます。

f:id:Xenous:20210613222703p:plain — bitset の考え方イメージ

python3 では、整数 int が多倍長整数なので、整数の値の大きさを特に気にすることなく実装できます。そのまま整数値と bit の状態を対応させます。

最大は 1<<(10**5) で、とてつもなく大きな数字ですが気にせず実装します。DP の解法よりはコードがシンプルになります。

D 問題 bitset の考え方に基づくコード

def main():
    N = int(input())
    T = list(map(int, input().split()))
    # 二進数表記で考える
    DP = 1 << (1000*N)
    sumT = sum(T)

    for i in range(N):
        # 右にシフトして OR をとる
        t = DP >> T[i]
        DP |= t

    # 答え
    ans = float('inf')
    cnt = 1 << (1000*N+1)
    for k in range(1000*N+1):
        cnt >>= 1
        if cnt & DP != 0:
            ans = min(max(k, sumT-k), ans)
    print(ans)


if __name__ == "__main__":
    main()

実行速度は以下のようになりました。(平均とかは取ってません。）

python 3.8.2 DP配列: 702ms
python 3.8.2 bitset: 488ms
pypy3 bitset: 458ms
pypy3 DP配列: 189ms

pypy だとリストへのアクセスが python に比べて超高速になるので、こちらの方が速くなっているようです。一方 bitset では大きな差にはなりませんでした。

E - Rush Hour 2

三分探索で実装しましたが、見事に穴にハマりました。

後々記載します。

2021-06-06

ABC203 参加記録

AtCoder コンテスト参加記録

3完0ペナ 97分でした
E問題解けたと思いましたが、、TLE で3完になりました。しばらく一度に提出するのを控えようと思います。

A - Chinchirorin

if 文を使って条件を列挙し、問題文の通りに判定します。

a, b, c = map(int, input().split())
if a == b: print(c)
elif a == c: print(b)
elif b == c: print(a)
else: print(0)

B - AtCoder Condominium

部屋番号の整数を実際に構成して、足し合わせて答えとします。 $1 \leq N, K \leq 9$ なため、計算量は余裕です。

N, K = map(int, input().split())
ans = 0
for i in range(1, N+1):
    for j in range(1, K+1):
        ans += i*100 + j
print(ans)

C - Friends and Travel costs

$10^{100}$ が大きいのでここまで行き着くかまずは考えてみます。最初に $10^{9}$ 円を持ち、 $2 \times 10^{5}$ 人から $10^{9}$ 円をもらう場合でも $2 \times 10^{14}$ くらいで終わります。よって最後に到達することは考えなくて良さそうです。

友達からもらうお金は、辿り着ける村の順番にあらかじめソートします。順に見ていく中で、辿り着いたときに負の値になると、途中でお金が足りなくなったと判断します。

N, K = map(int, input().split())
l = [(0, 0)]
for _ in range(N):
    A, B = map(int, input().split())
    l.append((A, B))
l.sort(key=lambda x: x[0])
i = 0; 
for a, b in l:
    if K < a - i:
        print(i + K)
        return
    K -= a - i
    i += a - i
    K += b
print(i + K)

D - Pond

本番では方針さえ全然思いつきませんでした。二分探索で答えを決め打ち、0 1 に変換する方針の問題は前にも出てきていたのでちゃんと覚えておきたい典型です。

マスの行列の大きさの最大が $800$ なため、各マスを探索する分には $O(N^{2})$ で十分間に合います。そこから中央値の探索をすることを考えます。

中央値は値そのものよりも順位を見る統計量です。 $K\times K$ の区画を動かすことを考えたとき、元々の中央値の値より小さい値(もしくは大きい値)がいくつ抜けていくつ入ってきたかを考えようとしました。この場合、行または列で少なくとも $O(K)$ の確認を行う必要があり、最終的に $O(N^{2}K)$ になります。大体 $6\times 10^{7}$ くらいになるのでそこそこ厳しいです。また、同じ値が出入りしたときの更新の方法も簡単ではなさそうです。

答えを二分探索で決め打ちしたとき、全てのマスについて、その決め打ちした値以上か？それとも未満か？を 0 1 で表現できます。 $K \times K$ の区画で、1 の数が $\lfloor\frac{K^{2}}{2}\rfloor +1$ 個以上あれば、その値は中央値になる可能性があります。

この確認を全ての区画( $(N-K)^{2}$ 個の区画)で行って、少なくとも一つ中央値になる可能性があるとなれば、二分探索の上限を小さくでき、そうでないなら下限を大きくします。

$K \times K$ の区画で 0 1 の個数の集計をそのままやると、区画ごとに $O(K^{2})$ かかり TLE ですが、二次元累積和を使えば前処理に $O(N^{2})$ 、区画の 0 1 の個数集計は $O(1)$ で答えられます。

二分探索は $O(\log{a_{\max}})$ で済むので、全体で $O(N^{2}\log{a_{\max}})$ で解けます。

D問題提出コード

def accumulate_2d(field:list, H:int, W:int) -> list:
    """
    二次元累積和を計算する
    """
    res = [[0]*(W+1)]
    for i in range(H):
        tmp = field[i].copy()
        res.append([0] + tmp)
    for i in range(1, H+1):
        for j in range(1, W+1):
            res[i][j] += res[i-1][j] + res[i][j-1] - res[i-1][j-1]
    return res


def f(n):
    global A, N, K
    # 0 1 判定
    B = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            B[i][j] = A[i][j] >= n
    # 累積和テーブル
    field = accumulate_2d(B, N, N)
    # 各区画で個数計算
    l = K; r = K
    for k in range(N-l+1):
        for j in range(N-r+1):
            tmp = field[l+k][r+j] - field[k][r+j] - field[l+k][j] + field[k][j]
            if tmp < K**2//2+1: 
                # ある区画でより小さい値が中央値になる
                return False
    return True


def main():
    global A, N, K
    N, K = map(int, input().split())
    A = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        A.append(tmp)
    
    R = 10**9+1 # right side
    L = 0 # left side
    while True:
        if L+1 >= R:
            break
        mid = (L+R)//2
        t = f(n=mid) # boolean function
        if t: L = mid # True
        else: R = mid # False
    ans = L
    print(ans)


if __name__ == "__main__":
    main()

E - White Pawn

本番で、解き方は割とすぐ思いつきましたが、TLE を解消できませんでした。

黒ポーンの配置の制約から、境界については考える必要はなさそうです。サンプルにあるようなケース以外にも、特に下記の場合の動きを正しく管理するにはどうするか？を考えます。

f:id:Xenous:20210606132216p:plain — 確認した自作テストケース

黒のポーンが置かれている位置についてソートし、左端から順に見ていきます。各黒ポーンの時点で、到達できる $y$ 軸の値を集合 (この集合を $S$ とおきます) で管理します。

まず、新しく移動可能になる $y$ 座標について考えます。このポーンの $y$ 座標を $q$ とおくと、 $q$ が $S$ に含まれておらず、 $q+1$ または $q-1$ が $S$ に含まれているなら、 $S$ に $q$ を追加することができます。

次に、移動可能だった場所が移動できなくなるパターンを考えます。これは「 $q+1$ と $q-1$ が $S$ に含まれていない」かつ「 $q$ が $S$ に含まれている」が成り立つときです。このとき $q$ を $S$ から削除します。

以上で要素の管理のルールは表現できました。あとはこれを間に合うように更新させていきます。

黒ポーンをソートして順に見ていくので、ここまでで $O(M\log{M})$ かかります。要素の追加と削除ですが、set 型の union() や difference() を使用すると、結合させる集合どうしの大きさに比例して計算量が大きくなり、 $O(MN\log{M})$ となって間に合いません。

追加と削除の要素は高々ポーンの数しか出てこないことを考えると、直接要素を add、remove したほうが高速でした（具体的な計算量はわかりませんでした）。

E 問題提出コード

def main():
    N, M = map(int, input().split())
    dots = dict()
    for _ in range(M):
        X, Y = map(int, input().split())
        if X not in dots: dots[X] = set([])
        dots[X].add(Y)

    X = list(dots.keys())
    X.sort()
    status = set([N])
    for x in X:
        yset = dots[x]
        able = set([])
        stop = set([])
        for y in yset:
            if y-1 in status or y+1 in status and y not in status: able.add(y)
            if y in status and y-1 not in status and y+1 not in status: stop.add(y)
        for a in able:
            status.add(a)
        for s in stop:
            status.remove(s)
    ans = len(status)
    print(ans)


if __name__ == "__main__":
    main()

2021-06-05

ARC121 参加記録

AtCoder コンテスト参加記録

コンテストから時間あけてしまいました。
1完 95分でした

A - 2nd Greatest Distance

40分ごろに提出できそうでしたが、だいぶ遅かったため B問題を解いたタイミングで出すようにしました。(失敗しましたが...)

$N$ 個の点があり、点 $i, j$ の距離が $\max{(|x_{i} - x_{j}|, |y_{i} - y_{j}|)}$ で定められています。距離の定義から、 $x$ 軸方向と $y$ 軸方向別々に見ても良さそうですね。それぞれでもっとも遠いところから2番目を考えます。

気になるパターンは、 $x$ 軸と $y$ 軸を別々に比べたときに、実は同じ頂点を見ていた、という場合です。 $x$ 軸で調べた値と $y$ 軸で調べた値を並べてしまうとこのようなことが起こります。場合分けを考え始めると煩雑になるため、間違いなく二番目の頂点が含まれている部分まで候補の点を出し、その中で全探索します。

$x$ 軸で考えます。もっとも遠いのは左端の頂点と右端の頂点をとってきた場合です。その次に短いのは、右端の代わりにその一つ手前の頂点を取ること、左端の代わりに次の頂点をとることになります。従って、候補はこの時点で三つ出てきます。

$y$ 軸も同様に考えたとき、頂点を集合で管理すれば、最小三つ、最大六つになります。この中で定義通りの距離を求めて二番目を求めればOKです。

B - RGB Matching

この問題の教訓は、Counter 使う前に sort しろ、です。もったいない。。

R, G, B の各色について、それぞれ同色が2つずつペアにできれば不満度は 0 です。つまり、各色の個体数が偶数なら 0 です。

次に、そうでない場合というのは、偶数、奇数、奇数のパターンしかありません。合計が偶数になるためです。従って、色によらずこの一つのパターンだけ考えればOKです。以下では、R(偶数)、G(奇数)、B(奇数)とします。

このとき、ペアにならない犬について不満度が小さくなるような組み合わせを見つけます。以下の2つの場合が考えられます。

GのあまりとBのあまりをくっつける
GのあまりとR、BのあまりとR をくっつける

あらかじめ、R、G、Bにおいて、どの値が何個あるかを数えておきます。例えば G の不満度の値を固定して、その値を B のとりうる不満度の列で二分探索し、もっとも差が小さくなるものを見つけます。

これを上記の2パターンでやって、小さい方が答えです。

実装では、個数のカウントに collection.Counter() を使います。辞書型のオブジェクトで、.keys() でキーを取得できます。これに対して二分探索をするのですが、事前にソートしておけば、.keys() の値もソートされた状態で取得できます。

2021-05-23

ABC202 参加記録

AtCoder コンテスト参加記録

4完0ペナ 56分でした

A - Three Dice

サイコロの反対の値は、出た目を $x$ とおくと、 $7-x$ で表せます。あとは加算して答えです。

a, b, c = map(int, input().split())
a = 7-a; b = 7-b; c = 7-c
print(a+b+c)

B - 180°

180度回転で行わないといけない操作が問題文に定義されているので、それを行います。先に数字を変換してから逆順に出力しました。

S = input()
ans = []
for s in S:
    if s == '6':
        ans.append('9')
    elif s == '9':
        ans.append('6')
    else:
        ans.append(s)
ans.reverse()
print(''.join(ans))

C - Made Up

$B_{C_j}$ の解釈から考えます。サンプル 1 を例にとります。

Cとして 2 3 2 が与えられています。最初の値( $j=1$ )は $C_{1} = 2$ です。したがって $B_{C_j} = B_{2} = 1$ です。

さて、このとき $A_i = 1$ となる $i$ の個数を求めます。これは単純に、数列 A の中で 1 が何個あるか先に数えておけば良さそうです。

同じ要領で $j=2$ 、すなわち $B_{C_j} = B_{1} = 3$ と同じになるような $i$ の個数を数えて、... を繰り返し、全ての $j$ について数え上げればOKです。

あらかじめ A の要素のカウントを collections.Counter で行うと良いと思います。Cの値はBのインデックスになるので、あらかじめ 1 を引いておきます。

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [x-1 for x in map(int, input().split())]

Acounter = Counter(A)
ans = 0
for c in C:
    x = B[c]
    ans += Acounter[x]
print(ans)

D - aab aba baa

まず制約で $1 \leq A, B \leq 30$ とあります。a と b の並び替えで一番大きな計算は $_{60}\mbox{C}_{30}$ ですが、python はこの計算をオーバーフローを気にせず実行できます。オーバーフローに気をつけて計算する場合は、パスカルの三角形を用いて計算しておくと良さそうです(たぶん)。

後は b の位置で数え上げを行います。例えば a の個数が 4 つ、b の個数が 3 つの場合、まずは左から見て 1 つ目の b の位置で場合分けをして、数え上げていきます。

f:id:Xenous:20210523142246p:plain — b の位置で分ける数え上げのイメージ

例えば $K = 15$ としたとき、11〜20 の部分に含まれるので、左の ab は確定します。次は、残りの aaabb について同様にして調べれば良いです。

f:id:Xenous:20210523145051p:plain — K = 15 のときの探索の流れ

本番では結構バグって時間がかかってしまいました。スパゲティコードになってますが一応参考までに載せておきます。

D問題提出コード

def nCk(n:int, k:int) -> int:
    """
    nCk の値を O(n) で計算する. (n-k)! // k! の計算を行う.

        Parameters:
        -----------
        n, k: int
            nCk に該当する0以上の整数
        
        Return:
        -------
        int
            nCk の計算結果.
            n または k が 0 より小さい場合は 0 を返す.
            n が k より小さい場合も 0 を返す.
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    k = min(k, n-k)
    numer = 1
    for i in range(n, n-k, -1):
        numer *= i
    denom = 1
    for i in range(k, 1, -1):
        denom *= i
    return numer // denom


def main():
    A, B, K = map(int, input().split())
    if K == 1:
        ans = 'a'*A + 'b'*B
        print(ans)
        return

    cnt = 0; Acnt = A; Bcnt = B
    ans = ''
    # K がどこにあるか探索する
    while True:
        for i in range(0, Acnt+1):
            # b の位置を固定したときの場合の数
            res = nCk(i+(Bcnt-1), min(i, Bcnt-1))
            if res == 0:
                # a または b の数が 0 になったら脱出
                break
            if cnt < K <= cnt+res:
                break
            cnt += res
        if res == 0:
            # a または b の数が 0 になったら、後ろに残りの a の数分くっつけるだけ
            ans += 'a'*Acnt
            break
        # 確定した部分を入れる
        ans += 'a'*(Acnt - i) + 'b'*(Bcnt > 0)
        Acnt = i
        if Bcnt > 0: Bcnt -= 1
        if Bcnt == 0 and Acnt == 0:
            break
    print(ans)


if __name__ == "__main__":
    main()

E - Count Descendants

解説ACです。本番では二重の辞書(dict 型の value に dict を持つ)で、DFSで戻ってくる際に、各頂点の「深さ」と「頂点番号」を集合管理することでクエリに答えようとしましたが、マージする際に木の情報を上書きしてしまい、うまくいきませんでした。

解説にあるように、DFS で巡った順に番号を振っていくと、かなり見通しが良くなります。以下は例です。

f:id:Xenous:20210525125825p:plain — 頂点に初めて訪れたとき(青色)と、最後にその頂点から出ていくとき(赤色)の時刻

深さごとに、それぞれ入りの時刻を保持しておくと、以下のように整理できます。ここで例えば「頂点 $2$ を含む長さ $2$ のパスが作れる頂点の個数」を考えたとき、depth が 2 の行において、頂点 $2$ の入った時刻と出た時刻の間にある要素の個数を見ると、それが頂点 $2$ を通る長さ $2$ のパスになっていることがわかります。

f:id:Xenous:20210525131710p:plain — 深さごとに入りの時刻を整理した図

この頂点の探索を二分探索で行えば、各クエリに $O(\log{N})$ で応答できるので、最終的には $O(N + Q\log{N})$ で十分間に合います。

今回の番号の振り方は下記でも練習できます。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja

2021-05-22

AtCoder 水色になりました

振り返り

AtCoder 水色になりました。

f:id:Xenous:20210522105951p:plain

ということで、簡単に振り返りで、モチベーションについてと、精進してきたことを書き残しておきます。精進部分については緑や水色を目指す方の参考になれば幸いです。

まずは簡単な自己紹介です。

社会人です。
修士卒です。一応数学科にいて、途中から統計学の方へシフトしました。
SIer です。業務でコードは書いてません。
AtCoder 初参戦は2019/11 本格参加は2020/03 です。
PAST は第3回、第5回ともに中級です。

モチベーションについて

色々な方が竸プロのモチベーションについて書いていたりしますが、私の場合はレートです。完全にオンラインゲーム感覚です。昔から結構オンラインゲームにハマっていて、そのゲームでのウデマエ(=レート)を上げるのが楽しいんですよね。竸プロの場合、ウデマエはアルゴリズムの理解と応用力でしょうか。一目見て解法が思い浮かぶ人は本当にすごいと思います。

直大さんのブログでの色の説明や、E8さんの記事を見るとおおよそ水色が竸プロerにおいては中級者なのかなと思い、2020年中に水色を目指してプレイしてました。5ヶ月ほど遅れてしまいましたが、水色になることは達成できました。

精進方法について

今までにどういう方針で何をやったかを前半で、問題を解くときにやっていたことを後半で記載します.

どういう方針で何をやったか

目標の色レート帯になるには、なりたい色のパフォーマンス値を取る必要があります。パフォーマンスはコンテストの出来で決まりますが、「自分と同じレート帯が解ける問題を早く解くこと」、または「自分と同じレート帯の人が解けない問題を解くこと」で高い値を得ることができます。

よって、精進の方針として、「見た瞬間わかる」くらいになること(数の暗黙知？)と、「自分にとって難しいと思える問題を解けること」の二軸で進めることにしました。

さて、水色を目標としたときに、水色においての基礎知識を E8 さんがまとめた記事があります。精選100問です。こんな素晴らしくまとめてくださった記事を使わない手はないと思い、最初はこれに取り組み始めました。

しかし、DPは全く理解できず、、自分にとってわかりやすそうなものと出題頻度をみて、優先順位を決め、精選100問のうち以下の内容を先に取り組みました。

全探索、二分探索、bit全探索、DFS、BFS、ダイクストラ
DP超基礎編のみ
UnionFind、累積和、いもす法
試し割り法による素因数分解、約数列挙
高速な組み合わせ nCk の計算

また、上記がわかったつもりでもコンテスト中気づけなかったり、解ききれないことも多く、そもそも竸プロの問題に慣れる必要があると思いました。そこで、AtCoder Problems の bootcamp を使います。 Atcoder Problems では、Beginner 向けに bootcamp 300問が用意されてます。これの easy 2 問、medium 2問、hard 2問の計6問のバチャを作ってやってました。

これらを解き切った頃には緑色に到達し、レートも1000越えしていたと思います。ちょうど2020年の11月ごろで、半年間はかかってます。その後はだいぶ問題に慣れたので、精選100問の中級編の余りと、上級編でコンテストによく出てくるものを一旦さらっておくようにしました。以下が取り組んだ内容です。

DP(ナップザックDP、区間DP、bitDP、LIS)
ワーシャルフロイド法
最小全域木の構成法(クラスカル法)
座標圧縮
半分全列挙
平方分割
Binary Index Tree
セグメント木
遅延評価セグメント木

他に、コンテスト中に知っておく必要があるなと思って調べたことです。

エラトステネスの篩
桁DP
確率DP、期待値DP

セグメント木などは、自分で実装してみたりしたものの、使えるようにするだけで一週間くらいかかってました。これらを履修した後でも相変わらず緑でした。おそらく周りの方々も精進し続けて、全体のレベルが上がっているのでしょう（そう思いたい）。

上記全て取り組み終わったのがちょうど2021年2月くらいです。それ以降は水・青diffを時間が取れそうな日に取り組んでいましたが、コンテストでDPがまだ解けていなかったため、あんまりやりたくなかった Educational DP Contest に取り組みます。

現状まだ取り組み途中ですが、ちょうどABC201のD問題が水diffのDPの問題で、このおかげ？で色変することができました。引き続き EDPC に取り組み、そのあとは上級編の残り、典型90問と ACL に取り組もうかと思ってます。

ここまで、やったことをまとめるとこんな感じです。

(灰~茶のとき) 2020/03 ~ 2020/05: 精選100問中級編（全探索、DFS/BFS、累積和、unionfindあたり）
(茶~緑のとき) 2020/05 ~ 2020/11: AtCoder Problems Bootcamp for Beginner 300問
(緑後半のとき) 2020/11 ~ 2021/02: 精選100問中級編のこり、上級編一部
(最近) 2021/03 ~ 2021/05: 水青埋め、EDPC

問題を解くときにやっていたこと

よく議論になる点について私の考えを書いておきます。

解説をどのタイミングで見るか？

解説を見る前に10〜30分は自分の頭で解法を考え、計算量を見積もって、イケそうなら実装するまでやったほうがいいと思います。そうするほうが記憶に残りやすいのと、「自分の考えた解法がなぜダメなのか」を考えることができます。これは間違った解き方において反例を出す能力が向上すると思います。

解説をさっさとみたほうが効率的な気もしますが、結果的に記憶に残る方を選んでやれば良いと思ってます。

Streak を切らさないほうがいいのか？

一時期 Streak を切らさないようにしていましたが、切らさないようにABCのA問題を解くなどした時期もあり、いい面も悪い面もあるかなと思います。

難しい問題に取り組んで Streak を繋げようとすると、一日で解けない場合や、WAが出て焦ったりして精神衛生上良くないことが私にはあったので、コントロールが難しいですね。

問題を解く週間をつけたいとか、問題に触れる時間がなくなってしまった時に、無理矢理時間を作る意味で取り組むのがいいかなと思ってます。

終わりに

振り返りで色変記事を書いてきました。他の方の精進の参考になれば嬉しいです。これからもウデマエを上げて、青を目指していきたいと思います！

Xenous の精進記録

AtCoder関連他、学習したことの記録です。

ABC206 参加記録

A - Maxi-Buying

B - Savings

C - Swappable

D - KAIBUNsyo

E - Divide Both

ARC122 参加記録

A - Many Formulae

B - Insurance

C - Calculator

D - XOR Game

ABC204 参加記録

A - Rock-paper-scissors

B - Nuts

C - Tour

D - Cooking

E - Rush Hour 2

ABC203 参加記録

A - Chinchirorin

B - AtCoder Condominium

C - Friends and Travel costs

D - Pond

E - White Pawn

ARC121 参加記録

A - 2nd Greatest Distance

B - RGB Matching

ABC202 参加記録

A - Three Dice

B - 180°

C - Made Up

D - aab aba baa

E - Count Descendants

AtCoder 水色になりました

モチベーションについて

精進方法について

どういう方針で何をやったか

問題を解くときにやっていたこと

終わりに