# Gori#027(AGC006&EDPC)

# A - Prefix and Suffix

# 概要

文字列SSTTが与えられる.
ここで, 以下の条件を満たす文字列のうち, 最も短いものを求めよ.

  • 長さはNN以上
  • 先頭NN文字がSSに一致
  • 末尾NN文字がTTに一致

# 解法

制約から1N1001 \leq N \leq 100なので, 文字列SSTTに関して, 1,...,1001, ... , 100の範囲で一致するかを確認すれば良い.

# 提出

AGC006-A

# B - Median Pyramid Easy

# 概要

$N段のピラミッドがあり, 各ブロックには番号が振られている.
ブロックに書かれている数字は, そのブロックの左下, 真下, 右下のブロックに書かれている数字の中央値となっている.
この時に, NN段目のブロックに書き込まれた順列としてあり得るものがあるか判定し, 存在するなら1つ求めよ.

# 解法

一番上のブロックになり得るためには, その下の段で2つ連続で並んでいればよい.したがって, 2つ連続で並ぶようなブロックの積み方を考える.

すると, x1,x,x+1,x2x-1, x, x+1, x-2というようにすれば確実にxxのブロックが2つできるので, これを採用する.
他のブロックはなんでもよい.

# 提出

AGC006-B

# F - LCS

# 概要

文字列SSTTが与えられる.SSTTの部分列である文字列のうち, 最長のものを1つ求めよ.

# 解法

最長部分列はDPの典型なので, dpテーブルと遷移を以下の様に定める.

// dp[i][j] := sをi文字目まで見て, tをj文字目まで見た時の最長部分列

// 遷移
// dp[i+1][j+1] = dp[i][j] + 1 if s[i] == t[j];
// dp[i+1][j+1] = dp[i+1][j]   if dp[i+1][j] < dp[i][j+1]
// dp[i+1][j+1] = dp[i][j+1]   otherwise

しかし, これだけでは文字列長しか求められない.
そのため, 文字列を復元する.
復元は後ろから前に向かって行う(これは典型).
そもそも一致した部分は, 上で述べた遷移のうちs[i]==t[j]s[i] == t[j]の遷移なので, その遷移を復元すれば良い.

# 提出

EDPC-F

以上.
お疲れ様でした.

# 参考資料

Last Updated: 2019-2-15 04:38:05