水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

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).

解答

beta.atcoder.jp

一発 AC 出来たのでよかった.

f:id:babcs2035:20181123160538p:plain