GCJ Qualification Round 2016 D. Fractiles
問題概要
以下のルールにしたがって再帰的に文字列を作る。
- もとの文字列 So がある。
- S[i]='L' だったら、その部分を So に置き換える。
- S[i]='G' だったら、その部分を So と同じ長さ分だけ 'G' を並べた文字列に置き換える。
- これを C-1 回繰り返す。
元の文字列の長さ K と繰り返す回数 C が与えられる。元の文字列が具体的に何であったかは分からない。
元の文字列が L だけであることを確認するにはどこを見ればいいだろうか。ただし見ることのできる位置は S 箇所までとする。
解法（small）
1,2,..., K を見れば分かる。
なぜなら So[0]='L' だったら S の先頭 K 文字は So そのものなはずで、So[0]='G' だったら先頭 K 文字は 'G' になるから So[0]='G' であることが分かるからだ。
解法（large）
簡単にスライドにした。
この方法では一箇所見ることで C 箇所を調べられる。おそらくこれが最適。
調べる位置のインデックスはどうやって求めれば良いのだろうか。
下図のように文字列に番号をつける。この番号でなら簡単に求まる。
なぜなら次のような関係があるからだ。
この方法で求めたインデックスは全体を通してのインデックスなので、適当に調整すれば終わり。
GCJ Qualification Round 2016 D. Fractiles
smallが自明すぎてうっかり先にsmallだけ提出してしまった。large解のチェックのために取っておいた方が良かったかな。
