Competitive Programing Typical 90 Problem day6

プログラミング

Day 6.

I somehow grew up the ability to understand what I am writing. 

I want to keep going.

 

Today's problem was interesting although it can be solved by simple strategy (greedy).

Code is below.

N, K = map(int,input().split())
S = list(str(input()))
#入力を受け取る
symbol = 26
#English letter from a to z, 26 types

letters = list("abcdefghijklmnopqrstuvwxyz")
#I want to convert symbol to number
#list of symbol 

dp = [[-1]*(N+1) for _ in range(symbol)]
#case to hold information about
#the index of next same symbol
# for example: If s = aiueoao
# as for a, [0,5,5,5,5,5,-1]
# because 1st a appear at 0, and next a is at 5.
# so the list(information) is like that one.

#below is storing information to make list(above)
for i in range(N-1,-1,-1):
  num = letters.index(S[i])
  dp[num][i] = i
  for j in range(symbol):
    if j == num:
      continue
    else:
      dp[j][i] = dp[j][i+1]

#we do greedy strategy
#we take most early symbol from left parts.
#but there are limitations.
# 1st, we have to make K length string
#  so, ith letter have to be S[:N-K+i+1]
#  i reflect this limitaion to "if sentence"
# 2nd, we have to select from left
#  so, ith letter is righside fo i-1th letter.
#  to memorize the index of previous letter, i use temp

answer = []
#ingredient of answer letters
temp = 0
for i in range(K):
  for j in range(symbol):
    if 0 <= dp[j][temp] and dp[j][temp] < dp[j][N-K+i+1]:
      answer.append(letters[j])
      temp = dp[j][temp] + 1
      break
    elif 0 <= dp[j][temp] and dp[j][N-K+i+1] == -1:
      answer.append(letters[j])
      temp = dp[j][temp] + 1
      break

#to join the discrete letters in the list
print("".join(answer))

 

  • 辞書順で考える問題に、最大、最小とかが出てきた場合は、貪欲法を使う、という問題。
  • ここでの問題を、文字を順序を損なわないような数字に置き換えることで、Range Minimun Queryという手法を使って解けるようだ。
    • Range Minimum Queryという手法についてよくわからない
      • なので、手法を使うと何が嬉しいのかを理解すること。
      • コードを書かないにしても、そのやり方（順序、気持ち）を理解する。
    • ということを目標とする。
  • こちらのサイトを参考にする。
  • そもそも、Range Minimum Queryとは、区間最小クエリのこと。
    • クエリとは、データベースからデータを抽出したり、操作したりといった処理を行うための命令。こちら。
    • 区間を指定したら、最小値を抽出したり、最小値の場所を抽出したり、する。
    • 最大値にも出来る。（max, min, gcd, lcm　の類いは出来る）
  • クエリを処理するアルゴリズムの計算量は、次の2つによって決まる。
    • 前処理時間
    • クエリ処理時間
    • どっちに比重を置きたいか
      • クエリ処理を沢山するなら、前処理頑張った方が良い
  • RMQアルゴリズムを3つ
    • 平方分割
      • 長さnの配列を長さ√n(平方根)にわけて、
      • 分けた部分配列の最小値を求め、場所と値を記憶
      • クエリが与えられたら、両端を含む部分の最小値と間の全ての部分配列の最小値の比較で求まる。
    • Segment Tree
      • Segment Treeは、1列の配列を部分列に分け、さらに分け、最終的に1つの要素に行き着くまで分けて、分けた（最終産物も、途中産物も、最初の配列も全ての）ものの最小値（など）を管理する。
      • 形が木
        • 分けた時に、分岐する。
        • 根が、最初の配列
      • 部分（Segment）から成る、木（Tree）
      • 前処理は分けて、最小値を求める。
      • クエリ処理は、部分列の最小値の比較。
      • クエリ処理は、Segment Treeの方が、平方分割よりも時間計算量が少ない！（前者はlog n、後者は√n）
    • Sparse Table
      • i番目の要素から、2**kの区間からの長さの部分配列の最小値を求める。
      • 何番目、2の何乗、という2つの要素に対応して、最小値を書き込んだ表を作成する。
      • ここまでが前処理
      • ここから、区間が指定されたら、
        • RMQ(i, k), RMQ(j-2**k+1, k)
        • k = floor(log(j-i))
        • として、O(1)で計算する。
    • どれも、発想として、前処理で、部分配列の最小値を求めて、後で、その分けた部分配列の性質を使って、途中の最小値を求める作業を省略する、ということ。

いずれはコードを書くとしよう。

バイバイ！

  •  
  •