AtCoder Beginner Contest 196

初めて PythonJava の二刀流で参加した.A-E は Python で解いて,F は TL の関係で Java で解いた.

A - Difference Max

一瞬場合分け問題かと思ったけど,冷静になると  x=b,y=c が最適で,答えは  b-c.これはどっちの言語でもそんなに変わらなさそう.

_, b = map(int, input().split())
c, _ = map(int, input().split())
print(b - c)

B - Round Down

これは in とスライスを気軽に使える Python が楽.

X = input()
if '.' in X:
    X = X[:X.index('.')]
print(X)

C - Doubled

 N は最大で  10 ^ {12} にもなるので,全探索は間に合わない.そこで,前半分だけを全探索することにすれば, \sqrt{N} 通り程度で済むので間に合う.

実装上は  \sqrt{N} ではなく  10 ^ 6 を上限に取ってしまう方が楽?累乗を前計算したけど,文字列に変換してつなげて整数に戻す方が良かったかも.

N = int(input())
p = [1]
for i in range(10):
    p.append(p[-1] * 10)
A = 0
for i in range(1, 1000001):
    l = len(str(i))
    x = i * p[l] + i
    if x <= N:
        A += 1
print(A)

D - Hanjo

 HW\leq 16 と制約が小さいので,既に埋まった畳の集合  S を状態に持つ DP をベースに考える.あとは  1\times 2 の畳の枚数  a 1\times 1 の畳の枚数  b も持てば,めでたく遷移が書ける.

制約より  b S a から一意に定まるので状態として持つ必要はないが,(メモ化再帰の場合は) 持っても探索空間は増えないので持っておくと多少楽が出来る.

マス  (i, j) に整数  iW + j を割り当て,まだ畳が敷かれていない最小の整数に対応するマスを含むように畳を置いていくことで重複なく数え上げることが出来る.

H, W, A, B = map(int, input().split())
N = H * W
D = {}

def dfs(s, a, b):
    if s == (1 << N) - 1:
        return 1
    if (s, a, b) in D:
        return D[(s, a, b)]
    res = 0
    for i in range(N):
        if (s >> i) & 1 == 0:
            if a:
                r, c = divmod(i, W)
                if c < W - 1 and (s >> i + 1) & 1 == 0:
                    res += dfs(s | 1 << i | 1 << i + 1, a - 1, b)
                if r < H - 1 and (s >> i + W) & 1 == 0:
                    res += dfs(s | 1 << i | 1 << i + W, a - 1, b)
            if b:
                res += dfs(s | 1 << i, a, b - 1)
            break
    D[(s, a, b)] = res
    return res

print(dfs(0, A, B))

E - Filters

難しくない?20 分近く掛かった.

関数の形を観察すると, f_i(\cdots (f_2(f_1(x)))\cdots) は図 E に示すような形 になっていることが分かる.

f:id:suisen_kyopro:20210321005243p:plain
図 E

従って,図中の  L,R,U,D をうまく更新できればクエリに高速に答えることが出来る.

初め, L=D=-\infty,R=U=+\infty としておく.そして, t_i の値によって  L,R,U,D は以下のように更新することが出来る.

  •  t_i=1 のとき:  D\leftarrow D+a _ i,U\leftarrow U+a _ i と更新
  •  t_i=2 のとき:  D の変化量に注目すると,これは  \max (0,a _ i-D) である. L も同じだけ変化するので, D\leftarrow D+d,L\leftarrow L+d と更新できる.注意しないといけないのは, a _ i \gt U である場合は  U,R も更新されるという点である.これは, U\leftarrow \max (U,D), R\leftarrow \max(R,L) とすればよい.ここで, D,L は更新後の値である.
  •  t_i=3 のとき:  t_i=2 のときと同様に考えればよい.
N = int(input())
INF = 10 ** 18
D, U = -INF, +INF
L, R = -INF, +INF
for _ in range(N):
    a, t = map(int, input().split())
    if t == 1:
        D += a
        U += a
    elif t == 2:
        d = max(0, a - D)
        D += d
        L += d
        R = max(L, R)
        U = max(U, D)
    elif t == 3:
        d = max(0, U - a)
        U -= d
        R -= d
        L = min(L, R)
        D = min(U, D)

input()
for x in map(int, input().split()):
    if x <= L:
        print(D)
    elif x >= R:
        print(U)
    else:
        print(D + (x - L))

F - Substring 2

問題の F.bitset による 64 倍高速化で通せそうな雰囲気を感じたので,その方針を採用した (コンテスト後に分かったが,これは落とされるべき解法だったらしい).

以後, S[l:r] S l 文字目から  r-1 文字目までの部分文字列を表すものとする.

 N=|S|,M=|T| とする. S および  T を二進数として解釈すれば,\displaystyle \min _ {0\leq i\leq N-M}\{\mathrm{popcount}(S[i:i+M]\oplus T)\} を求める問題と言い換えられる.ここで, \oplus はビット毎の排他的論理和 \mathrm{popcount}(x) は整数  x の二進数表記における  1 の個数である.

 \mathrm{popcount}(S[i:i+M]\oplus T) を求める際に, S および  T を 64 bit 毎に区切って 64 bit 整数の配列に押し込むことで排他的論理和および popcount の計算の回数を削減することを考える.

 S[i:i+M] T の間で,64 bit 整数の境目が完全にかみ合っている場合は演算の回数は 1/64 となりかなりの高速化が期待できる.

しかし,当然うまくかみ合わない場合も存在する.この場合は各整数を 2 分割して比較する必要があるため,理想ケースに比べて 2 倍遅くなってしまう.

文章で書くと分かりにくいので,図を示す.1/64 となるケースが図 F-1 であり,1/32 となるケースが図 F-2 である.

f:id:suisen_kyopro:20210321012849p:plain
図 F-1. 境目が一致する理想ケース

f:id:suisen_kyopro:20210321013220p:plain
F-2. 境目が一致しないケース

図から分かるように,演算回数が 1/64 となるケースは全ての  i のうち 1/64 程度しか存在しない.これでも愚直な実装に比べて 32 倍程度の高速化は期待できるが,この問題においては不十分であり TL には間に合わない.

そこで,さらなる工夫を考える.各  S[0:N],S[1:N],\ldots,S[63:N] に対して 64 bit 毎の分割を行い,配列を作成しておく.これにより, i の値によって適切な配列を選択すれば,必ず理想ケースに落とし込むことが出来る.具体的には, S[i\bmod 64:N] に対応する配列を選択するようにすればよい.

実装においては,最後の端数の処理がやや面倒であるが,本質部分とは言えないので説明を省略する.詳しくは以下の Java による実装を参照.

String s = sc.next();
String t = sc.next();
int n = s.length();
int m = t.length();

// 開始位置の mod 64 の値ごとに 64 bit 分割を行う.
long[][] x = new long[64][];
for (int i = 0; i < 64; i++) {
    // 切り上げ除算
    int p = (n - i + 63) / 64;
    long[] r = x[i] = new long[p];
    for (int j = 0; j < p; j++) {
        // Long.parseLong を使用した場合,64 bit 目が 1 だと実行時エラーとなる.
        r[j] = Long.parseUnsignedLong(s, i + (j << 6), Math.min(n, i + (j + 1 << 6)), 2);
    }
}
// 切り上げ除算
int p = (m + 63) / 64;
long[] y = new long[p];
for (int j = 0; j < p; j++) {
    y[j] = Long.parseUnsignedLong(t, j << 6, Math.min(m, j + 1 << 6), 2);
}

int ans = m;
// 開始位置を全探索
for (int i = 0; i + m <= n; i++) {
    int k = i >> 6;
    int r = i & 63;
    long[] a = x[r];
    int sum = 0;
    for (int j = 0; j < p - 1; j++) {
        sum += Long.bitCount(a[k + j] ^ y[j]);
    }
    // 末項の帳尻合わせ
    int l1 = k + p == a.length ? (n - i) & 63 : 64;
    int l2 = l & 63;
    // signed shift (>>) とした場合空いた部分は元の符号 bit によって埋められるため,unsigned shift (>>>) を用いる必要がある.
    long v1 = a[k + p - 1] >>> (l1 - l2);
    long v2 = y[p - 1];
    sum += Long.bitCount(v1 ^ v2);
    ans = Math.min(ans, sum);
}
pw.println(ans);