A - Advance to the End

概要

基本的な文字列の扱いに慣れる問題です．
各言語の仕様をきちんと把握しておくことで，素早く解答ができるでしょう．

問題原案：@machoniump

解説

入力の受け取りや出力については，ここでは説明されていません．
そういった内容が知りたい方は各言語のリファレンス等を見たり「標準入出力」などといったキーワードを用いて検索をかけたりするとよいでしょう．
「計算量」などの用語やプログラミング言語の基礎的な文法についてもの意味についても同様です。

$Ⅰ.$ 「操作」の言い換え

「$S$ の先頭の $1$ 文字を $S$ の末尾に移動する」という操作をプログラムで表現するにはどうするのがよいでしょうか．
色々な方法が考えられますが，そのうちの一つをご紹介します．

与えられた操作を整理してみましょう．
$S=S_1S_2S_3 \ldots S_N$ とすると，$1$ 回操作したあとの文字列は $S_2S_3 \ldots S_NS_1$ になります．
これからわかる通り，件の操作は「$S$ を先頭の $1$ 文字と，それ以外の文字列に分割し，それらの順番を逆にして連結する」のように言い換えることができます．
上記の場合は $S_1$ と $S_2S_3 \ldots S_N$ に分割すればよいです．

$Ⅱ.$ 実装

では，これをコードにしてみましょう．
上記のことを実装するには次の二つのことができればよいです．

• $S$ の先頭の $1$ 文字を取得する $\cdots (1)$
• $S$ の $2$ 文字目以降を取得する $\cdots (2)$

$(1)$ は，多くの言語で S[0] というようにして行うことができます．
$(2)$ は，for 文によって $2$ 文字目以降を順番に取得していくことでも実現できますが，substr() などの関数を使用すると便利でしょう．
この関数や類似の機能はほとんどの言語に存在します．詳しい仕様については確認言語のリファレンスを参照してください．

以上のことを $K$ 回繰り返すことで，目的の文字列が得られます．

$Ⅲ.$ 計算量の見積もり

ほとんどの言語で，「文字列の一部を $L$ 文字分を取得する」という操作の時間計算量は $O(L)$ です．
また，「複数の文字列を連結する」という操作では，大抵連結後の文字列を新たに生成することになるため，計算量はその文字列の長さに比例します．

今回の「$S$ を先頭の $1$ 文字と，それ以外の文字列に分割し，それらの順番を逆にして連結する」という操作では，

• 先頭の $1$ 文字を取得するのに $(1)$
• 先頭の $1$ 文字以外を取得するのに $(N)$
• 上記二つの順番を入れ替えて連結するのに $(N)$

で，以上を合わせて $O(N)$ です．

さらにそれらを $K$ 回繰り返すので，全体では $O(NK)$ となります．
$N, K \leq 1000$ という制約より，これは $2$ 秒の実行時間制限に十分間に合います．

$Ⅳ.$ 発展

$1)$ ボーナス問題

解説はこのページの下部にあります
(難易度順)

• $\text{A)}\hspace{0.5em}$ $1 \leq K \leq 10^{18}$ という制約下でこの問題を解いてください．$K$ 以外の制約に変更はありません．
• $\text{B)}\hspace{0.5em}$ $1 \leq N \leq 2 \times 10^5,\, 1 \leq K \leq 10^{18}$ という制約下でこの問題を解いてください．$N, K$ 以外の制約に変更はありません．

$2)$ 類題

(難易度順)

• ABC 197 $\hspace{0.15em}$ A - Rotate
• ABC 103 $\hspace{0.15em}$ B - String Rotation
• ABC 258 $\hspace{0.15em}$ C - Rotation

実装例

xxxxxxxxxx

#include <bits/stdc++.h>

using namespace std;

​

int main() {

    int N, K; cin >> N >> K;

    string S; cin >> S;

    for(int i=0; i<K; ++i) S = S.substr(1) + S[0];

    cout << S << "\n";

    return 0;

}

xxxxxxxxxx

N, K = map(int, input().split())

S = input()

for _ in [0] * K: S = S[1:] + S[0]

print(S)

xxxxxxxxxx

interface Main {

  static void main(String[] $) {

    var scanner = new java.util.Scanner(System.in);

    int N = scanner.nextInt(), K = scanner.nextInt();

    String S = scanner.next();

    for(int i=0; i<K; ++i) S = S.substring(1) + S.charAt(0);

    System.out.println(S);

  }

}

ボーナス問題(解答)

• $\text{A)}$
  与えられた操作を $N$ 回繰り返すことで，最初の $S$ に一致します．
  したがって，「$S$ に対して $K$ 回操作した後の文字列」と「$S$ に対して $K\%N$ 回操作した後の文字列」は等しくなります．
  ですから，$K$ の代わりに $K\%N$ の用いることで，時間計算量 $O(N^2)$ でこの問題を解くことができます．
• $\text{B)}$ $S$ の末尾と先頭とがつながっていると仮定すると，「操作によって文字の順番は変化しない」とみることもできます．
  このように考えた場合，与えられた操作は「どこの文字を先頭とするか」を動かしていることにすぎません．
  これは，先述のテクニックと組み合わせて $K = K\%N$ とすることで，「『 $S$ の先頭から $K$ 文字目まで』と『$S$ の $K+1$文字目から末尾まで』を入れ替える」として実現することができます．
  さらに，$0 \leq K\%N < N \hspace{0.2em} (N,K > 0)$ のもとでは実際に「$S$ を $2$ つ連結した文字列の$K$ 文字目から $N$ 文字分」を切り出してもよいです．
  これらの時間計算量はいずれも $O(N)$ です．
  実装例(Python):

xxxxxxxxxx

N,K=map(int,input().split())

S=input()

print((S+S)[K%N:K%N+N])