JOI '15 春合宿1日目:1 - コピー&ペースト2
問題
https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d1.pdf
解法
K <= 200 という制約から考えると「全ての操作後の文字列の 1 ~ K 文字目は元の文字列の何文字目か?」という問題を解けばいい.これは,操作を逆から見ていくことで求められる.具体的には,求める文字の操作中の位置を pos と置くと,各操作をする前の文字列での位置は
・pos 文字目がコピペの範囲に入っているとき:A + (pos - C) 文字目
・pos 文字目がコピペの範囲の右側のとき:pos - (B - A) 文字目
・pos 文字目がコピペの範囲の左側のとき:変わらない(pos 文字目)
となる.O(NK).
解答
一発 AC 出来たのでよかった.