https://www.acmicpc.net/problem/3203
아이디어
사실 먼저 고백하자면, 이 문제의 핵심 아이디어는 "알고리즘 분류" 보기 버튼에 의해 미리 스포일러당한 상태로 풀었음을 밝힌다.
1. 관찰
슬쩍 보기에는 프로그래밍 언어를 구현하는 단순 파싱 문제로 보이나, 최악의 경우 REPEAT 100000 블록이 24번까지 중첩될 수 있음이 문제다. 즉, REPEAT 블록을 최적화하는 것이 관건인데, 아래 조건에 주목해야 한다.
PRINT는 최대 20번 실행된다.
즉, 문제가 되는 프로그램에서는 PRINT가 없는, 대입문만 있는 REPEAT, 또는 그것과 다른 대입문만을 포함하는 REPEAT가 런타임의 대부분임을 알 수 있다. 이를 순수한 REPEAT문이라 하자. 그렇다면 순수한 REPEAT문은 어떻게 치환할 수 있을까?
2. 아핀 행렬
파싱 후 정리한 결과로 다음과 같은 식을 얻었다고 하자.
이때, 는 번째 문자에 해당하는 현재 변수값이고, 는 각 항의 계수들이다. 은 상수항이다.
치환될 번째 문자가 아닌 다른 변수에 대해
가 있다고 생각한다면, 이 26+1개의 식을 행렬과 벡터를 사용해 표현할 수 있다.
여기서, 행렬의 합을 곱으로 취급하도록 하는 아핀 행렬(affine matrix)을 이용하면 이를 다음과 같이 쓸 수 있다.
이로써 대입문을 단일 행렬곱으로 나타낼 수 있게 되었으니, 행렬곱과 거듭제곱을 반복해 순수한 REPEAT문 블록 내부 전체에 대응하는 행렬도 구할 수 있을 것이다.
3. 분할 정복을 이용한 행렬 거듭제곱
순수한 REPEAT n 블록의 실행 결과는 블록 내에 해당하는 행렬의 곱셈을 번 반복한 것이므로, 행렬의 거듭제곱을 보다 빠르게 할 수 있다면 문제를 풀 수 있다.
다행히 이전에 백준 11444 '피보나치 수 6'을 풀며, '분할 정복'을 이용해 어떤 대상의 거듭제곱을 에 할 수 있음을 알았으니 이를 그대로 적용하면 될 것이다.
3. 그리고...
아쉽게도 순수하지 않은 REPEAT문에 대해서는 이 방법을 쓸 수가 없다. 각 명령어를 순회하며 실행(evaluate)하는 구현도 따로 만들어야 한다.
코드 (Kotlin)
fun main() {
readln()
val prog = Program()
parse(prog.root)
prog.run()
}
fun parse(parent: BlockStmt) {
while (true) {
val line = readln().trim()
if (line == "STOP") return
if (line.startsWith("REPEAT")) {
val cnt = line.split(' ').filter { it.isNotEmpty() }[1].toInt()
val repeat = Repeat(parent.prog, parent, cnt)
parse(repeat)
parent.appendStmt(repeat)
continue
}
if (line.startsWith("PRINT")) {
val idx = line.split(' ')[1][0] - 'a'
parent.appendStmt(Print(parent.prog, parent, idx))
continue
}
else {
val words = line.split(' ')
val lhs: Int = words[0][0] - 'a'
val expr = Vec()
for (i in 2..<words.size step 2) {
val sgn = if (words[i-1] == "-") -1 else 1
val word = words[i]
val lastLetter = word[word.length - 1]
val (mag, idx) =
if (lastLetter in 'a'..'z')
(if (word.length == 1) 1 else (word.substring(0, word.length - 1).toInt())) to lastLetter - 'a'
else word.toInt() to 26
expr[idx] = expr[idx] mplus sgn * mag
}
parent.appendStmt(Assignment(parent.prog, parent, lhs, expr))
continue
}
}
}
const val MOD = 10000
infix fun Int.mplus(that: Int) = ((this + MOD) + (that + MOD)) % MOD
infix fun Int.mtimes(that: Int) = ((this + MOD) * (that + MOD)) % MOD
class Vec(val vals: IntArray = IntArray(27)) {
operator fun get(i: Int) = vals[i]
operator fun set(i: Int, value: Int) { vals[i] = value % MOD }
}
class Mat(val cols: Array<Vec> = Array(27) { Vec() }) {
operator fun get(i: Int, j: Int) = cols[i][j]
operator fun set(i: Int, j: Int, value: Int) { cols[i][j] = value % MOD }
infix fun mtimes(that: Mat) = Mat().also {
for (i in 0..<27) {
for (j in 0..<27) {
// it[i, j] = (0..<27).reduce { acc, k -> acc mplus (this[i, k] mtimes that[k, j]) }
var acc = 0
for (k in 0..<27) {
acc = acc mplus (this[i, k] mtimes that[k, j])
}
it[i, j] = acc
}
}
}
infix fun mtimes(that: Vec) = Vec().also {
for (i in 0..<27) {
// it[i] = (0..<27).reduce { acc, k -> acc mplus (this[i, k] mtimes that[k]) } // why not working?
var acc = 0
for (k in 0..<27) {
acc = acc mplus (this[i, k] mtimes that[k])
}
it[i] = acc
}
}
infix fun mpow(n: Int): Mat {
if (n==0)
return eye()
if (n==1)
return this
val powHalf = mpow(n/2)
var result = powHalf mtimes powHalf
if (n % 2 == 1)
result = this mtimes result
return result
}
companion object {
fun eye() = Mat()
.also { mat -> (0..<27).forEach { k -> mat[k, k] = 1 } }
fun assigner(idx: Int, expr: Vec) = eye()
.also { mat -> (0..<27).forEach { j -> mat[idx, j] = expr[j] } }
}
}
interface Stmt {
val prog: Program
val parent: Stmt?
val pure: Boolean
fun run()
fun evaluate()
fun assigner(): Mat
}
interface BlockStmt : Stmt {
val stmts: List<Stmt>
fun appendStmt(stmt: Stmt)
}
abstract class StmtBase(
override val prog: Program,
override val parent: Stmt?
): Stmt {
override fun run() = evaluate()
}
abstract class BlockStmtBase(prog: Program, parent: Stmt?) : StmtBase(prog, parent), BlockStmt {
override val stmts: MutableList<Stmt> = mutableListOf()
override var pure = true
override fun appendStmt(stmt: Stmt) {
stmts += stmt
if (!stmt.pure) pure = false
}
override fun run() {
if (pure) {
prog.mem = assigner() mtimes prog.mem
}
else {
evaluate()
}
}
override fun assigner(): Mat {
if (!pure) throw IllegalStateException()
return stmts.map { it.assigner() }.reduce { acc, mat -> mat mtimes acc }
}
}
class Program {
var mem = Vec().also { it[26] = 1 }
val root = Root(this)
fun run() {
root.run()
}
}
class Root(prog: Program) : BlockStmtBase(prog, null) {
override fun evaluate() {
stmts.forEach { it.run() }
}
}
class Assignment(prog: Program, parent: Stmt?, val lhs: Int, val expr: Vec) : StmtBase(prog, parent) {
override val pure: Boolean = true
override fun evaluate() {
prog.mem = assigner() mtimes prog.mem
}
override fun assigner(): Mat = Mat.assigner(lhs, expr)
}
class Print(prog: Program, parent: Stmt?, val idx: Int) : StmtBase(prog, parent) {
override val pure: Boolean = false
override fun evaluate() {
println("${'a' + idx} = ${prog.mem[idx]}")
}
override fun assigner(): Mat = throw IllegalStateException()
}
class Repeat(prog: Program, parent: Stmt?, val cnt: Int): BlockStmtBase(prog, parent) {
override fun evaluate() {
repeat(cnt) { stmts.forEach { stmt -> stmt.run() } }
}
override fun assigner(): Mat = super.assigner() mpow cnt
}메모리 및 시간
- 메모리: 38416 KB
- 시간: 524 ms
후기
- 시행착오
- 모듈로 더하기, 곱하기 연산 시 숫자가 음수로 떨어질 수 있는 경우를 고려하지 못했다.
- 연산자 사이에는 공백이 있다 했는데, TC 중에서 공백이 2칸 이상 띄어져 있는 경우도 있는 것 같다.
- 다행히 백준 섭종 전에 제출을 할 수 있었다.
- 요즘 DSL을 만들기 위해 공부하고 있는데, 최적화에 대해서도 한 번 생각해볼만한 문제였던 것 같다.
- (수정 260429) 행렬 연산식을 구하는 과정을 좀 더 상세히 썼다.
유사 개발자