第二回全国統一プログラミング王決定戦本戦 A,B問題メモ

第二回全国統一プログラミング王決定戦本戦

むずかった。前半数問は、大雑把なオーダー記法による計算量見積もりだけでなく、それをどこまで削減できるかの感覚が問われているように感じた。

A - Count Triplets

問題

長さ $N$ の数列 $A_1,A_2,...,A_N$ がある
$A_i \lt A_j \gt A_k$ となっている整数の組 $(1 \le i \lt j \lt k \le N)$ の個数を求めよ
$3 \le N \le 5000$
$1 \le A_i \le 10^9$

解法

$j$ を決め打つ。選べる $i$ と $k$ の個数は $j$ よりそれぞれ前と後ろにある $A_j$ より小さい数の個数である。

そしてこの2つは独立に選んでよいので、3つの組としては単純に掛け合わせた分だけ存在する。

各 $j$ につき前と後ろにある自分より小さい数を掛け合わせた数を求め、それらを合計したものが答え。

転倒数を数える要領でBinary Indexed Tree等を使ってもいいし（ただし座標圧縮が必要）、 $N$ が小さいので各 $j$ の両側を毎回探索してもいい。

        
          
          
              
              class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
 
n = int(input())
aaa = list(map(int, input().split()))
bbb = sorted(set(aaa))
ccc = {b: c for c, b in enumerate(bbb)}
m = len(bbb)
bit_f = Bit(m)
bit_b = Bit(m)
smaller_f = []
smaller_b = []
for a in aaa:
    c = ccc[a]
    bit_f.add(c + 1, 1)
    smaller_f.append(bit_f.sum(c))
for a in reversed(aaa):
    c = ccc[a]
    bit_b.add(c + 1, 1)
    smaller_b.append(bit_b.sum(c))
smaller_b.reverse()
ans = 0
for i in range(1, n - 1):
    ans += smaller_f[i] * smaller_b[i]
print(ans)

            

        
      

B - NIKKEI String

問題

文字列 $S$ を6つの空でない文字列に分割し、元の並び順に $S_1～S_6$ とする
順に並んだ6つの文字列が「NIKKEI型である」とは、 $S_2=S_6$ かつ $S_3=S_4$ であることをいう
$S$ をNIKKEI型に分割する方法の個数を求めよ
$6 \le |S| \le 500$

解法

いろいろな解き方があるっぽいが、問題文より条件を1つ1つプログラムに落とし込んでいく。

まず $S_2=S_6$ のため、 $S_6$ の末尾文字が $S_2$ の末尾文字としてそれより4文字以上前に含まれていないといけないので、それを全探索で決め打つ。

これにより、文字を $S_1～S_2$ と $S_3～S_6$ に分割する箇所が固定される。

aabbbbccbb
↓
aabbb bccbb
aabb bbccbb
aab bbbccbb

aabbbbccb b は不可。S2とS6の間に3文字以上なく、S3,S4,S5を取れる場所が無い

次に $S_6$ の長さを決め打ち、 $S_2=S_6$ となるか確認する。この時、 $S_1$ が取れるよう左側に1文字、 $S_3～S_5$ が取れるよう右側に3文字以上残るところまで探索する。

これにより、 $S_1/S_2/S_3～S_5/S_6$ の分割箇所が固定される。

aabb bbccbb
↓
aab b bbccb b
aa bb bbcc bb

a abb bbc cbb までいくとS2とS6が異なり、これ以上伸ばしても同じになることは無いため、終了

最後に $S_3$ の長さを決め打つ。それに続けて $S_4$ を同じ文字数だけとり、同じになるか確認する。 $S_5$ が1文字以上取れるよう注意する。

aa bb bbcc bb
↓
aa bb b b cc bb

これでNIKKEI型の条件を列挙できたので、これらを全て満たすものの個数が答え。計算量は $O(N^4)$ だが、 $S_6$ と $S_3$ で一方の長さが長くなれば一方が短くなるし、文字列比較という単純な操作なので間に合う。

前もって各長さでハッシュ値を計算しておくと $O(N^3)$ になる。

文字列問題は添字の管理で混乱しがち。

        
          
          
              
              s = input()
n = len(s)
 
ans = 0
s6t = s[-1]
for s2t_pos in range(n - 5, 0, -1):
    if s[s2t_pos] != s6t:
        continue
    # print(s2t_pos, n-s2t_pos-3, (n - s2t_pos - 3) // 2 + 1)
    for s6len in range(1, min(n - s2t_pos - 4, s2t_pos) + 1):
        s2h_pos = s2t_pos - s6len + 1
        s6h_pos = n - s6len
        if s[s2h_pos:s2t_pos + 1] != s[s6h_pos:n]:
            break
        for s3len in range(1, (n - s2t_pos - s6len - 2) // 2 + 1):
            s3h_pos = s2t_pos + 1
            s3t_pos = s3h_pos + s3len - 1
            s4h_pos = s3t_pos + 1
            s4t_pos = s4h_pos + s3len - 1
            if s[s3h_pos:s3t_pos + 1] != s[s4h_pos:s4t_pos + 1]:
                continue
            ans += 1
    # print('', ans)
print(ans)

            

        
      

C - Largest N

問題

$H \times W$ の盤面があり、 $K$ マスは白マス、残りは黒マス
$i$ 個目の白マスの位置は $(a_i,b_i)$ で与えられる
黒マスだけを拾って盤面から取れる最大の「N」のサイズを求めよ

解法

1