ABC411-D AtCoder Beginner Contest 411 D　Swiftで競技プログラミング

問題はこちら→https://atcoder.jp/contests/abc411/tasks/abc411_d

そのままのシミュレートではTLEやMLEになってしまいます。
サーバーに関する情報の遷移だけをみていくことにしよう。

t番目のクエリが完了した時点でのi番目のpcの状態を
\[p(t,i)\]と書くことにしよう。これを用いてクエリを表現すると次のようになります。

クエリ 1 p の場合

\[i=p\Longrightarrow p(t,p) = p(t-1,0)\\ i\neq p\Longrightarrow p(t,i)=p(t-1,i)\]

クエリ 2 p sの場合

\[i=p\Longrightarrow p(t,p) = p(t-1,p) + s\\ i\neq p\Longrightarrow p(t,i)=p(t-1,i)\]

クエリ 3 pの場合

\[i=p\Longrightarrow p(t,0) = p(t-1,p)\\ i\neq p\Longrightarrow p(t,i)=p(t-1,i)\]

という式が得られます。 今求めたいのは\[p(Q,0)\]なので、このクエリを逆順に辿っていきましょう。

とりあえずt=Qを見てみましょう

\[
\begin{eqnarray}
p(Q,0)
=
\begin{cases}
p(Q-1,0) & (クエリ1) \\
p(Q-1,0) + s_q & ( クエリ2 ) \\
p(Q-1,p) & (クエリ3)
\end{cases}
\end{eqnarray}
\]

t=Q-1は
\[
\begin{eqnarray}
p(Q-1,0)
=
\begin{cases}
p(Q-2,0) & (クエリ1) \\
p(Q-2,0) + s_{q-1} & ( クエリ2 ) \\
p(Q-2,p) & (クエリ3)
\end{cases}
\end{eqnarray}
\]

\[
\begin{eqnarray}
p(Q-1,p)
=
\begin{cases}
p(Q-2,0) & (クエリ1) \\
p(Q-2,p) + s_{q-1} & ( クエリ2 ) \\
p(Q-2,p) & (クエリ3)
\end{cases}
\end{eqnarray}
\]

となり、遷移状態を（一部ですが）書き出すことができます。ひとまずt=Q-1でクエリ2が適用されていたとすると、次のように遷移します。

\[
\begin{eqnarray}
p(Q,0)
=
\begin{cases}
p(Q-1,0) = p(Q-2,0) + s_{q-1} & (t = Qでクエリ1) \\
p(Q-1,0) + s_q = p(Q-2,0) + s_{q-1} + s_q & (t = Qでクエリ2 ) \\
p(Q-1,p) = p(Q-2,p) + s_{q-1} & (t = Qでクエリ3)
\end{cases}
\end{eqnarray}
\]

このことから、答えを求めるにはクエリを逆順に辿っていけば良いことがわかります。上式を辿っていくと最後はp(0,i)とかp(0,0)が必ず登場します。これは問題の条件から空文字””であることがわかっており、かつ初期条件なので、ここで処理が終了になります。

上記の遷移をクエリに従い実行していけば自然と答えがもとまるようになっています。

実装

以上より、プログラムの方針は次のとおりです。

初期状態　serverStr = “”, t=Q, i=0 からスタート

クエリ1 p の場合
i=pならばiを0で置き換える。つまりi=0にする。

クエリ2 p s の場合
i=pならばserverStrをs+serverStrに置き換える。つまりserverStr = s + serverStr（+=が使えないことに注意）

クエリ3 p の場合
i=0ならiをpで置き換える。つまりi=pにする。

ここでクエリ2について注意です。serverStr = s + serverStrをそのままやるとコピーの時間により実行時間が悪化します。そのため文字列を逆に足していきます。つまりserverStr += s.reversed()としておき、最後にまたserverStr.reversed()をとることで正しい文字列を得ることができます。

いかがSwiftによる実装です。

コード

import Foundation

func readStrings() -> [String] {
    return readLine()!.split(separator: " ").map { String($0) }
}

func read2IntsTuple() -> (Int,Int){
    let tmp = readInts()
    return (tmp[0],tmp[1])
}

let (N,Q) = read2IntsTuple()
var queries = [[String]]()
for _ in 0 ..< Q{
    queries.append(readStrings())
}
var serverStr = ""

var i = 0
for q in 0 ..< Q{
    let t = Q - 1 - q
    let query = queries[t]
    let num = Int(query[0])!
    let p = Int(query[1])!
    if num == 1{
        if i == p{
            i = 0
        }
    }else if num == 2{
        if i == p{
            let s = query[2].reversed()
            serverStr += s
        }

    }else{
        if i == 0{
            i = p
        }
    }
}

print(String(serverStr.reversed()))

クエリを逆順に辿っていく手法はよくあるので覚えておきましょう。

これでAtCoder Beginner Contest 411 Dを解くことができました。