めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

006 - Smallest Subsequence(★5)の解説

何の話かと言うと

atcoder.jp

上記の問題をネタに「ギリギリ間に合う系」、もしくは、「より一般にはもっと多くの種類で考えてもよさそうなのに、なぜか具体的な少数のものに限定されている」系の話をします。

実行時間の見積もり

PyPy3 での実行時間を調べてみます。

for _ in range(10**9):
  pass

# 902 ms
for _ in range(10**10):
  pass

# 8416 ms

これより、制限時間 2s の問題であれば、10^9 回のループまではなんとか間に合うことがわかります。

素朴な解法

例えば、4 文字の部分列を作るのであれば、最初の文字は、

・文字列 S の最後の3文字を除いた中で、最も小さい文字

を選びます。

・2文字目は、

・文字列 S の 1 文字目を選んだ場所より後ろで、最後の2文字を除いた中で、最も小さい文字

を選びます。

つまり、検索の末尾を1文字づつ増やしながら、直前に選んだ場所以降で最小の文字を選ぶ操作を繰り返せばOKです。

これを実装するとループの回数はいくらになるでしょう?

全部で K 文字選ぶので、K 回のループがあります。

次に、それぞれのループの中で、文字列 S に対する最小文字の検索をします。最悪ケースで N-K 文字を検索するので、N-K 回のループになります。(最後の K 文字を除く事と、検索の末尾が増えると同時に検索の先頭も後ろに移動する事を考えてください。)

というわけで、全体として、K\times (N-K) 回のループになります。

計算量の正確な見積もり

1\le K\le N\le 10^5 という条件があるので、上記の計算量を大雑把に 10^5 \times 10^5 と考えると、10^{10} でアウトになります。

なのですが、厳密に、K\times (N-K) を計算すると、1\le K\le N という条件があることから、この値は K=N/2 で最大値 N^2/4 を取ります。つまり、正確なループ回数は最大で 10^{10}/4 = 10^9 \times 2.5 に抑えられます。

10^9 回で 900ms という結果を考えると、ギリギリ感はありますが、試してみる価値はありそうです。

atcoder.jp

結果は、最遅ケースで 1778ms、なんとかセーフでした!

より効率的な解法

さきほどの素朴な解法は、次の様な本当の最悪ケースを手で作ると TLE になります。

  N = 10**5
  K = N//2
  S = ['a'] * N

これでもパスできるための効率化は、「アルファベットは26文字」という特殊性を利用して、

・a が選べるかチェック
・b が選べるかチェック
 \vdots
・z が選べるかチェック

という(ある意味愚直な)確認を繰り返します。具体的には、k 文字目を選ぶ際に「直前に選んだ場所以降でアルファベット X が最初に存在する位置 index」を検索して、index が後ろ過ぎなければ(残り m 文字選ぶのであれば、末尾から m-1 文字目までは選べない)これを採用する、ということを繰り返していきます。

・「直前に選んだ場所以降でアルファベット X が最初に存在する位置 index」

については、事前に DP で準備ができます。

  dp = {} # dp['a'][n] # n 文字目以降で最初に a が来る位置
  for o in range(ord('a'), ord('z')+1): # O(26*N)
    tmp = [-1] * (N+2)
    for n in range(N, 0, -1):
      if S[n] == chr(o):
        tmp[n] = n
      else:
        tmp[n] = tmp[n+1]
    dp[chr(o)] = tmp

1 文字に付き、N 文字の検索で用意できるので、全体として O(26\times N) = O(N) で用意できます。

すると、さきほどのチェックは、O(1) で済むので、全部で K 文字選ぶ処理は、O(K) で終わります。

atcoder.jp

このように、与えられた条件の中で、「より一般にはもっと多くの種類で考えてもよさそうなのに、なぜか具体的な少数のものに限定されている」部分に注目して、

・少数に限定されたもののループを利用する(このループは O(1) と見なせる)

という手法を考えるとよいことがあります。次の問題もそのような例です。

enakai00.hatenablog.com

おまけ

巨大なリストの作成は、初期化だけでも時間がかかるので注意しましょう。

N = 10**8
a = [None] * N

# 1015 ms

リストを作るだけで、1sec 以上かかってます。

003 - Longest Circular Road(★4)の解説

何の話かと言うと

atcoder.jp

「トポロジカルオーダーで処理する」系の問題例としてこちらを紹介します。

この問題では、無向グラフを取り扱います。有向グラフの例については、下記の記事が参考になります。

enakai00.hatenablog.com

考え方

ノード数 N に対してリンク数が N-1 であることから、木構造のグラフだと気づきます。(気づいてください。)そこで、始ノードを見つけて、一歩づつ歩きながら歩数をカウントしていきます。ノード n に対して dp[n] をそのノードに至るまでの歩数の最大値として記録していきます。a -> b に進んだら、

dp[b] = max(dp[b], dp[a]+1)

というアップデートができます。この際、(アップデート前の値を用いて)、dp[b] + dp[a] + 1 は、ノード b で出会う2つの経路の距離を表す事に注意します。

たとえば、a -- b -- c という経路で、c -> b (dp[b] = 1 になる)というアップデートの後、a -> b というアップデートをすると、既存の dp[b] は c からの距離になるので、dp[b] + dp[a] + 1 は、(b で出会う)a と c の距離になります。

この問題では、このような経路の距離の最大値を求めればよいので、一歩進む度に dp[b] + dp[a] + 1 を計算して、その時点の最大値を保持していけばOKです。

最後に残った最大値に(閉路にするために追加する道路分の)1 を加えたものが答えになります。

atcoder.jp

おまけ

この記事では「トポロジカルオーダーで処理する」系の問題として解きましたが、これは、一般には、「木の直径を求める」という問題で、公式解説では、一般的に知られたエレガント(?)な解法も紹介されています。

github.com

002 - Encyclopedia of Parentheses(★3)の解説

何の話かと言うと

atcoder.jp

上記の問題をネタにキューを使った再起処理の基本を説明します。

キューを使った再起処理

公式解説では、2^N 通りのすべての組み合わせから条件に合うものを抽出する方法が説明されていますが、再帰処理を用いて条件に合うものだけを生成することもそれほど難しくありません。

まず、簡単のために、条件を考えずに 2^N 通りのすべての組み合わせを生成してみます。

n 文字目まで用意したら、その後ろには "(" をつけるか ")" を付けるかの2択で n+1 文字目を生成すればよいので、次の様な実装ができます。

from collections import defaultdict, deque

def braket(N):
  q = deque()
  q.append('(')
  q.append(')')
  while q:
    s = q.popleft()
    if len(s) == N:
      print(s)
      continue
    q.append(s + '(')
    q.append(s + ')')

braket(4)

今の場合、"(" を先にキューに追加しているので、"(" < ")" とした辞書順に生成されます。

((((
((()
(()(
(())
()((
()()
())(
()))
)(((
)(()
)()(
)())
))((
))()
)))(
))))

ちなみに、popleft() で取り出すところを pop() で取り出すと生成順序が逆向きになります。

条件に合うものだけを生成する

条件に合うものだけを生成するには、"(" と ")" を何個使ったかをカウントする必要があります。キューから文字列を取り出して、毎回、カウントするのは非効率なので、カウント数も含めてキューに入れてしまいます。すると、こんな感じで実装できます。

from collections import defaultdict, deque

def braket(N):
  bra = N // 2
  ket = N // 2
  q = deque()
  q.append((bra-1, ket, '(')) # bra, ket, string
  while q:
    bra, ket, s = q.popleft()
    if bra == 0 and ket == 0:
      print(s)
      continue
    if bra > 0:
      q.append((bra-1, ket, s + '('))
    if bra < ket:
      q.append((bra, ket-1, s + ')'))

braket(6)

結果はこちらで、意図通りに出力されていますね。よかった!

((()))
(()())
(())()
()(())
()()()

atcoder.jp