Overall Editorial by cirno3153

このユーザー解説はJava/Kotlinにおける実装例を紹介するものとなっています。

A問題 - When?

今が0時0分から \(X\) 分経過していることが分かっているとき、時刻は \(\lfloor \frac{X}{60} \rfloor\) 時 \((X \bmod 60)\) 分です。 従って、これを出力すれば良いです。

Javaの実装例

import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int K = sc.nextInt() + 21 * 60; // 0時0分からの経過時刻に直しておく
      out.printf("%02d:%02d\n", K / 60, K % 60); // %02dは、整数を2桁0埋めして出力
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val K = sc.nextInt() + 21 * 60; // 0時0分からの経過時刻に直しておく
    println("%02d:%02d".format(K / 60, K % 60)) // %02dは、整数を2桁0埋めして出力
  }
}

B問題 - Number Box

高橋君は、最初のマスと移動方向を決めるとその時にできる整数が定まります。 従って、最初のマスが \(N^2\) 通りあり、それぞれについて長さ \(N\) の整数を生成するので計算量 \(O(N^3)\) 程度で解けることが分かります。

では、具体的な実装について検討してみましょう。

まず、この問題は整数ではなく文字列の辞書順最大として解いても構いません。

というのも、全ての整数の桁数が同じなので、整数としての大小関係は文字列としての大小関係に等しいからです。 例えば \(123 < 456\) のとき、“123” < “456”です。

後は \(8\) 方向への移動ですが、これは実装方針が二つあります。

方針1: 移動ベクトルを持つ

最初のマスを \((x, y)\) 、移動ベクトルを \((d_x, d_y)\) とすると、通るマスは \((x, y), (x + d_x, y + d_y), \ldots, (x + (N - 1)d_x, y + (N - 1)d_y)\) となります。

\((d_x, d_y)\) の候補は \((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)\) なので、これを全部試せばよいです。

Javaの実装例

import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      char[][] A = new char[N][];
      for (int y = 0;y < N;++ y) A[y] = sc.next().toCharArray();
      
      int[] dx = {1, 1, 0, -1, -1, -1, 0, 1};
      int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
      
      String ans = ""; // 辞書順最大の文字列を求める、初期値は辞書順最小(これは空文字列)
      for (int y = 0;y < N;++ y) {
        for (int x = 0;x < N;++ x) {
          for (int d = 0;d < 8;++ d) {
            StringBuilder sb = new StringBuilder(); // 文字列の連結を行う
            for (int i = 0;i < N;++ i) sb.append(A[(y + dy[d] * i + N) % N][(x + dx[d] * i + N) % N]);
            String gen = sb.toString(); // 初期マスと移動方向を決めたときに作られる文字列
            if (ans.compareTo(gen) < 0) ans = gen;
          }
        }
      }
      out.println(ans);
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val A = Array(N) {sc.next()}
    
    val dx = arrayOf(1, 1, 0, -1, -1, -1, 0, 1)
    val dy = arrayOf(0, 1, 1, 1, 0, -1, -1, -1)
    
    var ans = "" // 辞書順最大の文字列を求める、初期値は辞書順最小(これは空文字列)
    for (y in 0 until N) {
      for (x in 0 until N) {
        for (d in 0 until 8) {
          val gen = (0 until N) // 初期マスと移動方向を決めたときに作られる文字列
            .map {A[(y + dy[d] * it + N) % N][(x + dx[d] * it + N) % N]}
            .joinToString(separator="")
          if (ans < gen) ans = gen
        }
      }
    }
    println(ans)
  }
}

位相に着目すると、もう少し実装を簡単にすることができます。

\(\sin \theta \) と \(\cos \theta \) は丁度 \(90^\circ\) だけずれる関係なので、 \(y\) 方向の移動ベクトルの列 \((0, 1, 1, 1, 0, -1, -1, -1, \ldots)\) に対して、 \(x\) 方向の移動ベクトルの列は \(y\) 方向の移動ベクトルの列を \(2\) 個ずらしたものになります。

従って、 \(D = (0, 1, 1, 1, 0, -1, -1, -1, 0, 1)\) に対して、 \((d_x, d_y) = (D_{i+2}, D_i) (0 \leq i < 8)\) と表せます。

Javaの実装例

import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      char[][] A = new char[N][];
      for (int y = 0;y < N;++ y) A[y] = sc.next().toCharArray();
      
      int[] direction = {0, 1, 1, 1, 0, -1, -1, -1, 0, 1};
      
      String ans = ""; // 辞書順最大の文字列を求める、初期値は辞書順最小(これは空文字列)
      for (int y = 0;y < N;++ y) {
        for (int x = 0;x < N;++ x) {
          for (int d = 0;d < 8;++ d) {
            StringBuilder sb = new StringBuilder(); // 文字列の連結を行う
            for (int i = 0;i < N;++ i) sb.append(A[(y + direction[d] * i + N) % N][(x + direction[d + 2] * i + N) % N]);
            String gen = sb.toString(); // 初期マスと移動方向を決めたときに作られる文字列
            if (ans.compareTo(gen) < 0) ans = gen;
          }
        }
      }
      out.println(ans);
    }
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val A = Array(N) {sc.next()}
    
    val direction = arrayOf(0, 1, 1, 1, 0, -1, -1, -1, 0, 1)
    
    var ans = "" // 辞書順最大の文字列を求める、初期値は辞書順最小(これは空文字列)
    for (y in 0 until N) {
      for (x in 0 until N) {
        for (d in 0 until 8) {
          val gen = (0 until N) // 初期マスと移動方向を決めたときに作られる文字列
            .map {A[(y + direction[d] * it + N) % N][(x + direction[d + 2] * it + N) % N]}
            .joinToString(separator="")
          if (ans < gen) ans = gen
        }
      }
    }
    println(ans)
  }
}

方針2: グリッドを回転させる

与えられたマス目を回転させることで、実装を簡単にするテクニックがあります。

仮に、左から右へ探索するコード及び左上から右下が書けたとします。 このとき、マス目を90度回転させるコードがあるならば、探索→90度回転、を4回行えば答えを求めることができます。

では90度回転はどのように実装すればよいのでしょうか？ これは、座標 \((x, y)\) を \((-y, x)\) に変換すれば良いです。

なぜこの実装が正しいのか これは、アフィン変換という概念を考えると分かります。

詳細な解説はABC244-Bの解説に書いていますが、回転行列というものを使います。 回転行列では、座標 \((x, y)\) を \(\theta\) だけ反時計回りに回転させてできる座標 \((x', y')\) は次のように表せます。

\( \begin{pmatrix} x' \\ y' \\ 1 \\ \end{pmatrix} = \begin{pmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \\ \end{pmatrix} \)

ここで \(\theta = 90^\circ\) を代入すると、 \((x', y') = (x \cos \theta - y \sin \theta, x \sin \theta + y \cos \theta) = (-y, x)\) となります。

Javaの実装例

import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      char[][] A = new char[N][];
      for (int y = 0;y < N;++ y) A[y] = sc.next().toCharArray();
      
      String ans = ""; // 辞書順最大の文字列を求める、初期値は辞書順最小(これは空文字列)
      for (int loop = 0;loop < 4;++ loop) {
        for (int y = 0;y < N;++ y) {
          for (int x = 0;x < N;++ x) {
            StringBuilder sb = new StringBuilder(); // 文字列の連結を行う
            for (int i = 0;i < N;++ i) sb.append(A[y][(x + i) % N]);
            String gen = sb.toString(); // 初期マスから右に動いた時に作られる文字列
            if (ans.compareTo(gen) < 0) ans = gen;
            sb = new StringBuilder();
            for (int i = 0;i < N;++ i) sb.append(A[(y + i) % N][(x + i) % N]);
            gen = sb.toString(); // 初期マスから右下に動いた時に作られる文字列
            if (ans.compareTo(gen) < 0) ans = gen;
          }
        }
        A = rotate(A);
      }
      out.println(ans);
    }
  }
  
  static char[][] rotate(char[][] grid) {
    int H = grid.length, W = grid[0].length;
    char[][] ret = new char[W][H];
    for (int y = 0;y < H;++ y) {
      for (int x = 0;x < W;++ x) {
        ret[x][(H - y) % H] = grid[y][x];
      }
    }
    return ret;
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    var A = Array(N) {sc.next()}
    
    val direction = arrayOf(0, 1, 1, 1, 0, -1, -1, -1, 0, 1)
    
    var ans = "" // 辞書順最大の文字列を求める、初期値は辞書順最小(これは空文字列)
    repeat(4) {
      for (y in 0 until N) {
        for (x in 0 until N) {
          val right = (0 until N) // 初期マスから右に動いた時に作られる文字列
            .map {A[y][(x + it) % N]}
            .joinToString(separator="")
          if (ans < right) ans = right
          val rightDown = (0 until N) // 初期マスから右下に動いた時に作られる文字列
            .map {A[(y + it) % N][(x + it) % N]}
            .joinToString(separator="")
          if (ans < rightDown) ans = rightDown
        }
      }
      A = rotate(A)
    }
    println(ans)
  }
}

fun rotate(A : Array<String>) = 
  Array(A[0].length) {y -> 
    (0 until A.size)
      .map {x -> A[(A.size - x) % A.size][y]}
      .joinToString(separator="")}

この問題は更に高速に解くことができます。

簡単のため、左から右に向かう場合について考えます。

この時、ある行に書かれた文字列を \(S\) とすると、その中から始点を一つ選んで移動することは \(S\) をrotateしたものの辞書順最大を求める問題になります。 \(\mathrm{rotate}_i(S)\) を \(S\) を \(i\) 文字rotateしたものと定義すると、求めたいものは \(\max(\mathrm{rotate}_0(S), \mathrm{rotate}_1(S), \ldots, \mathrm{rotate}_{N-1}(S))\) です。 例えば \(S\) がatcoderのとき、atcoder, tcodera, coderat, oderatc, deratco, eratcod, ratcodeの最大値でatcoderとなります。

この問題を \(O(N)\) で解くことで、全体の計算量を \(O(N^2)\) にすることができます。 さて、この問題を \(O(N)\) で解く方法について説明します。

AtCoder Libraryにもある文字列アルゴリズムの一つに、Suffix Arrayというものがあります。 これは、 \(1 \leq i \leq N\) を満たす各 \(i\) について \(S_i\) を \(S\) の \(i\) 文字目から \(N\) 文字目までを切り出した文字列としたとき、 \(S_i\) は \(S_1, \ldots, S_N\) の中で何番目の文字列かを \(O(N)\) で求めるものです。 例えば \(S\) がatcoderのとき、Suffix Arrayはatcoder, tcoder, coder, oder, der, er, r で、辞書順だと順に \(1, 3, 5, 6, 4, 7, 2\) 番目の文字列が並びますね。

さて、 \(T\) を \(S\) を \(2\) 回繰り返した文字列と定義します。 このとき、 \(T\) のSuffix Arrayのうち、先頭 \(N\) 個の値は \(S\) をrotateしたものの辞書順と一致します。 何故、このことが成り立つのでしょうか？

\(T_i\) は、先頭が \(\mathrm{rotate}_i(S)\) であり、次に何文字かがくっついている構造になっています。 ここで、 \(\mathrm{rotate}_i(S) < \mathrm{rotate}_j(S)\) であったとすると、 \(T_i\) の先頭 \(N\) 文字より \(T_j\) の先頭 \(N\) 文字の方が大きいので \(T_i < T_j\) が成り立ちます。 従って、これは求めたいものと一致します。

Javaの実装例

import java.util.Scanner;
import static java.lang.System.out;
import java.util.ArrayList;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      char[][] A = new char[N][];
      for (int y = 0;y < N;++ y) A[y] = sc.next().toCharArray();
      
      ArrayList<String> candidate = new ArrayList<>(8 * N);
      for (int loop = 0;loop < 4;++ loop) {
        for (int y = 0;y < N;++ y) {
          StringBuilder sb = new StringBuilder(); // 文字列の連結を行う
          for (int i = 0;i < N;++ i) sb.append(A[y][i]);
          candidate.add(sb.toString()); // 初期マスから右に動いた時に作られる文字列
          sb = new StringBuilder();
          for (int i = 0;i < N;++ i) sb.append(A[(y + i) % N][i]);
          candidate.add(sb.toString()); // 初期マスから右下に動いた時に作られる文字列
        }
        A = rotate(A);
      }
      
      String ans = ""; // 辞書順最大の文字列を求める、初期値は辞書順最小(これは空文字列)
      for (String s : candidate) { // sをrorateさせた時の辞書順最大を求める
        String connect = s + s;
        int[] suffixArray = suffixArray(connect);
        for (int i = suffixArray.length - 1;i >= 0;-- i) {
          if (suffixArray[i] >= N) continue;
          String maxString = connect.substring(suffixArray[i], suffixArray[i] + N); // iから始めた文字列が最大
          if (ans.compareTo(maxString) < 0) ans = maxString;
          break;
        }
      }
      out.println(ans);
    }
  }
  
  static char[][] rotate(char[][] grid) {
    int H = grid.length, W = grid[0].length;
    char[][] ret = new char[W][H];
    for (int y = 0;y < H;++ y) {
      for (int x = 0;x < W;++ x) {
        ret[x][(H - y) % H] = grid[y][x];
      }
    }
    return ret;
  }
  
  private static int[] sais(int[] s, int upper) {
    int n = s.length;
    if (n == 0) return new int[0];
    if (n == 1) return new int[]{0};
    if (n == 2) {
      if (s[0] < s[1]) return new int[]{0, 1};
      return new int[]{1, 0};
    }

    int[] sa = new int[n];
    boolean[] ls = new boolean[n];
    for (int i = n - 2; i >= 0; i--) ls[i] = s[i] == s[i + 1] ? ls[i + 1] : s[i] < s[i + 1];

    int[] sumL = new int[upper + 1];
    int[] sumS = new int[upper + 1];

    for (int i = 0; i < n; i++) {
      if (ls[i]) sumL[s[i] + 1]++;
      else sumS[s[i]]++;
    }

    for (int i = 0; i < upper; i++) {
      sumS[i] += sumL[i];
      sumL[i + 1] += sumS[i];
    }
    sumS[upper] += sumL[upper];

    java.util.function.Consumer<int[]> induce = lms -> {
      java.util.Arrays.fill(sa, -1);
      int[] buf = sumS.clone();
      for (int d : lms) {
        if (d == n) continue;
        sa[buf[s[d]]++] = d;
      }
      System.arraycopy(sumL, 0, buf, 0, upper + 1);
      sa[buf[s[n - 1]]++] = n - 1;
      for (int v : sa) if (v >= 1 && !ls[v - 1]) sa[buf[s[v - 1]]++] = v - 1;
      System.arraycopy(sumL, 0, buf, 0, upper + 1);
      for (int i = n - 1; i >= 0; i--) {
        int v = sa[i];
        if (v >= 1 && ls[v - 1]) sa[--buf[s[v - 1] + 1]] = v - 1;
      }
    };

    int[] lmsMap = new int[n + 1];
    java.util.Arrays.fill(lmsMap, -1);
    int m = 0;
    for (int i = 1; i < n; i++) if (!ls[i - 1] && ls[i]) lmsMap[i] = m++;

    int[] lms = new int[m];
    {
      int p = 0;
      for (int i = 1; i < n; i++) if (!ls[i - 1] && ls[i]) lms[p++] = i;
    }
    induce.accept(lms);

    if (m > 0) {
      int[] sortedLms = new int[m];
      {
        int p = 0;
        for (int v : sa) if (lmsMap[v] != -1) sortedLms[p++] = v;
      }
      int[] recS = new int[m];
      int recUpper = 0;
      recS[lmsMap[sortedLms[0]]] = 0;
      for (int i = 1; i < m; i++) {
        int l = sortedLms[i - 1], r = sortedLms[i];
        int endL = (lmsMap[l] + 1 < m) ? lms[lmsMap[l] + 1] : n;
        int endR = (lmsMap[r] + 1 < m) ? lms[lmsMap[r] + 1] : n;
        boolean same = true;
        if (endL - l != endR - r) same = false;
        else {
          while (l < endL && s[l] == s[r]) {
            l++;
            r++;
          }
          if (l == n || s[l] != s[r]) same = false;
        }
        if (!same) recUpper++;
        recS[lmsMap[sortedLms[i]]] = recUpper;
      }
      int[] recSA = sais(recS, recUpper);

      for (int i = 0; i < m; i++) sortedLms[i] = lms[recSA[i]];
      induce.accept(sortedLms);
    }
    return sa;
  }

  public static int[] suffixArray(char[] s) {
    int[] s2 = new int[s.length];
    for (int i = 0; i < s2.length; i++) s2[i] = s[i];
    return sais(s2, 255);
  }

  public static int[] suffixArray(String s) {
    return suffixArray(s.toCharArray());
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    var A = Array(N) {sc.next()}
    
    val direction = arrayOf(0, 1, 1, 1, 0, -1, -1, -1, 0, 1)
    
    val candidate = mutableListOf<String>()
    repeat(4) {
      for (y in 0 until N) {
        val right = (0 until N) // 初期マスから右に動いた時に作られる文字列
          .map {A[y][it]}
          .joinToString(separator="")
        candidate.add(right)
        val rightDown = (0 until N) // 初期マスから右下に動いた時に作られる文字列
          .map {A[(y + it) % N][it]}
          .joinToString(separator="")
        candidate.add(rightDown)
      }
      A = rotate(A)
    }
    
    val ans = candidate.map { // 辞書順最大の文字列を求める
        val connect = it + it
        val suffixArray = suffixArray(connect)
        for (sa in suffixArray.reversed()) {
          if (sa < N) return@map connect.substring(sa, sa + N) // saから始めた文字列が最大
        }
        return@map ""
      }.max()
    println(ans)
  }
}

fun rotate(A : Array<String>) = 
  Array(A[0].length) {y -> 
    A.indices
      .map {x -> A[(A.size - x) % A.size][y]}
      .joinToString(separator="")}


fun suffixArray(s: String) = suffixArray(s.toCharArray())

fun suffixArray(s: CharArray) = sais(IntArray(s.size) {s[it].toInt()}, 255)

fun sais(s : IntArray, upper: Int): IntArray {
  val n = s.size
  if (n <= 1) return IntArray(n){it}
  if (n == 2) {
    return if (s[0] < s[1]) intArrayOf(0, 1) else intArrayOf(1, 0)
  }

  val sa = IntArray(n)
  val ls = BooleanArray(n)
  for (i in n - 2 downTo 0) ls[i] = if (s[i] == s[i + 1]) ls[i + 1] else s[i] < s[i + 1]

  val sumL = IntArray(upper + 1)
  val sumS = IntArray(upper + 1)

  for (i in 0 until n) {
    if (ls[i]) sumL[s[i] + 1]++
    else sumS[s[i]]++
  }

  for (i in 0 until upper) {
    sumS[i] += sumL[i]
    sumL[i + 1] += sumS[i]
  }
  sumS[upper] += sumL[upper]

  val induce = { lms: IntArray -> 
    sa.fill(-1)
    val buf = sumS.clone()
    for (d in lms) {
      if (d == n) continue
      sa[buf[s[d]]++] = d
    }
    System.arraycopy(sumL, 0, buf, 0, upper + 1)
    sa[buf[s[n - 1]]++] = n - 1
    for (v in sa) if (v >= 1 && !ls[v - 1]) sa[buf[s[v - 1]]++] = v - 1
    System.arraycopy(sumL, 0, buf, 0, upper + 1)
    for (i in n - 1 downTo 0) {
      val v = sa[i]
      if (v >= 1 && ls[v - 1]) sa[--buf[s[v - 1] + 1]] = v - 1
    }
  }

  val lmsMap = IntArray(n + 1) {-1}
  var m = 0
  for (i in 1 until n) if (!ls[i - 1] && ls[i]) lmsMap[i] = m++

  val lms = IntArray(m)
  var p = 0
  for (i in 1 until n) if (!ls[i - 1] && ls[i]) lms[p++] = i
  induce(lms)

  if (m == 0) return sa
  val sortedLms = IntArray(m)
  p = 0
  for (v in sa) if (lmsMap[v] != -1) sortedLms[p++] = v
  val recS = IntArray(m)
  var recUpper = 0
  recS[lmsMap[sortedLms[0]]] = 0
  for (i in 1 until m) {
    var l = sortedLms[i - 1]
    var r = sortedLms[i]
    val endL = if (lmsMap[l] + 1 < m) lms[lmsMap[l] + 1] else n
    val endR = if (lmsMap[r] + 1 < m) lms[lmsMap[r] + 1] else n
    val same = if (endL - l != endR - r) false
    else {
      while (l < endL && s[l] == s[r]) {
        l++
        r++
      }
      l != n && s[l] == s[r]
    }
    if (!same) recUpper++
    recS[lmsMap[sortedLms[i]]] = recUpper
  }
  val recSA = sais(recS, recUpper)
  
  for (i in 0 until m) sortedLms[i] = lms[recSA[i]]
  induce(sortedLms)
  return sa
}

C問題 - Rotation

問題の性質に注目しましょう。

\(S_i\) を \(S\) の \(i\) 文字目と定義します。 また、 \(S_i = S_{i \bmod N}\) と定義します。例えば \(S\) がabcのとき、abcabcabc…と続く無限に長い文字列の一部だけ見ているようなイメージです。

さて、 1 xを高速に処理しましょう。 「 \(S\) の末尾の文字を削除し、先頭に挿入する」操作は、無限に長い文字列の方では先頭を \(1\) 文字前にずらす操作になります。 abcabcabc…がcabcabcab…となる形です。

ということは、この操作を \(x\) 回行うと、先頭の文字は \(x\) 文字前になります。

この考察を用いると、この問題は以下のように解けます。

  1. 先頭の位置 \(p\) を持つ。初め、 \(p=0\) である。
  2. 1 xが与えられたとき、 \(p -= x\) とする。
  3. 2 xが与えられたとき、 \(S_{p+x}\) を出力する。

ここで \(p+x\) は負になる場合もあるので、正しく \(\bmod N\) を取ることに気を付けてください。ModIntを使うのも一つの手かもしれません。

Javaの実装例

import java.util.Scanner;
import java.io.PrintWriter;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    int N = sc.nextInt(), Q = sc.nextInt();
    String S = sc.next();
    int p = 0; // この位置から始める
    while(Q --> 0) {
      int query = sc.nextInt(), x = sc.nextInt();
      if (query == 1) p = (p + N - x) % N; // xを引くこととN-xを足すことはmod N上で等しい
      else out.println(S.charAt((p + x - 1) % N));
    }
    out.flush();
  }
}

Kotlinの実装例

import java.util.Scanner
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val Q = sc.nextInt()
    val S = sc.next()
    var p = 0 // この位置から始める
    repeat(Q) {
      val query = sc.nextInt()
      val x = sc.nextInt()
      when(query) {
        1 -> {p = (p + N - x) % N} // xを引くこととN-xを足すことはmod N上で等しい        2 -> {println(S[(p + x - 1) % N])}
      }
    }
  }
}

ところで、この問題は入出力が多いためにTLEすることがあります。 この下に高速入出力を置いておくので、良ければお使いください(コード長を抑えるためにほどほどの高速化に留めていますので、必要であれば各自で高速化をお願いします)。

Javaの高速入出力

import java.io.PrintWriter;
public class Main {
  public static void main(String[] args) {
    FastScanner sc = new FastScanner();
	PrintWriter out = new PrintWriter(System.out);
    new Main(sc, out);
    out.flush();
  }
  
  public Main(FastScanner sc, PrintWriter out) {
    int N = sc.nextInt(), Q = sc.nextInt();
    char[] S = sc.next().toCharArray();
    int p = 0; // この位置から始める
    while(Q --> 0) {
      int query = sc.nextInt(), x = sc.nextInt();
      if (query == 1) p = (p + N - x) % N; // xを引くこととN-xを足すことはmod N上で等しい
      else out.println(S[(p + x - 1) % N]);
    }
  }
}

class FastScanner {

  private final java.io.InputStream in = System.in;
  private final byte[] buffer = new byte[8192];
  private int ptr = 0;
  private int buflen = 0;

  private boolean hasNextByte() {
    if (ptr < buflen) return true;
    ptr = 0;
    try {
      buflen = in.read(buffer);
    } catch (java.io.IOException e) {
      e.printStackTrace();
    }
    return buflen > 0;
  }

  private byte readByte() {
    return hasNextByte() ? buffer[ptr++ ] : -1;
  }

  private static boolean isPrintableChar(byte c) {
    return 32 < c || c < 0;
  }

  private static boolean isNumber(int c) {
    return '0' <= c && c <= '9';
  }

  public boolean hasNext() {
    while (hasNextByte() && !isPrintableChar(buffer[ptr]))
      ptr++ ;
    return hasNextByte();
  }

  public String next() {
    if (!hasNext()) throw new java.util.NoSuchElementException();
    StringBuilder sb = new StringBuilder();
    byte b;
    while (isPrintableChar(b = readByte()))
      sb.appendCodePoint(b);
    return sb.toString();
  }

  public final char nextChar() {
    if (!hasNext()) throw new java.util.NoSuchElementException();
    return (char)readByte();
  }

  public final long nextLong() {
    if (!hasNext()) throw new java.util.NoSuchElementException();
    long n = 0;
    try {
      byte b = readByte();
      if (b == '-') {
        while (isNumber(b = readByte()))
          n = n * 10 + '0' - b;
        return n;
      } else if (!isNumber(b)) throw new NumberFormatException();
      do
        n = n * 10 + b - '0';
      while (isNumber(b = readByte()));
    } catch (java.util.NoSuchElementException e) {}
    return n;
  }

  public final int nextInt() {
    if (!hasNext()) throw new java.util.NoSuchElementException();
    int n = 0;
    try {
      byte b = readByte();
      if (b == '-') {
        while (isNumber(b = readByte()))
          n = n * 10 + '0' - b;
        return n;
      } else if (!isNumber(b)) throw new NumberFormatException();
      do
        n = n * 10 + b - '0';
      while (isNumber(b = readByte()));
    } catch (java.util.NoSuchElementException e) {}
    return n;
  }

  public double nextDouble() {
    return Double.parseDouble(next());
  }
}

Kotlinの高速入出力

import java.io.IOException
import java.io.PrintWriter

fun main() {
  val sc = FastScanner()
  val out = PrintWriter(System.`out`)
  solve(sc, out)
  out.flush()
}

fun solve(sc: FastScanner, out: PrintWriter) {
  val N = sc.nextInt()
  val Q = sc.nextInt()
  val S = sc.next()
  var p = 0 // この位置から始める
  repeat(Q) {
    val query = sc.nextInt()
    val x = sc.nextInt()
    if (query == 1) p = (p + N - x) % N // xを引くこととN-xを足すことはmod N上で等しい
    else out.println(S[(p + x - 1) % N])
  }
}

class FastScanner { // 正直、ただ移植してるだけになってて良くないかも
  private val `in` = System.`in`
  private val buffer = ByteArray(8192)
  private var ptr = 0
  private var buflen = 0
  private fun hasNextByte(): Boolean {
    if (ptr < buflen) return true
    ptr = 0
    try {
      buflen = `in`.read(buffer)
    } catch (e: IOException) {
      e.printStackTrace()
    }
    return buflen > 0
  }

  private fun readByte(): Byte = if (hasNextByte()) buffer[ptr++] else -1

  operator fun hasNext(): Boolean {
    while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++
    return hasNextByte()
  }

  operator fun next(): String {
    if (!hasNext()) throw NoSuchElementException()
    val sb = StringBuilder()
    var b = readByte()
    while (isPrintableChar(b)) {
      sb.appendCodePoint(b.toInt())
      b = readByte()
    }
    return sb.toString()
  }

  fun nextChar(): Char {
    if (!hasNext()) throw NoSuchElementException()
    return readByte().toChar()
  }



  fun nextLong(): Long {
    if (!hasNext()) throw NoSuchElementException()
    var n = 0L
    try {
      var b = readByte()
      if (b == '-'.toByte()) {
        do {
          n = n * 10 + '0'.toLong() - b
          b = readByte()
        } while (isNumber(b))
        return n
      } else if (!isNumber(b)) throw NumberFormatException()
      do {
        n = n * 10 + b - '0'.toLong()
        b = readByte()
      } while (isNumber(b))
    } catch (e: NoSuchElementException) {
    }
    return n
  }

  fun nextInt(): Int {
    if (!hasNext()) throw NoSuchElementException()
    var n = 0
    try {
      var b = readByte()
      if (b == '-'.toByte()) {
        b = readByte()
        do {
          n = n * 10 + '0'.toInt() - b
          b = readByte()
        } while (isNumber(b))
        return n
      } else if (!isNumber(b)) throw NumberFormatException()
      do {
        n = n * 10 + b - '0'.toInt()
        b = readByte()
      } while (isNumber(b))
    } catch (e: NoSuchElementException) {
    }
    return n
  }

  fun nextDouble() = next().toDouble()

  private fun isPrintableChar(c: Byte) = 32 < c || c < 0

  private fun isNumber(c: Byte) = c.toChar() in ('0'..'9')
}

D問題 - Trophy

具体的な戦略を考えてみましょう。

直感的には、一番効率の良いステージを周回すると最も速いように感じます。 つまり、あるステージ \(x\) が存在して、ステージ \(x\) を最速で解放し、後はひたすらステージ \(x\) を周回すると良いように感じます。

この戦略が最適であることを背理法を用いて証明します。 仮に、 \(x\) の他にも \(2\) 回以上遊ぶステージが存在するとします。 そのステージを \(y\) としたとき、仮に \(B_x \leq B_y\) ならば代わりにステージ \(x\) をひたすら遊ぶことがより高効率であり、 \(B_x > B_y\) ならば代わりにステージ \(y\) をひたすら遊ぶことがより高効率です。 従って、複数のステージを \(2\) 回以上遊ぶ意味はありません。同様に、 \(x\) より後ろのステージを遊ぶ必要もありません。

また、周回するステージ \(x (x \leq X)\) を決め打った時、必要な時間は \(\sum_{i=1}^{x} (A_i + B_i) + (X - x) B_x\) と求まります。 ここで \(\sum_{i=1}^{x} (A_i + B_i)\) は累積和から \(O(1)\) で求まるので、各 \(x\) に対して \(O(1)\) で必要な時間が求まり、全体 \(O(N)\) で解くことができます。

Javaの実装例

import java.util.Scanner;
import static java.lang.System.out;
public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt(), X = sc.nextInt();
      long sum = 0; // sumに∑[i=1, x](A_i + B_i)を管理する
      long ans = Long.MAX_VALUE; // 最小化なのでminを取る なので単位元である∞を入れておく
      for (int x = 1;x <= Math.min(N, X);++ x) { // Xより大きいステージは挑めない
        long A = sc.nextLong(), B = sc.nextLong(); // 後でX*Bを求める、32bitより大きくなるためlongで受け取っておく
        sum += A + B;
        ans = Math.min(ans, sum + (X - x) * B);
      }
      out.println(ans);
    }
  }
}

Kotlinの実装例

import java.util.Scanner
import kotlin.math.min
fun main() {
  Scanner(System.`in`).use { sc -> 
    val N = sc.nextInt()
    val X = sc.nextInt()
    var sum = 0L // sumに∑[i=1, x](A_i + B_i)を管理する
    var ans = Long.MAX_VALUE  // 最小化なのでminを取る なので単位元である∞を入れておく
    for (x in 1..min(N, X)) {  // Xより大きいステージは挑めない
      val A = sc.nextLong()
      val B = sc.nextLong()
      sum += A + B
      ans = min(ans, sum + (X - x) * B)
    }
    println(ans)
  }
}

posted:
last update: