LoginSignup
1
1
@mtmtss

文字列で与えられた数列を数字に分解する問題をpythonで解く

Last updated at Posted at 2024-05-24

問題

  • 1, 2, ..., 99が並び替えられた数列$s$が以下のような形式で与えられたとき，コンマ区切りで数列を出力せよ．
  • 例
    • 入力 
      194844479992885193431281672755538710981664457433843176692585632179368224916037252154184211658086419457126285078707285638157343020599675354922614657775295148733139079401662636483232968398997
    • 期待される出力 
      19,48,44,47,99,92,88,51,93,43,12,81,67,27,55,53,87,10,98,1,66,4,45,74,33,84,31,76,69,2,58,56,32,17,9,36,82,24,91,60,37,25,21,54,18,42,11,65,80,86,41,94,5,71,26,28,50,78,70,72,85,6,38,15,7,34,30,20,59,96,75,35,49,22,61,46,57,77,52,95,14,8,73,3,13,90,79,40,16,62,63,64,83,23,29,68,39,89,97

ここから先は筆者の考え方を示すので，解き方を考える方は一回スクロールしないほうがいいかもしれません

考え方（失敗バージョン）

  • 数字を1つ進める場合と2つ進める場合がある
    • 1つ進めるのは1桁の数字（1-9）のときなので，これらの9個の数字の場所を全探索できれば解けそう...！
    • 各数字の存在箇所は20で，$20^9$ 回の計算となり回りませんでした...
  • 計算量を減らしていく必要がありそう

考え方（うまくいったバージョン）

  • 例えば10, 20などの一の位が0の2桁の数字は，数列の中で1か所しか存在しない
  • このように数列のなかで1回しか出てこないような2桁の数字を検出して，消していけばよさそう
  • 具体的な手順を以下に示します

  1. 1, 2, ..., 99が検出されたかをメモする配列checkedを用意

    checked = [False]*99 # Trueなら検出済み

  2. 文字列sから数字のリストnumに変換する

    s = "194844479992885193431281672755538710981664457433843176692585632179368224916037252154184211658086419457126285078707285638157343020599675354922614657775295148733139079401662636483232968398997"
num = [int(s[i]) for i in range(len(s))]

  3. 一の位が0の2桁の数を消し，部分列に分割

    for i in range(10,100,10):
  checked[i-1] = True
num.append(1)
num.append(0)
sequence = [] # 分割後の数列を格納
lower = 0
for i in range(len(num)):
  if num[i] == 0:
    sequence.append(num[lower:i-1])
    lower = i+1
num.pop(-1)
num.pop(-1)
print(sequence)
    • 出力
    [[1, 9, 4, 8, 4, 4, 4, 7, 9, 9, 9, 2, 8, 8, 5, 1, 9, 3, 4, 3, 1, 2, 8, 1, 6, 7, 2, 7, 5, 5, 5, 3, 8, 7], [9, 8, 1, 6, 6, 4, 4, 5, 7, 4, 3, 3, 8, 4, 3, 1, 7, 6, 6, 9, 2, 5, 8, 5, 6, 3, 2, 1, 7, 9, 3, 6, 8, 2, 2, 4, 9, 1], [3, 7, 2, 5, 2, 1, 5, 4, 1, 8, 4, 2, 1, 1, 6, 5], [8, 6, 4, 1, 9, 4, 5, 7, 1, 2, 6, 2, 8], [7, 8], [7, 2, 8, 5, 6, 3, 8, 1, 5, 7, 3, 4], [], [5, 9, 9, 6, 7, 5, 3, 5, 4, 9, 2, 2, 6, 1, 4, 6, 5, 7, 7, 7, 5, 2, 9, 5, 1, 4, 8, 7, 3, 3, 1, 3], [7, 9], [1, 6, 6, 2, 6, 3, 6, 4, 8, 3, 2, 3, 2, 9, 6, 8, 3, 9, 8, 9, 9, 7]]

    検出した数字を切れ目として複数の部分列に分割する
    出力の ] と [ の間にはもともと2桁の数字が存在していた

  4. それ以外の2桁の数字をふるい落とす

    sequence_sieved = two_digit_sieve(sequence)
print(sequence_sieved)

    2桁の数字をふるい落とす関数two_digit_sieveの説明は次章で行います

    • 出力

      sequence_sieved: [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [1], [4], [], [], [], [], [], [], [2], [], [], [], [9], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [5], [], [], [], [], [], [], [], [6], [], [7], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [8], [3], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]

    2桁の数字はすべてふるい落とされる


  5. ふるい落とされた数列で，] と [ の間にはもともと2桁の数があったはず

    • ] [ を読むたびにindexを1つ増やしながら，1桁の数がもともとどこにあったか計算

      one_digit_idx = []
count = 0
flag = 0
for i in range(len(sequence_sieved)):
  for j in range(len(sequence_sieved[i])):
    one_digit_idx.append(count) # indexを保存
    count += 1 # 1桁の数字の分進める
  count += 2 # ][の分進める
print("one_digit_idx:",one_digit_idx)

    • 出力

      one_digit_idx: [38, 41, 56, 65, 100, 117, 122, 155, 158]

  6. 得られたindexをもとにしてもとの数列の復元を行う

    ans = []
i = 0 # 何桁進めるか制御
while(True):
  if i in one_digit_idx:
    ans.append(num[i])
    i += 1
  else:
    if i < len(num)-1:
      ans.append(num[i]*10+num[i+1])
      i += 2
  if i >= len(num)-1:
    break
print("\n===ans===\n", ans)

    • 出力

      ===ans===
 [19, 48, 44, 47, 99, 92, 88, 51, 93, 43, 12, 81, 67, 27, 55, 53, 87, 10, 98, 1, 66, 4, 45, 74, 33, 84, 31, 76, 69, 2, 58, 56, 32, 17, 9, 36, 82, 24, 91, 60, 37, 25, 21, 54, 18, 42, 11, 65, 80, 86, 41, 94, 5, 71, 26, 28, 50, 78, 70, 72, 85, 6, 38, 15, 7, 34, 30, 20, 59, 96, 75, 35, 49, 22, 61, 46, 57, 77, 52, 95, 14, 8, 73, 3, 13, 90, 79, 40, 16, 62, 63, 64, 83, 23, 29, 68, 39, 89, 97]

  7. 数分解があっているかをセルフで判定

    ideal_answer = [i for i in range(1,100)]
judge = True
# 1-99が1つずつ含まれているか判定
for i in ans:
  if i in ideal_answer:
    ideal_answer.remove(i)
  else:
    print(i,"is duplicated")
if len(ideal_answer) != 0 or len(ans) != 99:
  judge = False
# ansの結合が元の文字列と同じであるか判定
if ''.join(map(str, ans)) != s:
  judge = False

if judge:
  print("\nanswer is True!!")
else:
  print("\nanswer is False")

    • 出力

      answer is True!!

2桁の数をふるい落とすアルゴリズム

2桁の整数をふるい落としきれない（複数パターンの解が存在する）際のアルゴリズムに誤りがありました。時間があるときに編集します（2024/06/01）。

  • two_digit_sieve の内容について説明

    import copy

def two_digit_sieve(sequence):
  two_digit = []
  for i in range(11,100):
    if i % 10 != 0:
      two_digit.append(i)
  false_num_before = checked.count(False)
  while(checked.count(False) >= 10):
    two_digit_count = [0 for i in range(10,100)]
    two_digit_dict = dict(zip(two_digit, two_digit_count))

    # 2桁の数字の登場回数を数える
    for i in range(len(sequence)):
      for j in range(len(sequence[i])-1):
        two_digit_dict[sequence[i][j]*10+sequence[i][j+1]] += 1

    # 削除する2けたの数字を記憶するリスト
    remove_list = []

    # 登場回数が1回の場合，削除リストに入れる
    for td in two_digit:
      if two_digit_dict[td] == 1:
        checked[td-1] = True
        remove_list.append(td)

    # 削除リストに従って，部分列をさらに分断
    sequence_trimmed = []
    for i in range(len(sequence)):
      lower = 0
      j = 0
      while(j < len(sequence[i])-1):
        if sequence[i][j]*10 + sequence[i][j+1] in remove_list:
          sequence_trimmed.append(sequence[i][lower:j])
          lower = j+2
          remove_list.remove(sequence[i][j]*10 + sequence[i][j+1])
          j += 1
        j += 1
      sequence_trimmed.append(sequence[i][lower:])

    sequence = copy.deepcopy(sequence_trimmed)
    print("the number of undetected:",checked.count(False))
    print("sequence:",sequence)
    print("the length of sequence:",len(sequence))
    print()

    # 無限ループ対策
    if checked.count(False) == false_num_before:
      break
    false_num_before = checked.count(False)

  # ふるい落とした結果，決めきれない2桁の数字が残った場合の処理
  if checked.count(False) > 9:
    print("sequence_undecided:",sequence)
    sequence_decided = []
    remove_list = []
    for i in range(len(sequence)):
      if len(sequence[i]) > 1:
        for j in range(len(sequence[i])-1):
          # 決めきれていない2桁の数字を強制的に決める
          if checked[sequence[i][j]*10 + sequence[i][j+1]-1] == False:
            remove_list.append(sequence[i][j]*10 + sequence[i][j+1])
            checked[sequence[i][j]*10 + sequence[i][j+1]-1] = True

    for i in range(len(sequence)):
          lower = 0
          j = 0
          while(j < len(sequence[i])-1):
            if sequence[i][j]*10 + sequence[i][j+1] in remove_list:
              sequence_decided.append(sequence[i][lower:j])
              lower = j+2
              remove_list.remove(sequence[i][j]*10 + sequence[i][j+1])
              j += 2
            else:
              j += 1
          sequence_decided.append(sequence[i][lower:])
    sequence = copy.deepcopy(sequence_decided)
  return sequence

関数の計算量

  • whileループは1回回るごとに最低1つ，2桁の整数がふるい落とされるので最悪90回程度
  • whileループ内処理は最悪の場合numのサイズの2乗で40000程度
  • 全体で90×40000 < $10^7$なので計算できそう
  • アルゴリズム初心者なので，よりよい解き方があればご教示ください！
  • これから勉強して色々書いてみます
1
1
16

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1