🐢

[ABC349 C] Airport Code

2024/04/14に公開

Ruby

動的計画法を使わなくてもよかった問題。

問題を要約する

NRT は narita の略語か？
略語が2文字なら最後に X を埋めて3文字に調整されている

したがって JPN も JPX も japan の略語になる。

事前準備

大小文字を揃えておく
略語から X を除外しておく

コンテスト中は「元の単語の最後に X を追加しておく」としたが、計算量を考えると減らす方に持っていった方がよさそう。

解法1. 最長共通部分列

138 ms

S = gets.strip                 # => "narita"
T = gets.strip                 # => "NRT"
S.upcase!                      # => "NARITA"
T.delete_suffix!("X")          # => nil
H = S.size                     # => 6
W = T.size                     # => 3
dp = Array.new(H.next) { Array.new(W.next, 0) }
(1..H).each do |y|
  (1..W).each do |x|
    u  = dp[y - 1][x - 0]
    l  = dp[y - 0][x - 1]
    lu = dp[y - 1][x - 1]
    if S[y - 1] == T[x - 1]
      dp[y][x] = [u, l, lu + 1].max
    else
      dp[y][x] = [u, l].max
    end
  end
end
same = dp.last.last == T.size  # => true
puts same ? "Yes" : "No"

	N	R	T
-	0	0	0
N	1	1	1
A	1	1	1
R	1	2	2
I	1	2	2
T	1	2	3
A	1	2	3

最近学んだ最長共通部分列問題につられてコンテスト中はこれしか思いつかなかった。

実行速度については S.upcase! を省き、casecmp? で判定するようにもしてみたが別段速くはならなかった。

解法2. 地道に調べる

58 ms

S = gets.strip         # => "narita"
T = gets.strip         # => "NRT"
S.upcase!              # => "NARITA"
T.delete_suffix!("X")  # => nil
pos = 0
same = T.each_char.all? do |ch|
  loop do
    unless S[pos]
      break
    end
    if S[pos] == ch
      pos += 1
      break true
    end
    pos += 1
  end
end
same                   # => true
puts same ? "Yes" : "No"

S のなかに T を構成する文字が順番に現れるか？を言葉通り、地道に調べていく。

解法3. 正規表現

105 ms

S = gets.strip           # => "narita"
T = gets.strip           # => "NRT"
S.upcase!                # => "NARITA"
T.delete_suffix!("X")    # => nil
s = T.chars * ".*"       # => "N.*R.*T"
same = S.match?(/#{s}/)  # => true
puts same ? "Yes" : "No"

つまり、

"NARITA".match?(/N.*R.*T/)  # => true

だけでよかった。