【Rコードの効率化】競プロ典型90問 with R［11 / 90］

Last updated at 2025-03-24Posted at 2025-03-15

記事の概要

競プロ典型90問 (https://atcoder.jp/contests/typical90) を R 言語で解いていきます。R は統計分野で非常にポピュラーな言語である一方、実行速度の面で c++［や Python］などに劣るため、競技プログラミングの文脈で使用されることはほとんどありません¹。このため、c++ や Python のコードの実行速度を改善するための情報が世の中に溢れているのに比べて、R のコードを改善するための情報はそれほど多くありません。このような状況は、R の学習者にとって少しもったいないと著者は感じています。

この記事は、R のみで典型90問にどの程度まで対応できるのかを著者の能力が許す範囲で試行錯誤することを通じて²、R のコードを書く時の Tips を発見することを目的としています。著者が理解した原則や Tips は、次の節に整理されています。それ以降は、典型90問の提出コードと箇条書きのメモが続きます。趣味の範囲で少しずつ、気長にやっていく予定です。

記事を通じて、文中の各括弧［］はその中の情報が未検証であることを意味します。また、AtCoder の提出コードへのリンクを掲載し、隣にジャッジ結果³と実行時間の情報を付記します。著者自身の記録のために、AC コード以外を掲載することもあるかもしれません。

高速化 Tips

高速な内部関数を活用する
ベクトル化された関数を活用する
総称的関数はクラスを指定する
オブジェクトを適切に構築・変更する
無駄な copy-on-modify を回避する

1. 高速な内部関数を活用する

R には C/C++/Fortran で内部的に実装された高速な関数（.Primitive）やインタプリタに組み込まれた関数（.Internal）が多数用意されています。多くの内部関数はベクトル化されており、内部関数による処理に帰着させることができれば、R のような動的言語ではどうしても非効率になりがちなループ処理を回避することもできます。R コードの効率化において重要なポイントの一つは、これらの内部関数を最大限に活用することです。

.Primitive
ある組み込み関数が .Primitive であるかどうかは、その関数を定義している R コードを確認することで調べられます（is.primitive() 関数でも判定できます）。

# .Primitive な組み込み関数の例
base::gamma # Γ(x)
#> function (x)  .Primitive("gamma")
base::`+`
#> function (e1, e2)  .Primitive("+")
.Primitive # 自己言及的でややこしい
function (name)  .Primitive(".Primitive")

# .Primitive でない組み込み関数の例
base::factorial
#> function(x)
#> gamma(x + 1)

下の例では、無作為に並んだ $1$ 以上 $100$ 以下の整数ベクトルに対して、各要素の階乗 $n!$ の値を ➀ sapply(x, function(x) prod(1:x)) ➁ factorial(x) ➂ gamma(x + 1) という三種類のコードで計算したときの実行時間を比較しています。➀は遅く、➁と➂には内部関数を直接利用するかどうかによるわずかな差が生じています。

# 階乗の計算速度の比較
n <- 100
x <- sample(n)
expr1 <- expression(sapply(x, function(x) prod(1:x)))
expr2 <- expression(factorial(x))
expr3 <- expression(gamma(x + 1))
microbenchmark::microbenchmark(eval(expr1), eval(expr2), eval(expr3))
#> Unit: microseconds
#>         expr    min     lq     mean  median      uq    max neval
#>  eval(expr1) 109.79 112.06 134.9970 114.565 149.410 266.55   100
#>  eval(expr2)   4.31   4.71   5.9762   5.040   5.705  23.97   100
#>  eval(expr3)   4.09   4.40   5.2994   4.665   5.360  11.01   100

.Internal
内部関数の他にも、R のインタプリタ上に組み込まれた内部関数が存在します。これらの関数は、.Internal() 関数に Call（関数呼び出し）を直接渡すことで利用できます。base 環境に定義された同名のインターフェース関数と比べて引数の型や順番が異なる点に注意が必要です。もっとも、インターフェース関数を利用することによる速度低下はごくわずかなので、回数の多いループ処理の中で実行する場合を除けば気にする必要はありません。

# .Internal な関数呼び出しの例
.Internal(pmin(na.rm = FALSE, 1:10, 10:1))
#> [1] 1 2 3 4 5 5 4 3 2 1
x <- as.double(1:10)
vec <- as.double(c(3, 6, 9))
.Internal(findInterval(vec, x, FALSE, FALSE, FALSE))
#> [1] 0 0 1 1 1 2 2 2 3 3

# .Internal でない関数呼び出しの例
pmin(1:10, 10:1, na.rm = FALSE)
#> [1] 1 2 3 4 5 5 4 3 2 1
x <- as.double(1:10)
vec <- as.double(c(3, 6, 9))
findInterval(x, vec)
#> [1] 0 0 1 1 1 2 2 2 3 3

2. ベクトル化された関数を活用する

R の多くの組み込み関数は .Primitive や .Internal のようなベクトル化された内部関数を正しく利用して定義されているため、ベクトル化の恩恵をそのまま引き継いでいます。したがって、組み込み関数を積極的に用いることでループ処理を回避することができます。

# ベクトル化された関数 ifelse() による高速化
n <- 1e5
m <- 5e4
x <- sample(n)
expr1 <- expression(y <- numeric(n), for (i in 1:n) y[i] <- if(x[i] > m) x[i] else 0)
expr2 <- expression(y <- ifelse(x > m, x, 0))
microbenchmark::microbenchmark(eval(expr1), eval(expr2))
#> Unit: milliseconds
#>         expr      min       lq     mean   median       uq       max neval
#>  eval(expr1) 8.285057 8.475347 8.918903 8.621047 8.739062  12.94639   100
#>  eval(expr2) 1.759251 1.805747 4.069947 1.838206 3.097033 132.29453   100

3. 総称的関数はクラスを指定する

R の関数の中には総称的関数（generic function；汎用関数）と呼ばれるものがあります。総称的関数は、先頭の引数に渡されたオブジェクトのクラスを参照して処理（method）を分岐するという特徴を持ちます。

ある関数が総称的関数であるかどうかは、その関数の定義を確認することで調べられます（isGeneric() 関数を利用して判定することも可能です）。

# 総称的関数の例
base::diff
#> function (x, ...) 
#> UseMethod("diff")

methods("diff") # メソッドの一覧（一部抜粋）
#> [1] ...  diff.Date  diff.default  diff.difftime  ...

総称的関数を利用するときは diff.default() のように引数のクラスを明示することで分岐の判定を省略することができます。ただし、この工夫による効果は非常にわずかであり、ループの中で使用する場合などを除けば無視しても問題ありません。

x <- sample(10)
times <- 1e4
expr1 <- expression(for (i in seq_len(times)) diff(x))
expr2 <- expression(for (i in seq_len(times)) diff.default(x))
microbenchmark::microbenchmark(eval(expr1), eval(expr2))
#> Unit: milliseconds
#>         expr      min       lq     mean   median       uq       max neval
#>  eval(expr1) 36.47495 37.46836 41.46717 41.02733 41.57082 164.27747   100
#>  eval(expr2) 24.76773 25.29104 27.71984 26.18812 29.64242  42.33706   100

4. オブジェクトを適切に構築・変更する

ベクトルの構築

ベクトルは vector(mode, length) 関数で構築できます。mode に "double" や "logical" などの型を指定すると、その型のベクトルが出力されます。vector(mode = "double", length) の代わりに double(length) や numeric() とすることも可能で、型に対応する関数が用意されています。

リストも vector(mode = "list", length) によって構築することが可能です。ただし、list(...) 関数は ... に渡されたオブジェクトを要素とするリストを構築する関数であり、double() のような使い方はできません。

長さ $n$ ごとの構築時間を測定すると以下のようになります。

logical 型と integer 型が他の型に比べて高速
リストは double 型や character 型と同程度の実行時間で構築可能

# 比較に用いた表現式
expr1 <- quote(vector("logical", n)) # logical(n) も同じ
expr2 <- quote(vector("integer", n)) # integer(n) も同じ
expr3 <- quote(vector("double", n)) # double(n) または numeric(n) も同じ
expr4 <- quote(vector("character", n)) # character(n) も同じ
expr5 <- quote(vector("list", n))

なお、vector() 関数は同名の .Internal 関数のインターフェースであるため、直接 .Internal(vector("double", 1e5)) のように書くことで（極めてわずかに）高速化できます。

値の追加

ベクトルに値を追加する方法として、x <- c(x, value) のようなコードが計算量の面から非効率であることは有名です。その理由は、後述する "copy-on-modify" という R 言語に特有のルールのために、この方法で値を追加するたびにベクトル全体の再構築が行われてしまうためです。

以下の例は、4 種類の異なる方法でベクトルに値を追加する操作を $n=1000～10000$ 回行ったときの実行時間の変化を表すグラフを比較したものです（R のバージョンは）。

expr1：最初にベクトルの長さを確保して x[i] <- value で代入する方法
expr2：ベクトルの長さを確保せずに x[i] <- value で追加する方法
expr3：x <- c(x, value) でベクトルを再構築する方法
expr4：x <- append(x, value) で値を追加する方法

結果のグラフからは、expr3 や expr4 の方法が非常に非効率であることがわかります。また、インデックスを用いて値の代入を行う方法であれば、ベクトルの構築時にサイズを確保しているかどうかは、$n = 10000$ 以下の範囲では実行時間にほとんど影響を与えないようです。

# ベクトルへの値の追加
expr1 <- expression(x <- numeric(n), for (i in 1:n) x[i] <- i)
expr2 <- expression(x <- numeric(), for (i in 1:n) x[i] <- i)
expr3 <- expression(x <- numeric(), for (i in 1:n) x <- c(x, i))
expr4 <- expression(x <- numeric(), for (i in 1:n) x <- append(x, i))

expr1 と expr2 の二つを $n = 10^4～10^6$ の範囲で比較すると結果は次のようになり、計算量のオーダーに明確な差はなさそうに見えるものの、expr1 の方が明らかに高速であることがわかります。非常に長いベクトルを利用する場合（特に $n \ge 10^5$ の範囲：補足参照）は、できるだけベクトルの構築時に必要なサイズを確保しておくべきでしょう。

リストに値を追加する場合も、以下のコードの実行時間を比較することで同様の結果が得られます。

# リストへの値の追加
expr1 <- expression(x <- vector("list", n), for (i in 1:n) x[[i]] <- i)
expr2 <- expression(x <- list(), for (i in 1:n) x[[i]] <- i)
expr3 <- expression(x <- list(), for (i in 1:n) x <- c(x, i))
expr4 <- expression(x <- list(), for (i in 1:n) x <- append(x, i))

補足：AtCoder 環境での比較

expr1 と expr2 について、AtCoder のコードテスト機能を利用して比較した結果を下の表にまとめます。$n \le 10^5$ 程度まではどの方法の実行時間も許容範囲ですが、$n \gt 10^5$ の範囲では expr1 の方が明確に良いようです。

$n$	`expr1` double	`expr2` double	`expr1` list	`expr2` list
$10^3$	$136$ ms	$136$ ms	$137$ ms	$135$ ms
$10^4$	$141$ ms	$143$ ms	$139$ ms	$142$ ms
$10^5$	$142$ ms	$170$ ms	$145$ ms	$189$ ms
$10^6$	$178$ ms	$335$ ms	$286$ ms	$1111$ ms
$10^7$	$566$ ms	$2675$ ms	$1889$ ms	$\gt10550$ ms

なお、環境を指定してベクトルに変更を加える場合は定数倍が重く、以下のコードの実行時間は約 $1,000$ ms となります。

# 指定した環境内のベクトルに値を追加
n <- 1e7
E <- new.env()
E$x <- numeric(n)
for (i in 1:n) E$x[i] <- i

値の変更

ベクトルやリストの値を変更するときは、インデックスを指定して x[i] <- value のようにすれば十分です。ただし、ベクトルに設定された型では解釈できない値を代入してしまうと、ベクトル全体が新しい型で再構築されてしまうため注意が必要です。

下の例では、integer 型のベクトルに 0.0 という double 型の値を代入する処理（expr1）の実行時間を、double 型のベクトルを用いる場合（expr2）の実行時間と比較しています。ベクトルの構築にかかる時間は expr1 の方が短いにも関わらず、値の変更までを含めた実行時間は逆転しており、値の代入時に double 型のベクトルが再構築されていることがわかります。

# 値の変更（型変更に伴う再構築）
microbenchmark(
  expr1 = {x <- integer(1e7); x[1] <- 0.0},
  expr2 = {x <- numeric(1e7); x[1] <- 0.0}
)
#> Unit: milliseconds
#>   expr      min       lq      mean   median        uq      max neval cld
#>  expr1 56.66149 70.07621 111.65538 75.68392  89.27119 325.2021   100   a
#>  expr2 33.25045 42.42657  91.99726 46.10210 202.03193 226.5705   100   a

# ベクトルの構築のみ
microbenchmark(
  expr1 = {x <- integer(1e7)},
  expr2 = {x <- numeric(1e7)}
)
#> Unit: milliseconds
#>   expr      min       lq     mean   median       uq      max neval cld
#>  expr1 16.69308 18.22149 45.38674 18.99538 30.84683 210.0227   100  a 
#>  expr2 34.39694 39.81781 65.99914 47.73621 51.36052 233.5095   100   b

値の削除

R ではベクトルから in-place に値を削除することができないため、不要な要素を取り除いたベクトルを再構築する方法が取られます。

リストに限れば、インデックスを指定して NULL を代入することで要素を削除することができます。ただし、この処理には結局 $O(N)$ の計算量を要するようで、インデックスを指定して再構築する方法と比べて本質的な改善は見込めません。

# 先頭の値から順番に削除
expr1 <- expression(x <- vector("list", n), for (i in 1:n) x[[1]] <- NULL)
# 最後尾の値から順番に削除
expr2 <- expression(x <- vector("list", n), for (i in 1:n) x[[length(x)]] <- NULL)
# インデックスを指定して再構築
expr3 <- expression(x <- vector("list", n), for (i in 1:n) x <- x[seq_len(n - i)])

名前による参照

ベクトルやリストは、それ自体と同じ長さの character 型ベクトルを名前ベクトル（names 属性）として持つことができます。名前ベクトルが定義されていれば、その要素に名前でアクセスすることができます。ただし、ベクトルやリストの要素を名前で指定すると、その名前を名前ベクトルの中から線形探索する処理が行われてしまうため、インデックスを直接指定する方法よりも非効率になります。

x <- c(Alice = 1, Bob = 3)
x["Bob"] <- 2 # 名前を指定して値ｗ代入
x
#> Alice   Bob 
#>     1     2 
x["Carol"] <- 3 # 名前が存在しないときは末尾に追加
x
#> Alice   Bob Carol 
#>     1     2     3
names(x) # attr(x, "names") も結果は同じだが names() は .Primitive
#> [1] "Alice" "Bob"   "Carol"

5. 無駄な copy-on-modify を回避する

R では、単一のオブジェクトに複数の名前（Binding）を付与することができます。その状態からいずれかの名前を通じてオブジェクトに変更を加えると、その時点でオブジェクトが複製されます。この仕様のことを "copy-on-modify" といいます。

# copy-on-modify
x <- 1:10
rlang::obj_address(x)
#> "0x...hoge"
y <- x
rlang::obj_address(y) # 同一アドレス
#> "0x...hoge"
y[5] <- -5 # 変更を加えるときに複製される
rlang::obj_address(y) # 複製後のアドレス
#> "0x...fuga"
rlang::obj_address(x) # もとのアドレス
#> "0x...hoge"

in-place に実行できる変更を関数に任せてはいけない

この仕様のため、たとえば自作関数に渡したベクトルなどに関数の中で変更を加えると、関数の実行環境の中にそのオブジェクトが複製されてしまいます。これを意識せずにコードを書くととてつもなく非効率な計算を行うことになるので注意が必要です。また、R の関数では「参照渡し」が行われるわけではないため、変更後の値を出力して再代入するか、eval 関数を用いて代入のための表現式を評価する環境を指定しないかぎり、もとの変数の値は変更されません。

x <- numeric(1e5)
# 関数の中で値を変更すると非効率
set0 <- function(x, i) x[i] <- 0
microbenchmark::microbenchmark(
  set0(x, 1),
  x[1] <- 0
)
#> Unit: nanoseconds
#>        expr   min    lq      mean median     uq     max neval cld
#>  set0(x, 1) 60860 68115 312110.36 359660 370115 6198376   100  a 
#>   x[1] <- 0   440   525   1031.63    890   1295    3510   100   b

# 値を参照するだけなら問題ない
cati <- function(x, i) cat(x[i])
microbenchmark::microbenchmark(
  cati(x, 1),
  cat(x[1])
)
#> Unit: microseconds
#>        expr   min      lq     mean median     uq      max neval cld
#>  cati(x, 1) 11.55 11.8200 26.69426 12.095 12.305 1278.711   100   a
#>   cat(x[1]) 10.99 11.3705 11.86534 11.530 11.760   34.220   100   a

なお、例外的に名前をただ一つ持つオブジェクトと環境（Environment）に加えられた変更は in-place に反映されます。

001 - Yokan Party（★4）

提出コード［AC, 349ms］

階差は diff() 関数で一括計算可能（diff.default() でわずかに改善するはず）
ただし diff(A) よりも A[2:N] - A[1:(N - 1)] の方が高速

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

NL <- rin() |> split() |> as.integer()
K <- rin() |> as.integer()
A <- rin() |> split() |> as.integer()
D <- c(A[1L], diff(A), NL[2L] - A[NL[1L]])
bs <- function(ok, ng, prop) {
  while (abs(ok - ng) > 1) {
    mid <- (ok + ng) %/% 2
    if (prop(mid)) {
      ok <- mid
    } else {
      ng <- mid
    }
  }
  c(ok, ng)
}
prop <- function(score) {
  cnt <- 0
  tmp <- 0
  for (d in D) {
    tmp <- tmp + d
      if (score <= tmp) {
        cnt <- cnt + 1
        tmp <- 0
      }
  }
  K + 1 <= cnt
}
cat(bs(1L, NL[2L], prop)[1L])

002 - Encyclopedia of Parentheses（★3）

提出コード［AC*, 718ms］

組み合わせは utils::combn で対応可能
必要なサイズの行列をあらかじめ用意して解を構築［ループごとにベクトルを構築するよりも高速］
行列からの抽出行数（列数）が 1 になりうる場合はインデックスに drop = FALSE を添える（そうしないと勝手にベクトルに変換されてしまう）

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

N <- rin() |> as.integer()
if (N %% 2L == 0L) {
  cmb <- combn(N, N %/% 2)
  M <- ncol(cmb)
  mat <- matrix(-1L, M, N)
  ok <- logical(M)
  for (i in seq_len(M)) {
    mat[i, cmb[, i]] <- 1L
    ok[i] <- all(cumsum(mat[i, ]) >= 0)
  }
  ans <- ifelse(mat[ok, , drop = FALSE] > 0, "(", ")")
  cat(apply(ans, 1, paste0, collapse = ""), sep = "\n")
}

003 - Longest Circular Road（★4）

提出コード［AC*, 846ms］

-［利用可能な範囲のパッケージには deque がないので］非再帰 DFS をポインタ付きのベクトルを用いて実装
‐ リストへの要素の追加は hoge[[length(hoge) + 1L]] <- value とする

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

N <- as.integer(rin())
AB <- matrix(as.integer(split(rin(N))), ncol = 2L, byrow = TRUE)
G <- lapply(numeric(N), function(x) list())
for (i in seq_len(nrow(AB))) {
  u <- AB[i, 1L]
  v <- AB[i, 2L]
  G[[u]][[length(G[[u]]) + 1L]] <- v
  G[[v]][[length(G[[v]]) + 1L]] <- u
}
bfs <- function(graph, start, length.cue = 1e6L) {
  seen <- logical(length(graph))
  dist <- numeric(length(graph))
  todo <- numeric(length.cue)
  l <- 1L
  r <- 1L
  seen[start] <- TRUE
  todo[r] <- start
  r <- r + 1L
  while (l < r) {
    v <- todo[l]
    l <- l + 1L
    for (w in graph[[v]]) {
      if (seen[w]) next
      seen[w] <- TRUE
      dist[w] <- dist[v] + 1L
      todo[r] <- w
      r <- r + 1L
    }
  }
  list(v = v, dist = dist)
}
tmp <- bfs(G, 1L)
ans <- bfs(G, tmp$v)
cat(ans$dist[ans$v] + 1L)

004 - Cross Sum（★2）

提出コード［AC, 4796ms］

大きめの行列を与えられるケースが非常に遅い（制約上の最大ケースは 2,000 × 2,000）
行列の和差に帰着させるとぎりぎりで TLE を回避できる
［rowSums() colSums() は apply() よりもわずかに高速らしい］

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

HW <- rin() |> split() |> as.integer()
H <- HW[1L]
W <- HW[2L]
A <- rin(H) |> split() |> as.integer() |> matrix(ncol = W, byrow = TRUE)
R <- rowSums(A)
C <- colSums(A)
ans <- rep.int(1, H) %*% t(C) + R %*% t(rep.int(1, W)) - A
cat(paste0(apply(ans, 1L, paste0, collapse = " "), collapse = "\n"))

006 - Smallest Subsequence（★5）

提出コード［AC*, 594ms］

解の構築は長さ $K\le100,000$ のベクトルに値を埋めていく方法を取ったが、空のリストに ans[[length(ans) + 1L]] <- value で値を追加していく方法でもそれほど遅くならない（612ms：提出コード）
R の base には letters（a から z までを要素として持つベクトル）が定義されているが、intToUtf8() 関数は数値ベクトルに対して文字列を返すので便利［ただし paste0(letters[hoge], collapse = "") との比較は未済］

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

abc2int <- function(s) utf8ToInt(s) - 96 # a: 1
int2abc <- function(n) intToUtf8(n + 96) # 1: a, 一つの文字列を返す
NK <- as.integer(split(rin()))
N <- NK[1L]
K <- NK[2L]
S <- abc2int(rin())
M <- matrix(-1, 26, N)
for (i in 1:26) {
  for (j in N:1) {
    if (j < N)
      M[i, j] <- M[i, j + 1]
    if (S[j] == i)
      M[i, j] <- N - j
  }
}
ans <- numeric(K)
j <- 1
for (k in 1:K) {
  for (i in 1:26) {
    if (K - k <= M[i, j]) {
      ans[k] <- i
      j <- N - M[i, j] + 1
      break
    }
  }
}
cat(int2abc(ans))

007 - CP Classes（★3）

提出コード［AC*, 1012ms］

自前実装の二分探索では TLE を避けられそうにないが、ベクトル化された .Internal な二分探索関数 findInterval() を使えば間に合う

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

N <- rin() |> as.integer()
A <- rin() |> split() |> as.integer() |> sort()
Q <- rin() |> as.integer()
B <- rin(Q) |> split() |> as.integer()
i <- findInterval(B, A)
ans <- pmin(abs(A[pmax(i, 1L)] - B), abs(A[pmin(i + 1L, N)] - B))
cat(paste(ans, collapse = "\n"))

008 - AtCounter（★4）

提出コード［AC*, 608ms］

dp テーブルは行列や配列を使えば問題ない（領域を確保していれば値の変更は高速かつインプレースに処理できる）
Python と異なり大きな整数値を素直に扱えないので剰余の計算は都度行う必要がある（最後で剰余を取るように変更すると WA）

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

n <- as.integer(rin())
x <- strsplit(rin(), "")[[1L]]
y <- strsplit("atcoder", "")[[1L]]
mod <- 1000000007
dp <- matrix(0L, n + 1L, 8L)
for (i in seq_len(n + 1L)) {
  dp[i, 1L] <- 1L
  if (i == 1L)
    next
  for (j in 2L:8L) {
    dp[i, j] <- dp[i - 1L, j] +
      (if (x[i - 1L] == y[j - 1L]) dp[i - 1L, j - 1L] else 0L)
    dp[i, j] <- dp[i, j] %% mod
  }
}
cat(dp[n + 1, 8L])

010 - Score Sum Queries（★2）

提出コード［AC, 830ms］

累積和は cumsum()
ベクトルの各要素に対する条件分岐は ifelse()

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

N <- as.integer(rin())
CP <- as.integer(split(rin(N))) |> matrix(N, byrow = TRUE)
Q <- as.integer(rin())
LR <- as.integer(split(rin(Q))) |> matrix(Q, byrow = TRUE)
cs1 <- c(0, cumsum(ifelse(CP[, 1L] == 1L, CP[, 2L], 0L)))
cs2 <- c(0, cumsum(ifelse(CP[, 1L] == 2L, CP[, 2L], 0L)))
ans <- matrix(0L, Q, 2L)
ans[, 1L] <- cs1[LR[, 2L] + 1L] - cs1[LR[, 1L]]
ans[, 2L] <- cs2[LR[, 2L] + 1L] - cs2[LR[, 1L]]
cat(paste(apply(ans, 1L, paste0, collapse = " "), collapse = "\n"))

012 - Red Painting（★4）

提出コード［AC*, 1986ms］

R では関数の実行環境の外にある変数に対して in-place に変更を加えることが難しく、十分高速に機能する Union-Find を実装することが困難
AC コードでは uf[x] が x の根ノードを表すようなベクトルとして Union-Find を表現し、➀根ノードを探索・更新する処理、➁二つの頂点を unite する処理、➂二つの頂点が同じ根を持つかどうかの判定、をすべてグローバル環境への処理としてべた書き
環境を利用することで実装が簡潔になるが、［環境を参照することによる定数倍が重い］ため TLE（提出コード）

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

get_root <- function(uf, x) {
  path <- numeric()
  while (uf[x] > 0) {
    path[[length(path) + 1]] <- x
    x <- uf[x]
  }
  list(root = x, path = path)
}
HW <- as.integer(split(rin()))
H <- HW[1]
W <- HW[2]
uf <- numeric(H * W)
painted <- matrix(0, H, W)
Q <- as.integer(rin())
di <- c(-1, 0, 1, 0)
dj <- c(0, 1, 0, -1)
ans <- vector("logical", 0)
for (. in seq_len(Q)) {
  q <- as.integer(split(rin()))
  if (q[1] == 1) {
    i <- q[2]
    j <- q[3]
    painted[i, j] <- 1
    for (k in 1:4) {
      .i <- i + di[k]
      .j <- j + dj[k]
      if ((0 < .i) && (.i <= H) && (0 < .j) && (.j <= W) && painted[.i, .j]) {
        x <- ( i - 1) * W +  j
        y <- (.i - 1) * W + .j
        rx <- get_root(uf, x)
        uf[rx$path] <- rx$root
        ry <- get_root(uf, y)
        uf[ry$path] <- ry$root
        # unite x & y
        if (rx$root == ry$root)
          next
        if (uf[rx$root] < uf[ry$root]) {
          rz <- ry
          ry <- rx
          rx <- rz
        }
        uf[rx$root] <- uf[rx$root] + uf[ry$root] - 1
        uf[ry$root] <- rx$root
      }
    }
  } else {
    i <- q[2]
    j <- q[3]
    .i <- q[4]
    .j <- q[5]
    res <- FALSE
    if (painted[i, j] && painted[.i, .j]) {
      x <- ( i - 1) * W +  j
      y <- (.i - 1) * W + .j
      rx <- get_root(uf, x)
      uf[rx$path] <- rx$root
      ry <- get_root(uf, y)
      uf[ry$path] <- ry$root
      # united
      if (rx$root == ry$root) {
        res <- TRUE
      }
    }
    ans[[length(ans) + 1]] <- res
  }
}
ans <- paste0(ifelse(ans, "Yes", "No"), collapse = "\n")
cat(ans)

014 - We Used to Sing a Song Together（★3）

提出コード［AC*, 251ms］

$N$ は使わないので invisible(rin()) で読み飛ばしてもよい

options(scipen = 100, digits = 22)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

N <- as.integer(rin())
A <- as.integer(split(rin())) |> sort()
B <- as.integer(split(rin())) |> sort()
cat(sum(abs(A - B)))

016 - Minimum Coins（★3）

提出コード［AC*, 1984ms］

素朴にループ処理を書くと TLE になるのでループを書かずにベクトル処理を利用
実行時間は制限ギリギリで、ジャッジサーバの調子によって AC になっているだけのような気がする

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

N <- as.integer(rin())
ABC <- as.integer(split(rin()))
A <- ABC[1]
B <- ABC[2]
C <- ABC[3]
amax <- min(10000L, N %/% A)
apos <- 0L:amax
bcnt <- pmin(10000L - apos, (N - A * apos) %/% B) + 1L
as <- rep.int(apos, bcnt)
bs <- .Internal(unlist(lapply(bcnt, function(x) 0:(x - 1)), FALSE, FALSE))
resid <- N - A * as - B * bs
ok <- resid %% C == 0L
cat(min(as[ok] + bs[ok] + resid[ok] %/% C))

参考資料

競プロ典型90問
AtCoder を知る人には言わずと知れた素晴らしい教材。
Advanced R - 2 Names and values
変数名と値の関係、とくに copy-on-modify の振る舞いについて詳述されている
R言語でAtCoderの問題を解いてみた
競技プログラミングを題材にして R 言語を学ぶ人は必読の虎の巻

とはいえ、著者も参考にさせていただいている素晴らしい記事はいくつか存在しています。R 言語で競技プログラミングの問題を解いてみたいと思った方は、一番最初にこちらの記事を読むことをお勧めします。 ↩
もっとも、著者自身の競技プログラミングの能力はそれほど高くないうえに忘れてしまった知識も多く、そもそも言語によらず解けない問題もたくさんあります。 ↩
結果が AC* のようにアスタリスクを伴っている問題では、著者が R で最初の AC を獲得しています。とってもしょーもないですが、モチベーション向上のためなのでご容赦ください。 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up