−目次

AtCoder Regular Contest 173 A,B,C,D問題メモ
- A - Neq Number
  - 問題
  - 解法
- B - Make Many Triangles
  - 問題
  - 解法
- C - Not Median
  - 問題
  - 解法
- D - Bracket Walk
  - 問題
  - 解法

AtCoder Regular Contest 173 A,B,C,D問題メモ

AtCoder Regular Contest 173

ケアレスな実装ミスでタイムロスしちまうのはなおらないねえ。

A - Neq Number

問題

ある正整数 $X$ を（先頭に0のつかない）十進法表記した際に、同じ数字が隣り合わない場合、 $X$ を“Neq Number” という
小さい方から $K$ 番目の Neq Number を求めよ
1つの入力につき $T$ ケース与えられる
$1 \le T \le 100$
$1 \le K \le 10^{12}$

解法

「 $d$ 桁の Neq Number は何個あるか？」は、簡単に求められる。

一番大きい桁は $1～9$ の9通り
続く $d-1$ 個の桁は $0～9$ のうち前の桁と違う数字の9通り
→ 全部で $9^d$ 個ある

なので、まず「 $d$ 桁以下のNeq Numberの個数」を事前計算しておくと、 $K$ 番目のNeqNumberが何桁かは判明する。

同様に、大きい方から何個かの先頭桁を決めたときに「これに当てはまる Neq Number は何個あるか？」も求められる。

各桁、前の桁の数と違う数の選択肢があるので、 $9^{未定桁数}$ ある。

1 2 3 4 ? ? ? ?    それぞれの"?"に適当な数を置いてできるNeqNumberは、9^4=6561個ある

$i$ 桁目に置く数を順に試す。答えが 123????? を満たす中で 20000 番目である場合、

      i
1 2 3 0 ? ? ? ?        1～ 6561
1 2 3 1 ? ? ? ?     6562～13122
1 2 3 2 ? ? ? ?    13123～19683
1 2 3 3 ? ? ? ?    ←×違反
1 2 3 4 ? ? ? ?    19684～26244

→ 答えは、1234???? を満たす中で 20000 - 19683 = 317番目

なので、大きい方の桁から $0,1,2,...,9$ のうち前の桁と異なるものを置いていき、個数を数えていくと、順に決めていける。

1つにつき、進数を $B=10$ 、 $K_{max}$ 番目のNeqNumberの桁数を $D$ として（ $D=14～15$ くらい）、 $O(BD)$ で求められる。

Python3

B - Make Many Triangles

問題

2次元空間上に $N$ 個の点がある
これらの点を頂点に持つ（非退化な）三角形をできるだけ多く作りたい
1度使った点は他の三角形では使えないとき、最大何個作れるか、求めよ
$3 \le N \le 300$

解法

基本的には、 $\left \lfloor \dfrac{N}{3} \right \rfloor$ 個作れるはず。

しかし同一直線上にある3点は、三角形が作れないので選ぶことができない。（作れないのはこの条件のみ）

点同士を結ぶ直線のうち、最も多くの点が並んでいる直線を $L$ 、そこに乗っている点の数を $C$ とする。

$L$ 上の点をなるべく多く消費することを考えると、 $L$ 上から2点と、それ以外から1点を選ぶことで三角形が作れる。
よって、そうやって作っていっても $L$ 上に点が残る場合、作れる個数は $N-C$ 個となる。

答えは、 $\min(\left \lfloor \dfrac{N}{3} \right \rfloor,N-C)$ となる。

同一直線上に並ぶ点のカウント

「同一直線上に並ぶ点の個数」を求めるには、2点組ごとに「2点を結ぶ直線の方程式 $ax+by+c=0$ の係数 $a,b,c$ 」を計算し、それごとにカウントする。
$c$ 個の点が並ぶ直線は、 $\dfrac{c(c-1)}{2}$ 回カウントされることになるので、最も多くカウントされた直線の値を逆算すると個数が分かる。

$(x_1,y_1)$ と $(x_2,y_2)$ を通る直線の方程式を、「小数による誤差を排除して」「 $x$ 軸や $y$ 軸に平行な場合にも対応して」求めるには、以下の式を使うのがよい。

$d_x=x_2-x_1,d_y=y_2-y_1$ として、 $d_yx - d_xy + (d_xy_1 - d_yx_1)=0$
二点を通る直線の方程式の３タイプ | 高校数学の美しい物語

ただし、係数に定数倍をかけたものは同一になるので、それらを統一する必要がある。

$d_x$ と $d_y$ は、GCDで割って互いに素にしておく
$d_x$ が負の場合、正にする
$d_x$ が0かつ $d_y$ が負の場合、 $d_y$ を正にする

こうすると、定数倍の違いを吸収して、3つの整数値で直線を特定できる。

Python3

C - Not Median

問題

$1～N$ の順列 $A=(A_1,...,A_N)$
各 $i=1,...,N$ につき、以下を満たす区間 $[l,r]$ があるか判定し、存在する場合は長さ $r-l+1$ の最小値を求めよ
- 区間長は奇数
- $i$ を含む（ $l \le i \le r$ ）
- $(A_l,A_{l+1},...,A_r)$ の中央値は、 $A_i$ ではない
$1 \le N \le 3 \times 10^5$

解法

最小の区間は3である。特に、 $i$ の左右が、 $A_i$ より小さい同士/大きい同士で一致していれば、確実に3となる。

      i        両隣が Ai より大きい同士なら、
A  8  5  6     [i-1, i+1] の区間にすれば確実に最小の3になる

それより長くなる場合というのは？

$A_i$ 自身より大きい数と小さい数が左右に交互に現れ、 1つずらしても「小さい数が出て小さい数が入る」「大きい数が出て大きい数が入る」ようにしかならない場合に、長くなる。

             i               j
A  7  14  6  8  10  2  9  5  4 ...    ^:8より大きい
   v   ^  v      ^  v  ^  v  v        v:8より小さい
   ~~~~~~~~~~~~~~~
      ~~~~~~~~~~~~~~~
          ~~~~~~~~~~~~~~              i を含む長さ5の区間は、
             ~~~~~~~~~~~~~~           全て8が中央値になる

上例 5 4 のように大きい数同士、小さい数同士が隣り合った箇所（ $j$ ）を含めた区間にすると、中央値を変えられる。
（※端の場合を除く。後述）

このように、 $A_i$ より大きい同士/小さい同士が隣り合う箇所を単に「連続箇所」とする。

各 $i$ につき、左右で最も近い連続箇所のindexを高速に求めたい。
区間に連続箇所を含められればよいので、もう一方の端は、 $i$ をギリギリ含めるか、もしくは1つだけ逆側を含めるかになる。
左右で近い方の連続箇所との距離を、奇数に調整したものが、答えとなる。

             i               v連続箇所
A  7  14  6  8  10  2  9  5  4 ...
   v   ^  v      ^  v  ^  v  v
          ~~~~~~~~~~~~~~~~~~~~
連続箇所から i を挟んで逆側（6）を、1つだけ含めて調整した場合

端の場合

端の場合、「逆側を1つだけ含める」ができない。
左端なら、区間を2個ずつ右に伸ばすしかない。

   i
A  8  10  2  9  5  4  12 ...
       ^  v  ^  v  v   ^

その場合、小さい同士が連続（5 4）していても、次が大きい（12）なら、やはり中央値は8である。

左端・右端は、愚直に2個ずつ伸ばして確かめていくのがよい。

※端で無い場合は、「 $A_i$ の左右の大小は異なる」前提から、この心配は無い。
例えば $i$ を左端、右側の連続箇所を右端とした区間が

長さが奇数なら、それでよし
長さが偶数なら、もう1要素、左か右に追加しなければならないが、、、
- 「小 i 大小大小小」のように、偶奇を考えると逆側の1個と、連続する値の大小は必ず一致する

最も近い連続箇所の求め方

複数の求め方がある。

セグメント木
SortedSet
実は愚直で間に合う

セグメント木

$A_i$ の小さい方から順に答えを求めていく。

現在、答えを求めている $A_i$ を $k$ とする。

$B=(B_1,...,B_{N-1})$ を、「 $A_i$ と $A_{i+1}$ が、ともに $k$ より小さい、またはともに $k$ より大きい場合に1、それ以外は0」を取る値とする。

  
A  7 14  6  8 10  2  9  5  4 12 11  3 13 1
B   1  1  1  1  1  1  1  1  1  1  1  1  1    k=1 のとき
B   0  0  0  1  0  0  0  1  0  1  0  0  0    k=8 のとき

$B$ を区間Maxセグメント木に載せて、その上で二分探索することによって、「 $[l,r)$ の範囲のうち最も左にある1」「最も右にある1」の位置を取得できる。

これで、左右に最も近い連続箇所の位置が求められる。

$k=A_4=8$ の答えを求め終わったら、次の $k$ に向けて、 $A_3,A_4,A_5$ の大小を調べて $B_3,B_4$ を更新する。

愚直

$i$ から左/右に1つずつ、連続箇所が出てくるまで調べる実装でも、間に合う。

ある $i$ で時間がかかる場合というのは、左右に $A_i$ より大/小が交互に出現する場合である。

このとき、通過した各要素は、その要素にとっては「両端が大きい同士/小さい同士」に該当するので、答えは3とすぐに求まる。

             i                       x をつけた要素は、
A  7  14  6  8  10  2  9  5  4 ...   両端が大きい同士/小さい同士なので答えは3
   v   ^  v      ^  v  ^  v  v       
   ←←←←←|→→→→→→→→       ←iからの探索範囲
       x  x      x  x  x

また、愚直に調べる対象となる $i$ は、小→中(i)→大と並んでいるので、他の要素から見れば、 $i$ （の周辺 $\pm1$ ）で大/小が連続し、そこで探索が終了することになる。

よって、 $A$ の各要素が愚直に調べられる回数は、左方向・右方向に1回ずつとなり、 $O(N)$ で間に合う。

         小 中  大    大 中 小
A  7  14  6  8  10  2  9  5  4 ...
   v   ^  v      ^  v  ^  v  v
             |→→→→→→→→
              ←←←←←←|

Python3

セグメント木実装。

        
          
          
              
              from operator import add, eq
 
 
class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木
 
    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成
 
    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """
 
    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory
 
    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins
 
    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)
 
    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)
 
    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])
 
    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()
 
        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1
 
        return func(result_l, result_r)
 
    def get_all(self):
        return self.tree[1]
 
    def get_point(self, i):
        return self.tree[i + self.offset]
 
    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。
 
        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1
 
        if r_found == -1:
            return -1
 
        return self._leftmost_sub(r_found, x, ev)
 
    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset
 
    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。
 
        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1
 
        if l_found == -1:
            return -1
 
        return self._rightmost_sub(l_found, x, ev)
 
    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset
 
    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1
 
 
n = int(input())
aaa = list(map(int, input().split()))
aaa = [a - 1 for a in aaa]
 
pos = [0] * n
for i, a in enumerate(aaa, start=1):
    pos[a] = i
 
 
def sgt_update(i):
    b = aaa[i - 1]
    if i > 1:
        a = aaa[i - 2]
        if a < b:
            sgt.update(i - 1, 1)
        else:
            sgt.update(i - 1, 0)
    if i < n:
        c = aaa[i]
        if b > c:
            sgt.update(i, 1)
        else:
            sgt.update(i, 0)
 
 
def pattern_left():
    j = 1
    over = 0
    under = 0
    while i <= n - 2:
        if b < aaa[j]:
            over += 1
        else:
            under += 1
        j += 1
        if b < aaa[j]:
            over += 1
        else:
            under += 1
        j += 1
        if over != under:
            return j
    else:
        return -1
 
 
def pattern_right():
    j = n - 2
    over = 0
    under = 0
    while j >= 1:
        if b < aaa[j]:
            over += 1
        else:
            under += 1
        j -= 1
        if b < aaa[j]:
            over += 1
        else:
            under += 1
        j -= 1
        if over != under:
            return n - j - 1
    else:
        return -1
 
 
sgt = SegmentTreeInjectable.from_array([1] * (n + 2), lambda: 1, max)
ans = [0] * n
INF = 1 << 60
for b in range(n):
    i = pos[b]
 
    if i == 1:
        ans[i - 1] = pattern_left()
        sgt_update(i)
        continue
 
    if i == n:
        ans[i - 1] = pattern_right()
        sgt_update(i)
        continue
 
    a = aaa[i - 2]
    c = aaa[i]
    if (a < b) == (b > c):
        ans[i - 1] = 3
        sgt_update(i)
        continue
 
    l = sgt.rightmost(0, i - 1, 1, eq)
    r = sgt.leftmost(i + 1, n + 2, 1, eq)
 
    tmp = INF
    if l > 0:
        tmp = min(tmp, (i - l + 1) // 2 * 2 + 1)
    if r < n:
        tmp = min(tmp, (r - i + 2) // 2 * 2 + 1)
    if tmp == INF:
        tmp = -1
    ans[i - 1] = tmp
 
    sgt_update(i)
 
print(*ans)

            

        
      

D - Bracket Walk

問題

$N$ 頂点 $M$ 辺の有向グラフ
- 自己辺・多重辺は存在しない
- 全体が強連結（どの頂点からどの頂点へも経路が存在する）
各辺には、'(' または ')' のいずれか一方が書かれている
以下のようなウォーク（同じ辺・頂点を複数回通ってもよい移動経路）が存在するか判定せよ
- 始点と終点が同じ頂点
- 全ての辺を1度以上通る
- 通った辺に書かれた括弧を順に並べると、正しい括弧列になっている
$2 \le N \le 4000$
$N \le M \le 8000$

解法

以下、単に「ウォーク」というと、始点と終点が同じ「閉じたウォーク」を指すとする。

条件の整理

まず、正しい括弧列というと以下の条件をともに満たすものだが、

'(' と ')' が同数
途中で ')' の個数が '(' の個数を上回ってはいけない

このうち、後者は無視できる。
もし途中で ')' の個数が上回ってしまっても、開始位置を適切にずらすことで、必ず正しい括弧列にできる。

よって、「'(' と ')' が同数」で全辺を通るウォークを見つけさえすればよい。
同数とは、「'(' を $+1$ 、')' を $-1$ で置き換えて、ウォークのコストが0」と言い換えられる。

条件を満たすウォークがあったとして、存在を見つける上では頂点 $1$ を始点終点に固定して考えて問題ない。
$1$ を始点と終点とするウォークを $Walk_1$ とする。

$Walk_1$ を複数個並べたものもまた、 $Walk_1$ である。
答えとなる「全辺を通りコストが0の $Walk_1$ 」を、 $Walk_1$ の結合で作ることを考える。

コストの正負による分類

ウォークのコストは、当然ながら正、0、負のいずれかである。

グラフ中にコスト正の閉路があることと、コスト正の $Walk_1$ があることは、一致する。

⇒の証明
- 閉路が $1$ を含んでいればそれ自体がウォークである
- $1$ を含まなくても、強連結なので、 $1$ から閉路まで行き、好きなだけ回って帰る、ということができる
⇐の証明
- 閉じたウォークは、複数の閉路に分解できる（同じ頂点に2回以上訪れていたら、そこで分割することを繰り返せばよい）
- コストが0や負の閉路だけでは、明らかにコスト正のウォークは構成できない

コスト正・負のウォークがそれぞれあるとどうなるか考える。

正と負が両方存在する場合

条件を満たすウォークを実現できる。

未使用辺を1つ適当に取る
それを含む $Walk_1$ を適当に1つ決める
$Walk_1$ のコストが正なら、別のコスト負の $Walk_1$ 、負なら正の $Walk_1$ を適当に1つ決める
2つを何回かぐるぐるすることで、総コストを0にあわせられる
2つの $Walk_1$ で使用した辺を使用済み辺として、最初に戻る
全ての辺を使用したら完了

全ての閉路のコストが0の場合

意図的に作らない限り珍しいが、これもあり得る。
この場合も、当然コスト0を実現できる。

正か負のどちらか一方のみが存在する場合

なんとなく「No」っぽいが、証明しようとすると悩ましい。公式Editorialでは背理法による証明がある。

正の閉路があり負の閉路が無いグラフでも、条件を満たすウォークがあったと仮定する。

あるウォーク $W$ と、そこに含まれる辺のみを使用した閉路 $C$ があるとする。
この時、以下のようにすることを、“ $W$ から $C$ を取り除く”と表現するとする。

$W$ で使われた辺と頂点を取り出し、複数回通った辺はその分、多重化したグラフを $G_W$ とする
$G_W$ は、オイラーグラフ（全ての頂点の入次数と出次数が等しい）となる
ここから $C$ に使われた辺を取り除いても、 $G_C$ もオイラーグラフのため、入出次数の一致は保たれる
連結性は保たれないかもしれないが、複数のウォークの集合として表現できる
- 今回は、コストが正か負かのみに注目するため、通過順は変化しても気にしない

条件を満たすウォークを $W$ とし、そこから正の閉路 $C$ を取り除くと、残ったグラフの総コストは負になる。
つまり、どれかのウォークはコストが負にならざるを得ず、負の閉路が存在することになる。

矛盾するので、コスト正の閉路しか無ければ、正解ウォークは作れないことが分かる。

負閉路検出はBellman-Fordで、 $O(NM)$ でおこなえる。
正閉路も、コストを逆転させれば同様に求められる。

Python3