# Gori#027(AGC006&EDPC)

# A - Prefix and Suffix

# 概要

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

長さは $N$ 以上
先頭 $N$ 文字が $S$ に一致
末尾 $N$ 文字が $T$ に一致

# 解法

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

# 提出

AGC006-A (opens new window)

# B - Median Pyramid Easy

# 概要

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

# 解法

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

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

# 提出

AGC006-B (opens new window)

# F - LCS

# 概要

文字列 $S$ と $T$ が与えられる. $S$ と $T$ の部分列である文字列のうち, 最長のものを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]$ の遷移なので, その遷移を復元すれば良い.

# 提出

EDPC-F (opens new window)

以上.
お疲れ様でした.

# 参考資料

Editorial(AGC006) (opens new window)